The 8 puzzle is what you write first, the day you learn about heuristic search. It is small enough that almost any approach works, large enough that bad approaches are visibly worse than good ones. This article walks the standard solution from top to bottom.
The state
Represent the board as an array of nine integers, indexed 0..8 in row-major order:
positions: indices:
1 2 3 0 1 2
4 5 6 ←→ 3 4 5
7 8 _ 6 7 8
The empty cell is some sentinel value — 0 is the usual choice. The goal state is [1, 2, 3, 4, 5, 6, 7, 8, 0].
The moves
From a position with the empty at index e, you can swap the empty with its orthogonal neighbours: e-3 (above) if not in the top row, e+3 (below) if not in the bottom row, e-1 (left) if not on the leftmost column, e+1 (right) if not on the rightmost column.
A function neighbors(state) returns the up-to-four states reachable in one move.
The heuristic: Manhattan distance
For each tile (ignore the blank), compute the row distance plus the column distance from its current position to its goal position. Sum across tiles. That sum is a lower bound on the number of moves remaining — every tile must travel at least that far.
In pseudocode:
h(state) = sum over tiles t:
abs(row(current) - row(goal)) + abs(col(current) - col(goal))
Manhattan distance is admissible (never overestimates) and consistent (satisfies the triangle inequality). Both properties matter for A*.
A* in twelve lines
A* maintains a priority queue of states, ordered by f = g + h, where g is the depth (moves so far) and h is the heuristic estimate of moves remaining. At each iteration: pop the lowest-f state, expand it, push neighbours with updated f.
open = priority_queue()
open.push(start, f=h(start))
came_from = {}; g = {start: 0}
while open is not empty:
state = open.pop()
if state == goal: return reconstruct_path(came_from, state)
for n in neighbors(state):
tentative_g = g[state] + 1
if n not in g or tentative_g < g[n]:
g[n] = tentative_g
came_from[n] = state
open.push(n, f=tentative_g + h(n))
That is the whole solver. Implement h, implement neighbors, and you can solve any 8 puzzle.
Performance
A* with Manhattan distance solves any 8 puzzle in a few hundred microseconds, expanding a few hundred to a few thousand states for the hardest instances. The state space is small enough that A* dominates IDA* at this size — A* is the right choice for 3×3, IDA* takes over at 4×4 and up.
Common pitfalls
Three things you will get wrong on the first attempt:
State hashing. Python's tuples hash nicely; Java's int arrays do not. Whatever language you use, the state needs to be hashable so the closed/open sets work. A common trick is to encode the 9-tile state as a single 32-bit integer (4 bits per cell, since cells are 0..8).
Forgetting the inversion-parity check. If you generate a random 8 puzzle by shuffling, half the time the puzzle is unsolvable, and A* will explore the entire 181,440-state half-space looking for a path that does not exist. Add a quick parity check before running A*, or generate by walking backwards from the goal.
Treating the blank as a tile in the heuristic. Manhattan distance is summed over the real tiles only. Including the blank inflates the heuristic and breaks admissibility (you can "fix" the blank for free with a move).
Beyond Manhattan
You can do better than Manhattan on the 8 puzzle, but not by much:
- Linear conflict — if two tiles in the same row are both in their goal row but in the wrong order, they will need at least two extra moves to pass each other. Add 2 per conflict. Improves Manhattan by 5–15%.
- Pattern databases — precompute optimal cost over subsets of tiles. Massive memory cost for tiny speed gain on the 8 puzzle. Worth it for 15 puzzle solvers, not here.
For 8 puzzles, plain Manhattan with linear conflict is the practical sweet spot.
What to build next
If you wrote an 8-puzzle solver, the natural extensions are:
- 15 puzzle solver with IDA* + walking distance. Same basic ideas, deeper search. (Guide here.)
- General N puzzle solver with pattern databases. A weekend project.
- Solvability test — a 30-line function that returns true if a board can be reached from the goal. Useful for app development. (Based on the parity theorem.)
The 8 puzzle is small. The techniques you learn solving it scale all the way up.