Math & theory

15 Puzzle Parity — The Proof of Why Some Configurations Are Unsolvable

Half of all 15-puzzle arrangements are unsolvable. Sam Loyd offered $1000 in 1880 for the impossible one. Here is the authoritative maths: permutation parity, inversion counts, why the blank's row matters, and worked checks for the famous 14–15-swapped board.

Updated 2026-08-25 10 min read

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?

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:

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:

  1. Read the tiles in row-order, ignoring the blank.
  2. Count inversions.
  3. Count the blank's row from the bottom (1, 2, 3, or 4).
  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.

Worked check: is this exact configuration solvable?

The two boards people ask about most are the same board written two ways. Both are the classic impossible one.

"14 and 15 swapped" — the goal with only the last two numbered tiles exchanged:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 15 14  _

Reading order (blank ignored): 1,2,…,13,15,14. The only out-of-order pair is (15,14) → 1 inversion. The blank sits in the bottom row → row 1 from the bottom. Sum = 1 + 1 = 2, even → unsolvable. This is Loyd's board, and the query "15 puzzle 13 15 14 blank unsolvable" describes the very same arrangement.

A solvable look-alike — same corner disturbed, but this one can be finished. Rotate the last three tiles in a cycle (13 → 15 → 14 → 13) instead of swapping just two:

 1  2  3  4
 5  6  7  8
 9 10 11 12
15 13 14  _

Reading order: 1,…,12,15,13,14. Inversions: (15,13) and (15,14) → 2 inversions. The blank is in the bottom row → row 1 from the bottom. Sum = 2 + 1 = 3, odd → solvable. The difference from Loyd's board is one inversion: a single swap (14↔15) is an odd permutation and lands in the unsolvable class, while a three-tile cycle is an even permutation and stays solvable. That is the whole theorem in one comparison.

The takeaway for any board you are staring at: count inversions, add the blank's row from the bottom, check odd. No solver required to know whether a solver could ever finish.

What this looks like for other sizes

The N×N parity rule depends on whether N is even or odd. The general statement:

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:

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 knight cousin: Guarini's puzzle and its parity proof

People searching for a "knight puzzle unsolvable configuration parity proof" are usually circling one of two closely related ideas, and both are worth separating from the sliding-tile case.

Colour parity on a chessboard. A knight always moves from a light square to a dark square and back — every knight move flips the colour. That single fact is a parity invariant, and it settles a whole family of "is this reachable?" questions the same way inversions settle the 15 puzzle. If a target position asks a knight to end on a colour that its move count forbids, no sequence of moves can get there. A closed knight's tour, for instance, must alternate colours perfectly, which is why it is impossible on any board with an odd number of squares.

Guarini's puzzle (1512). The oldest knight-swap puzzle places two white knights and two black knights on the corners of a 3×3 board and asks you to exchange them. Its solvability is proved not by inversions but by unrolling the move graph: draw a node for each of the eight usable squares (the centre is unreachable by any knight) and connect squares a knight move apart. That graph turns out to be a single 8-cycle. Once you see the cycle, the knights are just four beads on a ring that can only slide around it, so their cyclic order is an invariant — you can rotate them but never reorder them. The requested swap preserves that cyclic order, so it is reachable; a swap that reversed it would not be.

The through-line with the 15 puzzle is the method, not the mechanism: find a quantity the legal moves cannot change — inversion-plus-blank-row parity for sliding tiles, square colour or cyclic position for knights — and every "impossible" configuration is the one that would have to change it. Different puzzle, same style of proof.

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.

Frequently asked questions

Is the 15 puzzle with 14 and 15 swapped solvable? No. That board has exactly one inversion and the blank in the bottom row, so the invariant sums to 2 (even), which is the unsolvable class. It is Sam Loyd's famous impossible board, and the "13 15 14 blank" arrangement people ask about is the same position.

How do I check whether a specific 15 puzzle configuration is solvable? Read the tiles in row order and ignore the blank, count the inversions (pairs where a larger number comes before a smaller one), then add the blank's row counted from the bottom (1–4). If the total is odd, the board is solvable; if even, it is not.

What fraction of 15 puzzle positions are unsolvable? Exactly half. Of the 16!/2 reachable-or-not arrangements, half can be solved into the standard goal and half cannot, and this even split holds for every N×N sliding puzzle.

Does the parity rule work for the 8 puzzle (3×3)? Yes, and it is simpler. For odd board widths (3×3, 5×5, …) a board is solvable if and only if the inversion count is even — the blank's row does not enter the test.

What is the knight puzzle parity proof? It is a different invariant for a different puzzle. A knight always changes square colour on each move, so colour parity limits which positions are reachable; the classic knight-swap puzzle (Guarini's) is solved by showing its move graph is a single cycle, which fixes the knights' cyclic order. Same proof style as the 15 puzzle, different conserved quantity.

References