Introduction

The 8-puzzle is a small search problem with a large enough state space to make brute force wasteful. A* is a good fit because it combines the exact path cost so far with a heuristic estimate of remaining work, which lets it prioritize promising board states while still finding an optimal solution when the heuristic is admissible.

Represent the board as an immutable state

A simple representation is a tuple of nine numbers where 0 is the blank tile. The goal state is usually (1, 2, 3, 4, 5, 6, 7, 8, 0).

1start = (1, 2, 3,
2         4, 0, 6,
3         7, 5, 8)
4
5goal = (1, 2, 3,
6        4, 5, 6,
7        7, 8, 0)

Using an immutable state makes it easy to store boards in sets and dictionaries for visited tracking.

A* uses g, h, and f

For each state:

• 'g is the number of moves from the start state'
• 'h is the heuristic estimate to the goal'
• 'f = g + h is the priority used in the search frontier'

For the 8-puzzle, Manhattan distance is the standard heuristic. It sums how many row and column moves each tile is away from its target position.

1def manhattan(state):
2    total = 0
3    for index, value in enumerate(state):
4        if value == 0:
5            continue
6        target = value - 1
7        row, col = divmod(index, 3)
8        target_row, target_col = divmod(target, 3)
9        total += abs(row - target_row) + abs(col - target_col)
10    return total

Manhattan distance is admissible for the 8-puzzle, which means it never overestimates the remaining cost. That is why A* with this heuristic still finds shortest solutions.

Generate neighbor states by moving the blank

Each move swaps the blank with one adjacent tile. The valid moves depend on the blank position.

1def neighbors(state):
2    index = state.index(0)
3    row, col = divmod(index, 3)
4    moves = []
5
6    for row_delta, col_delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
7        new_row = row + row_delta
8        new_col = col + col_delta
9        if 0 <= new_row < 3 and 0 <= new_col < 3:
10            swap_index = new_row * 3 + new_col
11            new_state = list(state)
12            new_state[index], new_state[swap_index] = new_state[swap_index], new_state[index]
13            moves.append(tuple(new_state))
14
15    return moves

This is the transition model A* explores.

A minimal A* solver

1import heapq
2
3
4def solve(start, goal):
5    frontier = [(manhattan(start), 0, start)]
6    came_from = {start: None}
7    cost_so_far = {start: 0}
8
9    while frontier:
10        _, g, current = heapq.heappop(frontier)
11
12        if current == goal:
13            path = []
14            while current is not None:
15                path.append(current)
16                current = came_from[current]
17            return list(reversed(path))
18
19        for nxt in neighbors(current):
20            new_cost = g + 1
21            if nxt not in cost_so_far or new_cost < cost_so_far[nxt]:
22                cost_so_far[nxt] = new_cost
23                priority = new_cost + manhattan(nxt)
24                heapq.heappush(frontier, (priority, new_cost, nxt))
25                came_from[nxt] = current
26
27    return None
28
29
30path = solve(start, goal)
31for step in path:
32    print(step)

This solver stores the best known path to each state and reconstructs the solution once the goal is reached.

Check solvability before searching

Not every 8-puzzle arrangement is solvable. For the 3x3 puzzle, solvability depends on inversion parity. If the number of inversions is odd, the puzzle cannot be solved from the chosen goal state.

That check saves time because no search algorithm can find a path that does not exist.

Why A* works well here

Breadth-first search also finds an optimal solution, but it explores many more states because it ignores how close a board appears to the goal. A* uses the heuristic to focus effort where it matters. For the 8-puzzle, Manhattan distance is simple, cheap, and strong enough to make a real difference.

For larger puzzles such as the 15-puzzle, heuristic quality matters even more because the search space grows dramatically.

Common Pitfalls

• Using a heuristic that overestimates and then assuming A* is still guaranteed optimal.
• Forgetting to track visited states or best known path costs.
• Mutating board state in place and then corrupting set or dictionary keys.
• Skipping the solvability check and wasting time on impossible inputs.
• Treating the blank tile as a normal tile in the heuristic calculation.

Summary

• Represent the 8-puzzle as an immutable state and search over valid blank-tile moves.
• A* prioritizes states using f = g + h.
• Manhattan distance is the standard admissible heuristic for this puzzle.
• Track parent pointers and path costs so you can reconstruct the optimal path.
• Check solvability first to avoid searching impossible configurations.