In 1880, the American puzzle-maker Sam Loyd announced a $1000 prize for anyone who could solve a specific 15 puzzle: the standard 1-through-15 arrangement with 14 and 15 swapped. The puzzle craze was already sweeping America and Europe; Loyd's stunt added rocket fuel. Thousands tried. Nobody won.
There was a reason nobody won. Loyd's board was provably unsolvable, and the proof is elementary enough to fit on one page. This article is that page.
The claim
Exactly half of all 16!/2 ≈ 10,461,394,944,000 ways to arrange fifteen tiles and a blank on a 4×4 board can be solved into the standard goal. The other half can not be solved. Loyd's "14 and 15 swapped" sits in the unsolvable half.
This generalises. On every N×N slide puzzle, half of all arrangements are unsolvable. The 3×3 8 puzzle has 9!/2 = 181,440 solvable boards out of 362,880 total; the 24 puzzle, 35 puzzle, and so on follow the same rule.
Inversions
The proof needs one definition. Read the tiles in reading order — left to right across row 1, then row 2, then row 3, then row 4 — and ignore the blank. You get a sequence of fifteen numbers.
An inversion is a pair (a, b) where a comes earlier in the sequence than b, but a > b. Count every such pair across the whole sequence. That count is the inversion number of the board.
Example: the goal state 1,2,3,…,15 has zero inversions. Loyd's "14 and 15 swapped" has the sequence 1,2,3,…,13,15,14, which has exactly one inversion (the pair 15,14).
The key lemma: a slide changes parity in a controlled way
What happens to the inversion count when you make a legal move?
-
Horizontal slides (a tile moves left or right by one cell): the moved tile changes its position in the reading-order sequence by one slot. Its relative order with every other tile in the sequence stays exactly the same — because horizontal motion does not change which row the tile is in or which tiles precede or follow it in row-order. The inversion count is unchanged.
-
Vertical slides (a tile moves up or down by one cell): the moved tile jumps across three other tiles in the reading-order sequence — the three tiles in the row it leaves through or enters. Each of those three either flips from "after" to "before" or vice versa, which means each contributes either +1 or -1 to the inversion count. The sum of three ±1s is always odd. So the inversion count changes by an odd number.
In summary: a horizontal slide preserves the inversion count's parity (even or odd). A vertical slide flips it.
The blank's row also flips on vertical slides
Track the row of the blank, counting rows from the top. A horizontal slide leaves the blank in the same row. A vertical slide moves it up or down by one row, so the blank's row changes parity (even row ↔ odd row).
We now have two things that change together:
- Inversion-count parity flips ⇔ vertical slide.
- Blank-row parity flips ⇔ vertical slide.
Their sum is therefore invariant under every legal slide. We have found a conserved quantity.
The parity theorem
Define the invariant:
P = (inversion count) + (row number of the blank, counted from the bottom, starting at 1)
This is the conserved quantity. On every legal slide, P changes by an even number, so its parity (even or odd) never changes.
The goal state has zero inversions and the blank in row 1 from the bottom — so P = 1 (odd). Any board with P even is unreachable from the goal, and conversely the goal is unreachable from any such board.
That gives a clean solvability test for the 15 puzzle:
- Read the tiles in row-order, ignoring the blank.
- Count inversions.
- Count the blank's row from the bottom (1, 2, 3, or 4).
- Add. If the sum is odd, the board is solvable. If even, it is not.
Loyd's "14 and 15 swapped" has 1 inversion and the blank in row 1 from the bottom — sum 2, even, unsolvable.
What this looks like for other sizes
The N×N parity rule depends on whether N is even or odd. The general statement:
- N odd (3×3, 5×5, …): a board is solvable iff the inversion count is even. The blank's row does not matter, because the blank's row parity is determined by the inversion count's parity for symmetry reasons.
- N even (4×4, 6×6, …): a board is solvable iff (inversion count) + (blank's row from the bottom) is odd.
For a 3×3, the test is just "are there an even number of inversions?" That is simpler than the 4×4 version, and you can memorise it in a minute.
A nice consequence
Because exactly half of all arrangements are solvable, a random shuffle followed by checking the parity is faster than a random shuffle followed by trying to solve. Apps that need to guarantee solvable starting positions either:
- Pre-screen with the parity test and reshuffle on failure.
- Generate by walking backwards from the goal, applying random valid slides. This guarantees solvability by construction and is what most apps do, ours included.
If you ever play a slide puzzle and find it impossible no matter what you try, the app generated it badly — not your fault, and not a puzzle from the universe.
The Sam Loyd footnote
Loyd's $1000 prize is one of the better-documented practical jokes in puzzle history. The mathematician who proved unsolvability — independently — was either William Johnson and William Story (1879, American Journal of Mathematics) or Loyd himself, depending on whose account you trust. Loyd was a famously self-promoting figure who claimed several inventions that he did not invent; the 15 puzzle itself was invented by Noyes Chapman in 1874, six years before Loyd's prize stunt.
What Loyd actually contributed was the prize, the publicity, and the unsolvable variant — a useful contribution, if not the one he advertised.