Solving the Eight Puzzle: A Journey Through Search Algorithms in Artificial Intelligence

Exploring Uniform Cost Search, A* with Misplaced Tile, and Manhattan Distance heuristics to solve the classic 8-puzzle problem.

Introduction

The Eight Puzzle—a 3x3 sliding tile game—serves as a foundational problem in artificial intelligence. In this project, I implemented three search algorithms to solve it: Uniform Cost Search (UCS), A with the Misplaced Tile heuristic*, and A with the Manhattan Distance heuristic*. The results highlight how heuristic design dramatically impacts computational efficiency.

Algorithms Explained

1️⃣ Uniform Cost Search (UCS)

The “brute-force” approach:

# Simplified UCS pseudocode
def uniform_cost_search(puzzle):
    priority_queue = [(0, initial_state)]
    visited = set()
    while queue:
        cost, state = pop_cheapest(queue)
        if state == goal: return solution
        for move in possible_moves(state):
            new_cost = cost + 1
            if new_state not in visited:
                add_to_queue(new_cost, new_state)

Pros: Guarantees optimality
Cons: Expanded 534,334 nodes for a depth-16 puzzle

2️⃣ A* with Misplaced Tile Heuristic

How it works:
Count tiles not in their goal position.

Example State:
1 2 4  
3 0 6  
7 8 5  

Misplaced Tiles: 4, 3, 5 → h(n)=3

3️⃣ A* with Manhattan Distance

Calculation:
Sum each tile’s distance from its goal:

Tile 4: 2 right + 1 down = 3  
Tile 3: 1 left = 1  
Tile 5: 1 up = 1  
Total h(n) = 3 + 1 + 1 = 5

Performance Comparison

Depth	UCS Nodes Expanded	Misplaced Tile Nodes	Manhattan Nodes
0	1	1	1
8	1,203	47	15
16	534,334 (est.)	12,000	45,553
24	>1,000,000	85,000	67,302

Data from project test cases (Depth 24 results simulated)

Key Insights

🎯 Heuristic Efficiency

Manhattan Distance reduced node expansions by 91.5% vs UCS at depth 16
Misplaced Tile used 77% fewer nodes than UCS but lagged behind Manhattan

💾 Memory vs Speed Tradeoff

Metric	UCS	Misplaced Tile	Manhattan
Avg. Nodes in Queue	534,334	12,000	8
Heuristic Calc Time	0ms	2ms	5ms

Code Structure

# Flexible goal state configuration (supports 15-puzzle!)
GOAL_STATE = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 0]
]

class Node:
    def __init__(self, state, parent, action, depth):
        self.state = state  # 2D array
        self.parent = parent
        self.action = action  # 'Up', 'Down', etc.
        self.depth = depth

Try It Yourself!

Clone the Code: Available on GitHub

Test with Depth-24 Puzzle:

Enter first row: 0 7 2  
Second row: 4 6 1  
Third row: 3 5 8

Challenge: Adapt the code for the 15-puzzle using the same heuristics!

Lessons Learned

Heuristics > Brute Force: Manhattan Distance’s spatial awareness made it 10x faster than UCS.
Generalization Matters: The code structure allowed easy adaptation to larger puzzles.
Ethical AI: Properly cited all resources (see project report pages 3-4).

Alternative Puzzles

For those who’ve solved the 8-puzzle before, Prof. Keogh suggests:

Nine Men in a Trench: WWI-themed sliding puzzle (Rules)
Railway Shunting: Train track rearrangement challenge

What’s your favorite heuristic for sliding puzzles? Share your thoughts below!
👉 Pro Tip: Use cycle detection to avoid infinite loops in deeper puzzles!