Half of all sliding puzzles cannot be solved

The claim, and why it matters

A four by four sliding puzzle has fifteen numbered tiles and one gap. Those pieces can be arranged in a very large number of ways, and exactly half of those arrangements can be reached from the finished board. The other half cannot be reached from it, which means they cannot reach it either.

This is not a curiosity. It is the reason we do not generate boards by shuffling the tiles, and it is the difference between a puzzle and a cruel joke. A player who cannot tell the difference will conclude they are bad at the puzzle.

Counting inversions

The test uses a quantity that never changes in a way that matters. Read the tiles in order — left to right, top to bottom, ignoring the gap — to get a sequence of numbers. An inversion is any pair of tiles that appear in the wrong relative order: a larger number before a smaller one.

Count every such pair in the whole board. On the finished board the tiles read 1 to 15 in order, so there are no inversions at all, which is even.

Now watch what a legal move does to that count:

• A horizontal slide changes nothing. Swapping a tile with the gap beside it does not change the tile's position in the reading order, so no pair changes places.
• A vertical slide moves a tile past exactly three others on a four-wide board, because it jumps a whole row in the reading order. Each of those three pairs may flip, so the inversion count changes by an odd amount — but the gap has also moved between rows.

Combine the two and the invariant appears: on a four-wide board, the inversion count plus the row number of the gap always keeps the same parity. Every legal move preserves it, so no sequence of moves can ever change it.

The test you can actually apply

For a four by four board, count the inversions and note which row the gap is in, counting from the bottom starting at one.

1. Gap in an odd row from the bottom. The board is solvable when the inversion count is even.
2. Gap in an even row from the bottom. The board is solvable when the inversion count is odd.

Apply it to the impossible board above. It differs from the finished board by one swap of adjacent tiles, which changes the inversion count by exactly one, from zero to one. The gap is in the same place. Parity has flipped, and no move can flip it back.

Odd-width boards are simpler. On a three by three, a vertical slide moves a tile past two others, so the inversion count changes by an even amount and the gap position drops out of the argument entirely. A three by three is solvable precisely when its inversion count is even.

The prize nobody could win

The puzzle became a craze in the 1880s, and the swapped-tile version became briefly famous when it was offered as a challenge with a cash prize for solving it. The prize was safe. The impossibility had been established in the mathematical literature before the challenge was made, which is presumably why it was offered.

The puzzle's origins are murkier than its mathematics. It is generally credited to Noyes Chapman in the 1870s, though the well-known puzzle writer Sam Loyd claimed invention for years afterwards and the claim is not supported by the evidence. The parity argument, by contrast, is not in dispute at all.

So we shuffle differently

Knowing the test, there are two honest ways to deal a board. You can randomise the tiles, run the parity check, and reject or repair anything unsolvable. Or you can start from the finished board and make a long run of legal moves.

We do the second, for a reason that has nothing to do with speed: a board built from legal moves comes with its own proof. Whatever position you are given, reversing the moves that produced it returns the board to solved. There is no check to get wrong and no edge case to miss.

It also means the shuffle length is a real difficulty dial. A short shuffle produces a board a few moves from done; a long one produces something that looks entirely random and still cannot be a dead end.

The same principle runs through the site. Lights Out boards are produced by pressing cells on a dark board rather than randomising the lights, for exactly the same reason — and there too, most random arrangements have no solution.