15 Puzzle Solver

The classic 15-puzzle, solved optimally

The 15-puzzle is the original sliding puzzle: a 4x4 frame with tiles numbered 1 to 15 and one empty square. Slide the tiles until they read 1 to 15 in order, with the gap in the bottom-right corner. This 15 puzzle solver finds the fewest moves for any position you enter and plays them back one tile at a time. For other sizes, use the main sliding puzzle solver.

Press Load Sam Loyd's 14-15 puzzle above to see the most famous impossible position in history.

A short history

The puzzle was invented in the 1870s by Noyes Chapman, a postmaster in upstate New York, and became a worldwide craze in 1880. People played it in offices, on trains and in parliament. Puzzle maker Sam Loyd later claimed he had invented it and offered a $1,000 prize to anyone who could solve a board with only the 14 and 15 tiles swapped. Nobody ever collected, because that position can't be solved. Mathematicians had already proved in 1879 that exactly half of all 15-puzzle arrangements are impossible.

Why some 15 puzzles are unsolvable

Every slide keeps a hidden quantity called parity the same, so you can tell whether a position can be solved without searching. For a 4x4 board with the goal gap in the bottom-right:

1. Read the tiles row by row, ignoring the gap, and count the inversions, every pair where a larger number comes before a smaller one.
2. Find the row of the gap, counting from the bottom (bottom row = 1).
3. Add the two numbers. If the sum is odd, the puzzle is solvable. If it's even, it isn't.

Check the solved board: 0 inversions plus the gap in row 1 gives 1, which is odd, so it's solvable. Swap 14 and 15 and you get 1 inversion plus row 1, which is 2. Even, so Loyd's puzzle is impossible. On boards with an odd width, like 3x3 or 5x5, the gap's row doesn't matter. The puzzle is solvable when the inversion count is even.

Swapping any two tiles flips the parity. That's why the solver's Fix it button only has to swap one pair of neighbors to turn an impossible board into a solvable one.

How the solver finds the fewest moves

There are 16!/2, more than 10 trillion, solvable 15-puzzle positions, far too many to store. Instead the solver uses IDA*, a search that explores move sequences in order of length and never misses a shorter one. A pattern database tells it the least number of moves each group of tiles still needs. Together they find the optimal solution for almost any position within a second or two, right in your browser. The very hardest positions take much longer. An 80-move board takes about one to two minutes on a desktop computer and several minutes — ten minutes or more on slower phones, and the solver shows its progress while it works. Times vary with the device, temperature and other activity.

Moves are counted as single-tile slides (one tile moving into the empty space), the standard way optimal solutions are measured:

• Most moves any position needs: 80 (only 17 positions need that many)
• Average position: about 53 moves
• Typical hand solution with the row-by-row method: 100 to 150 moves

Using a picture instead of numbers?

For 4x4 picture puzzles, use the 4x4 Sliding Puzzle Solver. It lets you upload your image and shows which number each piece stands for.