Is Every 15 Puzzle Solvable? The Parity Rule, and How to Check Any Board
Short answer: No. Exactly half of all arrangements of a sliding puzzle can be solved and the other half never can, however long you try. To check a board, count the inversions (pairs of tiles in the wrong order): on a 3 × 3 or 5 × 5 board it is solvable when that number is even, and on the 4 × 4 board when the inversions plus the gap's row from the bottom make an odd number. William Johnson and William Story proved this in 1879, which is why nobody ever won Sam Loyd's famous prize for swapping back the 14 and 15. Our Sliding Puzzle only deals solvable boards.
If you have ever fought a cheap plastic 15 puzzle for an hour and ended with the last two tiles the wrong way round, it was probably not your fault. Somebody took the tiles out and put them back in a different order, and there is a 50% chance that made the puzzle impossible. This guide shows how to tell in under a minute, and why the rule works.
How many 15 puzzle positions can be solved?
Count every way to place the tiles and the empty square on the board, then halve it. We checked the halving by brute force on the 3 × 3 board: a search from the solved position reaches exactly 181,440 of the 362,880 arrangements, and the rule below picks out the same 181,440 with no exceptions.
| Board | All arrangements | Solvable | Hardest position |
|---|---|---|---|
| 3 × 3 (8 puzzle) | 362,880 | 181,440 | 31 moves (2 positions) |
| 4 × 4 (15 puzzle) | 20,922,789,888,000 | 10,461,394,944,000 | 80 moves (17 positions) |
| 5 × 5 (24 puzzle) | about 1.55 × 1025 | about 7.76 × 1024 | – |
A move here is one tile sliding one square. When we placed the 16 pieces of a 4 × 4 board at random 20,000 times, 50.3% of the boards were solvable, as the theory says.
How to check if a sliding puzzle is solvable
- Write the tiles in reading order, left to right and top to bottom, and leave out the gap.
- Count the inversions. For each tile, count how many smaller tiles come after it in the list, and add those counts up.
- Odd-width boards (3 × 3, 5 × 5): the puzzle is solvable if the total is even.
- Even-width boards (4 × 4): add the number of the row the gap is in, counting the bottom row as 1. The puzzle is solvable if this total is odd.
Two examples on the 3 × 3 board, gap in the bottom-right corner:
- 1 2 3 / 4 5 6 / 8 7 _: only the pair 8, 7 is out of order, so there is 1 inversion. Odd, so it cannot be solved.
- 8 6 7 / 2 5 4 / 3 _ 1: 24 inversions. Even, so it can be solved. It is also one of the two hardest positions of the 8 puzzle: the shortest solution takes 31 moves.
And Sam Loyd's 14-15 puzzle: the 15 tiles are in order except 15 before 14, which is 1 inversion, and the gap is in the bottom row, which adds 1. The total is 2, an even number, so the position is impossible.
Why the rule works: the proof in three steps
- Every move is a swap. Think of the gap as a sixteenth tile. Sliding a tile into the gap simply swaps the two. So any position you reach is the solved board with some number of swaps applied.
- The gap counts the swaps. Colour the board like a chessboard. Each move takes the gap to a square of the other colour, so it can only be back in its home corner after an even number of moves.
- Swaps have a parity that never changes. A given arrangement can be reached by many different sequences of swaps, but those sequences are either all even or all odd in length. This is a basic fact about permutations, the same one behind the "sign" of a determinant.
Put together: every position with the gap at home is an even number of swaps from the start. Exchanging only the 14 and 15 is one swap, so it is odd and out of reach. That is the half of the 1879 proof that rules positions out. The same paper also proved the other half: every arrangement on the right side of the line can actually be reached.
The inversion count is a shortcut for the same idea. On a 3 × 3 board, a sideways move does not change the reading order, and an up or down move makes one tile jump over 2 others, which changes the inversions by 0 or ±2, so their parity never moves. On a 4 × 4 board the jump is over 3 tiles, which flips the parity, but the gap also changes row, so inversions plus the gap's row keep the same parity. The solved board has 0 inversions and the gap in row 1, a total of 1: odd.
The 14-15 puzzle and the 1880 craze
The puzzle is usually credited to Noyes Palmer Chapman, a postmaster in Canastota, New York. Puzzles were on sale by December 1879, Chapman applied for a patent in February 1880 (it was refused), and that year the game became a craze in the United States. The proof came almost at once: Johnson and Story's "Notes on the '15' Puzzle" appeared in the American Journal of Mathematics in 1879.
From 1891 until his death in 1911, the puzzle writer Sam Loyd claimed he had invented it, which he had not, and he described a $1,000 prize for anyone who could swap the 14 and 15 back into order. As the parity argument shows, nobody could.
| Year | Event |
|---|---|
| 1879 | The puzzle is on sale in the United States; Johnson and Story publish the proof |
| 1880 | Chapman's patent application (refused); the puzzle becomes a craze |
| 1891 | Sam Loyd starts claiming he invented the puzzle |
| 1986 | Ratner and Warmuth show that finding the shortest solution on an n × n board is NP-hard |
| 1999 | Brüngger, Marzetta, Fukuda and Nievergelt prove the hardest 15 puzzle positions need 80 moves |
Solvable does not mean easy to solve fast
Deciding whether a board can be solved takes a minute with the rule above. Finding the shortest solution is a different problem: for the general n × n puzzle it is NP-hard, which means no fast method is known for big boards. That is why people solve the 15 puzzle with a fixed method (top row first, then the left column, then the smaller puzzle that is left) rather than the optimal route. The method in our Sliding Puzzle guide always works and uses more moves than the minimum.
What if your puzzle cannot be solved?
- Physical puzzle: take out any two tiles and swap them. One swap moves the board to the other half, so an impossible puzzle becomes solvable (and the other way round).
- Puzzle you are writing yourself: do not place the tiles at random. Start from the solved board and slide tiles, or shuffle at random and swap two tiles whenever the check says the board is impossible.
- Two tiles reversed at the end: with everything else in place and the gap home, this position is on the impossible side, and no move ever changes sides. So the board was impossible from the start; it was not a mistake on your part.
The parity rule in our Sliding Puzzle
Our Sliding Puzzle has three sizes: Easy is the 3 × 3 board, Medium the classic 4 × 4 and Hard 5 × 5. It never places tiles at random. It starts from the solved board and moves the gap at random, 40 steps per square (360 on Easy, 640 on Medium, 1,000 on Hard), so every board it deals is on the solvable side. We checked 60,000 of its boards against the rule and all of them passed.
The Moves counter counts every tile that slides, the same way the numbers above are counted, so you can compare yourself with the best possible. On 20,000 of our Easy boards the shortest solution averaged 22.0 moves (median 22, longest 30). If you like puzzles with a hidden mathematical rule, the Tower of Hanoi has one too (2n − 1 moves), and Sokoban is the sliding puzzle where a single wrong push can make a level unsolvable.
Frequently asked questions
Is every 15 puzzle solvable?
No. Of the 20,922,789,888,000 ways to place the 15 tiles and the gap on a 4 by 4 board, exactly half can be solved and half cannot. A puzzle shuffled by sliding tiles is always solvable; one put together by hand, with tiles taken out and pressed back in, is solvable only half the time.
How do you know if a sliding puzzle is solvable?
Read the tiles row by row, ignoring the gap, and count the inversions: pairs where a bigger number comes before a smaller one. On a 3 by 3 or 5 by 5 board the puzzle is solvable when that count is even. On a 4 by 4 board add the row of the gap counted from the bottom (bottom row = 1): it is solvable when the total is odd.
Why can't you swap the 14 and 15 in the 15 puzzle?
Every slide swaps the gap with one tile, and the gap can only return to its corner after an even number of slides. So any arrangement you can reach with the gap back in the corner is an even number of swaps away from the start. Swapping only the 14 and 15 is a single swap, an odd number, so no sequence of slides can produce it.
What is the most moves a 15 puzzle can need?
80 single-tile moves. The hardest positions were proved to need 80 moves by Brüngger, Marzetta, Fukuda and Nievergelt in 1999, and Richard Korf later counted 17 positions at that distance. On the 3 by 3 board the maximum is 31 moves, and only two positions need that many.
Who proved that half of the 15 puzzle positions are impossible?
William Woolsey Johnson and William Edward Story, in "Notes on the '15' Puzzle", published in the American Journal of Mathematics in 1879. The paper showed both halves of the answer: half of the positions can never be solved, and every position in the other half can.
