The 15 puzzle has been a benchmark for AI search algorithms since the 1960s. Each generation of algorithm was invented to push past the wall the previous one hit. This article walks through them in order of invention, with what each was good for and what made the next one necessary.
1960s — Breadth-first search
The first algorithm anyone tries. Explore states level by level: depth 1 has 4 states, depth 2 has 16, depth 3 has 64, and so on. Keep exploring until you find the goal.
For the 8 puzzle, BFS finishes quickly — the worst-case depth is 31, so at most 4³¹ states (much less in practice due to revisits). For the 15 puzzle, the hardest depth is 80, so 4⁸⁰ states. That is more states than atoms in the observable universe. BFS does not finish.
The wall: exponential blowup. Solving by uninformed search is hopeless beyond the 3×3.
1968 — A* search
Hart, Nilsson, and Raphael publish A Formal Basis for the Heuristic Determination of Minimum Cost Paths. The idea: instead of exploring states in order of distance from start, explore in order of f = g + h, where h is a lower-bound estimate of the distance remaining.
For the 15 puzzle, h is Manhattan distance — sum of row+column distances from each tile to its goal. Manhattan is admissible (never overestimates) and consistent (satisfies a triangle inequality). With these properties, A* finds the optimal solution.
Performance on the 15 puzzle: solves any board, but on the hardest instances it explores millions of states and consumes hundreds of megabytes of memory. The wall: memory.
1985 — IDA*
Richard Korf's Depth-first iterative-deepening: An optimal admissible tree search. The insight: instead of A*'s priority queue (which holds all explored states), do iterative-deepening DFS where the depth limit is f-cost rather than depth.
IDA* explores the same states A* would, in approximately the same order, but without remembering them between iterations. Each "depth-first sweep" uses O(depth) memory instead of O(states explored).
Performance on the 15 puzzle: solves any board in seconds on 1985 hardware, fits in kilobytes of memory. The wall: the heuristic is still Manhattan. Speeding up search requires a tighter heuristic.
1990s — Linear conflict
Hansson, Mayer, and Yung's Criticizing solutions to relaxed models yields powerful admissible heuristics. The Manhattan heuristic assumes tiles can pass through each other. They can't.
Linear conflict adds 2 moves to the heuristic for every pair of tiles in the same row, both belonging to that row, but in the wrong order — one will have to be moved out of the row to let the other pass. Similarly for columns.
Effect: typically 5–15% reduction in nodes expanded on hard 15 puzzles. Strict improvement over plain Manhattan; no real downside.
1996 — Walking distance
A heuristic that captures the structure of the puzzle more deeply. For each tile arrangement projected onto rows only (ignoring within-row positions), precompute the minimum number of row-swap operations to put each tile into its correct row. Same for columns.
Walking distance is admissible and considerably tighter than Manhattan + linear conflict — typically 1.5–2× the value of Manhattan, which means IDA* expands far fewer nodes.
Implementation cost: a small precomputed table (~500 KB for a 4×4). Sweet spot for the 15 puzzle.
2002 — Additive disjoint pattern databases
Korf and Felner's Disjoint pattern database heuristics. The strongest known heuristic for sliding puzzles.
The idea: partition the tiles into disjoint groups (a 7+8 partition for the 15 puzzle is standard). For each group, precompute the optimal cost of moving only that group's tiles to their goal positions, ignoring all other tiles. Tabulate every possible arrangement of the group.
At search time, look up each group's contribution and sum. Because the groups are disjoint and the moves needed for each group don't conflict (subject to a careful argument), the sum is admissible.
Memory cost: about 1 GB for the 15 puzzle. Performance: solves the hardest 15 puzzle in a few thousand node expansions — milliseconds.
2005+ — bigger pattern databases for bigger puzzles
The same technique scales to the 24 puzzle (5×5) and beyond. A 5+5+5+9 partition for the 24 puzzle is about 4 GB. With it, any random 24 puzzle solves in seconds.
The 35 puzzle (6×6) is at the edge of what's tractable. The hardest 6×6 instances are still open research as of 2026.
2010s+ — neural network heuristics
Neural networks have been trained to predict the Manhattan-distance-like quantity for sliding puzzles, sometimes producing tighter heuristics than hand-engineered ones. The catch: NN heuristics are usually not provably admissible, so the solvers built on them give probably-optimal rather than guaranteed-optimal answers.
For research papers, this is interesting. For shipping software where optimality matters (difficulty calibration in games), classical pattern databases remain the right tool.
Why this history matters
Every wave of slide-puzzle algorithm research was driven by the same pressure: the puzzle is small enough that algorithms can be benchmarked, big enough that bad algorithms time out. The 15 puzzle has been the testbed for general advances in heuristic search — A*, IDA*, pattern databases — that now power route planning, theorem proving, and many other domains.
When you solve a 15 puzzle in an app using a hint button, you are using algorithms that were developed for exactly this game and then generalised everywhere else.
A summary table
| Year | Algorithm | Time to solve hard 15 puzzle | Memory | What enabled it |
|---|---|---|---|---|
| 1960s | BFS | Doesn't finish | Huge | — |
| 1968 | A* + Manhattan | Minutes | Hundreds of MB | Heuristic search |
| 1985 | IDA* + Manhattan | Seconds | KB | Iterative deepening |
| 1996 | IDA* + walking distance | < 1 sec | + 500 KB precompute | Better heuristic |
| 2002 | IDA* + 7+8 pattern DB | Milliseconds | + 1 GB precompute | Subset enumeration |
Each line is a real qualitative leap, not a marginal improvement. The history of solving the 15 puzzle is also the history of modern heuristic search.