15 Puzzle Solver
How to use the 15 puzzle solver
Type the numbers as they sit on your puzzle, row by row, and leave the gap empty. Press Solve. Each move is the tile to slide and the direction it goes, and the board below follows along, with the next tile outlined. The goal is 1 to 15 in order with the gap in the bottom-right corner. The 3 by 3 version, the 8 puzzle, works the same way.
For the 15 puzzle you get a solution straight away, then the solver keeps looking until it has the shortest one there is and proves nothing shorter exists. Most boards take a second or two; a few of the hardest take longer, and the page tells you how far it has got.
Is my 15 puzzle solvable?
Exactly half of all the ways to arrange the tiles can be solved, and the solver tells you which half yours is in. Read the tiles row by row and count the inversions, the pairs where a bigger number comes before a smaller one. On a 4 by 4 board, add the row the gap is on, counting from the bottom. If the total is odd, it can be solved. On a 3 by 3 board, the inversions alone must be even.
The reason is that every slide changes those numbers in step, so the rule can never be broken by sliding. William Johnson and William Story proved it in 1879, during the craze for the puzzle. It is why the famous version with only 14 and 15 swapped can never be solved, and why a puzzle that has been taken apart and put back carelessly often cannot either: swapping any two tiles moves it to the other half.
How many moves does the 15 puzzle take?
Counting each tile slide as one move, no solvable 15 puzzle needs more than 80, and only a handful of positions need that many. Most random boards take between 50 and 60. The 8 puzzle never needs more than 31, and this page's tests check that by working out the distance of every one of its 181,440 positions.
Finding the shortest solution is a real search. The solver uses Richard Korf's IDA*, which tries ever longer solutions while ruling out any move that cannot lead home in time, guided by pattern databases: exact move counts for groups of tiles, worked out once when the page first solves. Before it went up it reproduced the published shortest lengths of Korf's own test boards.
How to solve the 15 puzzle by hand
Solve it in rings rather than all at once. Put 1, 2, 3 and 4 into the top row, bringing 3 and 4 in together because the last two of a row cannot be placed one at a time. Then do the second row the same way. That leaves a 2 by 4 strip at the bottom: solve it a column at a time from the left, 9 and 13 together, then 10 and 14, until only a 2 by 2 corner is left, which you turn round until it falls into place. It will not be the shortest way, but it always works.
More sliding puzzles
To play rather than solve, there is a new daily 15 puzzle every day. The Tower of Hanoi solver is the same kind of shortest-path problem with discs. In wood, our sliding puzzles include One Way or Another by Alexander Magyarics, where you first pack the tray, then have to slide a disc from one corner to the other. There are more solvers on the puzzle tools page.
Lights Out has the same twist, most boards being impossible: the Lights Out solver finds the fewest presses, or proves there are none.
Frequently Asked Questions
How do you know if a 15 puzzle is solvable?
Count the inversions, the pairs of tiles where a bigger number comes before a smaller one reading row by row, and add the row the gap is on counting from the bottom. If the total is odd, it can be solved. Exactly half of all arrangements can.
What is the minimum number of moves to solve a 15 puzzle?
It depends on the position. No solvable 15 puzzle needs more than 80 single-tile moves, and most random boards need between 50 and 60. The solver finds the exact minimum for yours.
Why can't the 14-15 puzzle be solved?
Swapping just the 14 and 15 changes the parity of the board, and no sequence of slides can change it back. It was proved in 1879 that exactly half of all arrangements are unreachable.
How do you solve a 15 puzzle step by step?
By hand: put the top row in place, then the second, then solve the bottom two rows a column at a time from the left, finishing with a 2 by 2 corner. For the shortest solution to a particular board, type it into the solver and follow the moves.
What is the 8 puzzle?
The 3 by 3 version of the 15 puzzle, with tiles 1 to 8 and one gap. No solvable position needs more than 31 moves. The solver handles it too.