How to use the 15 puzzle solver
Type the number of each tile where it sits on your board, row by row, and leave the gap empty. Then press Solve. The 15 puzzle solver checks the board, searches for the shortest solution and shows it as a list of tiles to slide. Press Play to watch it or step through with the arrows. Switch to Slide tiles to play the puzzle yourself by tapping tiles next to the gap. Scramble gives you a random solvable board.
For the smaller 3 x 3 version, choose 8 puzzle. You can also paste a board as text, for example 5 1 2 4 9 6 3 8 13 10 7 11 0 14 15 12, with 0 or _ for the gap.
Can every board be solved?
No: exactly half of all arrangements cannot be solved, and the solver tells you before searching. The test uses inversions: read the tiles row by row and count the pairs where a larger number comes before a smaller one.
- 8 puzzle (3 x 3): solvable exactly when the number of inversions is even. A slide along a row changes nothing; a slide up or down jumps a tile over two others, changing the count by 0 or 2.
- 15 puzzle (4 x 4): a vertical slide jumps a tile over three others, so the inversion count changes by an odd number while the gap moves one row. Inversions plus the gap's row counted from the bottom therefore always keeps its parity, and on the solved board it is odd. A board where it is even can never be solved.
The famous example is a solved board with 14 and 15 swapped: one inversion, gap on the bottom row, total 2, even, so it is impossible.
How the solver finds the shortest solution
The solver uses IDA* (iterative deepening A*), a search that tries all solutions up to a length limit and raises the limit until one works. It is guided by an estimate of how many moves are still needed that never overestimates, which is what makes the first solution found a shortest one.
- For the 8 puzzle the estimate is the Manhattan distance (how far each tile is from home, in rows plus columns) plus a correction for tiles that block each other in their own row or column (linear conflicts). Every 8 puzzle is solved optimally in a fraction of a second.
- For the 15 puzzle, easy boards are solved the same way; for harder ones the solver builds three pattern databases: exact move counts for every placement of tiles 1, 5, 6, 9, 10, 13, of tiles 7, 8, 11, 12, 14, 15 and of tiles 2, 3, 4. Added together, and checked on the board mirrored along its diagonal too, they give a much sharper estimate. Building them takes a second or two, inside your browser.
Most random 15 puzzles are solved optimally within a few seconds. The hardest positions need up to 80 moves and can take far longer, so the search has a 15-second budget. If it runs out, the solver switches to a fast method (first row, then first column, then the remaining 3 x 3 solved optimally) and labels that solution as not the shortest.
In testing, 8 puzzle results matched a full table of the exact distances of all 181,440 solvable positions, 15 puzzle results matched a second, independent search, and every solution was replayed tile by tile.
Worked example
The example board 5 1 2 4 / 9 6 3 8 / 13 10 7 11 / _ 14 15 12 is solved in 9 moves: slide 13, 9, 5, 1, 2, 3, 7, 11, 12. For the 8 puzzle, try 8 6 7 / 2 5 4 / 3 _ 1: it is one of only two 8 puzzle positions that need 31 moves, the most any 8 puzzle needs.
Tip for solving by hand
Solve the top row first, then the left column, and leave them in place: what is left is a smaller puzzle. Place the last two tiles of a row together by parking the last one under its spot and rotating both in.
Two more puzzles where the solver finds the fewest moves for you: Lights Out, where each press flips a cross of lights, and the Tower of Hanoi.
Solver tested . Found a problem? Tell us.
Questions
Why is my 15 puzzle unsolvable?
Half of all tile arrangements cannot be reached by sliding. If inversions plus the gap's row from the bottom is even, no sequence of slides solves the board. On a real puzzle this happens when two tiles were taken out and swapped. Swap any two tiles and it becomes solvable.
What is the most moves a 15 puzzle can need?
80 single-tile moves. Computer searches have shown that every solvable 15 puzzle position can be solved in 80 moves or fewer, and that some positions need all 80. For the 8 puzzle the maximum is 31.
Is the solution really the shortest?
When the result says proved optimal, yes: the search checked that no shorter solution exists. If the 15-second budget runs out on a very hard board, you get a fast solution instead, clearly labeled as not the shortest.
How do I count inversions?
Read the tiles row by row, ignoring the gap. For each tile, count the tiles after it that have a smaller number. Add all those counts together.
Does the solver send my board anywhere?
No. The search runs in your browser in a background thread; nothing is uploaded.