There are two ways to solve a 15 puzzle. One is the way every player eventually figures out — solve the top row, then the left column, recurse. The other is the way computers do it: a heuristic search through millions of states, guided by a clever lower-bound estimate of how many moves remain.
This guide covers both, in roughly the order most people learn them.
The 15 puzzle, in one paragraph
A 4×4 board, fifteen numbered tiles, one empty square. You slide tiles into the gap until the numbers are in order — 1 through 15, with the empty in the bottom-right corner. The board was invented by Noyes Chapman in 1874 and became an international craze in the 1880s after Sam Loyd offered $1000 for solving an unsolvable variant. It is the same puzzle, fundamentally, as the 8 puzzle — just one row and one column larger.
Solving it by hand: the row-and-column method
The technique that every human eventually finds is this:
- Solve row 1. Place 1 and 2. Then place 3 in the top-right corner. The "L"-shaped manoeuvre — bring 4 into position 3, slide 3 under, then rotate the pair into the corner — is the trick that makes corners possible.
- Solve column 1. Place 5, then 9, then 13 in the bottom-left corner, using the same L-shaped corner trick.
- Recurse. What is left is a 3×3 subpuzzle (with the bottom-right column and row), which is just an 8 puzzle you already know how to solve.
A confident player solves a 15 puzzle in 3–5 minutes by hand. A new player might take 20 minutes the first time and a third of that by the third time.
The same method scales to 5×5 and 6×6. The recursion always lands on a 3×3 endgame.
Optimal solver: A* with Manhattan distance
A computer can do much better than the row-and-column method. Specifically: it can find the shortest solution, which is rarely what a human plays.
The mathematical fact: the median 15 puzzle requires about 52 single-tile moves when solved optimally. The worst case is 80. The row-and-column method typically uses 100–150 moves on the same board.
To find an optimal solution, A* search treats each board state as a node, each move as an edge, and asks: how many moves to the goal, at least? The minimum number of moves remaining is impossible to compute exactly without solving the puzzle, but a good lower bound makes A* fast.
The classic lower bound is Manhattan distance:
For each tile, sum the row distance plus the column distance from its current position to its goal position. (Ignore the blank.)
Manhattan distance is admissible — it never overestimates the true distance, because every tile must travel at least that far. With A* and Manhattan distance, the 8 puzzle is solved in microseconds and the 15 puzzle in seconds.
IDA*: the memory-friendly cousin
A* needs to remember every state it has explored. For 15 puzzles, that runs into hundreds of megabytes of RAM for the hardest boards. Iterative-deepening A (IDA)** trades memory for time by doing depth-limited DFS with the heuristic, raising the depth limit each round.
IDA* is what every reference solver actually uses for the 15 puzzle. Richard Korf's 1985 paper introduced it precisely to solve 15 puzzles to optimality on early-1980s hardware.
Beyond Manhattan: walking distance and pattern databases
Manhattan distance is fast but loose. It assumes tiles can pass through each other freely. They cannot — two tiles in the same row must take turns, which costs extra moves.
Walking distance counts those extra moves. Pre-compute, for each pair of rows, the minimum number of "row swaps" required to permute the tiles into the correct rows. Do the same for columns. Add the two. The result is provably tighter than Manhattan distance — typically about 25% larger, which means A*/IDA* explores 25%× fewer nodes.
The strongest known heuristic for the 15 puzzle is the additive disjoint pattern database:
- Partition the tiles into disjoint groups (a common split is 5-5-5 plus the blank).
- For each group, pre-compute, for every possible arrangement of that group's tiles on the board, the minimum number of moves to put those tiles into their goal positions, ignoring all other tiles.
- At search time, add the lookups for each group.
A 7+8 partition for the 15 puzzle takes about 1 GB to store but lets IDA* solve any 15 puzzle in milliseconds. For the 24 puzzle (5×5), pattern databases are essentially the only practical approach.
Why hand solving is usually faster (for one puzzle)
A short reality check: writing an A* implementation, choosing a heuristic, and waiting for it to run takes longer than picking up a single 15 puzzle and solving it by hand. The mathematics is interesting; the practicality is that a person who knows the row-and-column method can solve any single board in five minutes flat.
The reason solvers matter is the aggregate: research papers that compare heuristics across thousands of random instances, AI textbooks that use the 15 puzzle as a benchmark, and apps that need to generate puzzles guaranteed to be solvable in roughly N moves for difficulty calibration.
Suggested reading order
If you came to this page hoping to write a solver, start with A*/Manhattan, watch it solve a few 8 puzzles, then port to IDA* for 15 puzzles. After that, walking distance is a 100-line addition that doubles your speed. Pattern databases are a weekend project that buys you another order of magnitude.
If you came here hoping to play a 15 puzzle, learn the row-and-column method first, then read why some boards are unsolvable, then come back here for the theory.