Slide the numbered tiles into order. Everybody has met this puzzle, usually in plastic, usually on a train.
What almost nobody is told is that half of all possible scrambles cannot be solved — not by you, not by anyone, not with unlimited time. And you cannot tell which by looking at them.
How to play the 15 puzzle
Tap any tile in line with the gap and it slides in. Tap one further along the same row or column and the whole row slides at once, exactly as it would under your finger. Green tiles are already home.
The panel under the board is the part that matters. It counts the arrangement after every move and tells you whether the thing in front of you can come out — and shows the arithmetic that decides it.
Is my sliding puzzle solvable?
Count the inversions: read the tiles in order, row by row, ignoring the gap, and count every pair that appears the wrong way round.
Then:
- Odd number of columns (3×3, 5×5) — solvable if the inversion count is even.
- Even number of columns (4×4) — add the row the gap is in, counted from the bottom starting at 1. The total has to be odd.
That second line is where most explanations go wrong. Some count the row from the top, some forget the board width matters at all, and both mistakes give you the right answer exactly half the time — which is indistinguishable from working.
We did not want to be one of those pages, so we checked. For the 3×3 there are only 362,880 arrangements, so every one can be tested: we walked the puzzle outwards from the solved board to find everything reachable, then compared the rule against that list. It agreed on all 362,880.
Why half of them are impossible
Every slide changes the inversion count and moves the gap. It turns out those two changes always cancel out in one particular combination — slide a tile sideways and the inversion count does not change at all; slide one vertically and it changes by an odd number, but the gap also changes row. The combined parity is untouched.
A quantity the rules cannot change is called an invariant, and this is the tidiest one in recreational mathematics. The solved board has one value of it. Every arrangement with the other value is in a separate world you can never slide into — 181,440 on one side and 181,440 on the other, for the 3×3.
There is a button on this page that deals a deliberately impossible scramble, and another that swaps two tiles. Press the second one and watch the verdict flip while nothing else changes. That is the whole proof, in one click.
The $1,000 prize that was never in danger
In the 1880s Sam Loyd offered a thousand dollars to anyone who could solve a board that was complete except for the 14 and the 15 being the wrong way round. It drove people to distraction. It was also perfectly safe: one swap gives one inversion, the gap sits in row 1 from the bottom, and 1 + 1 = 2 is even — the wrong side of the line on a four-wide board.
Loyd also claimed for the rest of his life that he had invented the puzzle. He had not. It was Noyes Palmer Chapman, a postmaster in New York state, around 1874; the claim went unchallenged for over a century until Slocum and Sonneveld traced the history in 2006. What Loyd invented was the impossible version, and the prize that made it famous.
How many moves can the 15 puzzle take?
For the 3×3 we know exactly, because we counted. The hardest arrangements need 31 moves, and there are only two of them. The commonest distance is 24 moves. And almost nothing is nearly solved: just 51 of the 181,440 are within five moves.
That last number explains why the puzzle feels the way it does. A random scramble is not somewhere near the answer — it is out in the fat middle of the distribution, two dozen moves away, and there is no shortcut that finds them.
Why nobody has solved the 5×5
The 3×3 has 362,880 arrangements and we walked all of them in a few seconds. The 4×4 has 20,922,789,888,000, which is past what a browser tab can enumerate — the answer for the hardest board, 80 moves, took a dedicated computation and was settled in 2010. That figure is not ours and we have not repeated it.
The 5×5 has more than fifteen septillion. Nobody knows its worst case, and on current hardware nobody is going to.
Which is the quiet pleasure of this puzzle: the rule that tells you whether a board can be solved takes a few seconds with a pencil and works at any size, while actually solving one gets impossible almost immediately. Knowing that something is possible and knowing how are very different problems, and the 15 puzzle keeps them in the same box.
If you like a puzzle whose answer is fixed before you start, the Towers of Hanoi is the other one; and Knight's Tour is the one where you can see the rule working while you play.
