The Fifteen Puzzle and Its Parity Invariant

After reading this you will be able to tell, just by inspecting a scrambled 15-puzzle, whether it can ever be solved, and you will understand the parity argument that proves half of all arrangements never can.

What the puzzle is, and the prize nobody won

The 15-puzzle is a 4 by 4 grid holding 15 numbered tiles and one empty square. A legal move slides a tile that borders the blank into the blank's spot. Your goal is the sorted board: 1 through 15 in reading order, with the blank in the bottom-right corner.

In 1880 a craze swept the United States. Sam Loyd, a famous puzzle-maker, offered a large cash prize to anyone who could take a board sorted except for tiles 14 and 15 being swapped, and slide it into perfect order. Nobody ever collected. The reason is not that the puzzle is hard. It is that the task is mathematically impossible. No sequence of legal slides, however long, can turn the 14-15 swap into the sorted board.

The proof rests on a quantity that never changes as you play. Mathematicians call such a quantity an invariant. Once you can compute it, you can look at any board and settle its fate in a few seconds.

Permutations and the sign of a swap

Read the 16 squares in order, left to right, top to bottom, and write down what sits in each. Ignore the blank for a moment and treat the 15 tiles as a permutation of the numbers 1 to 15. Any permutation can be built by swapping two items at a time. The number of swaps you use is not fixed, but its evenness is. A permutation is either always reachable by an even number of swaps or always by an odd number, never both.

Call the count of swaps an inversion-based measure. An inversion is any pair of tiles that appears in the wrong relative order. Count, for every tile, how many smaller-numbered tiles sit somewhere after it in reading order. Sum those counts. That total, written N, has the same evenness as the number of swaps needed to sort the board.

\text{sign}(\pi) = (-1)^{N}

Here \pi is the permutation of the tiles and N is the total inversion count. If N is even the sign is +1; if odd it is -1. The sorted board has N = 0, which is even, so its sign is +1.

Why one slide never changes the invariant

Watch what a single legal move does. A horizontal slide moves a tile left or right into the blank. In reading order, that tile and the blank simply trade neighboring positions. The relative order of every real tile is unchanged, so N does not move at all.

A vertical slide is the interesting case. Moving a tile up or down into the blank jumps it past exactly 3 other tiles in reading order (the 3 tiles that lie between the two squares on the same row-major line). Jumping past 3 tiles changes the inversion count by an odd amount: \pm 1 or \pm 3. So a vertical move flips the parity of N.

But a vertical move also changes the blank's row by 1. Track the blank's row distance from its home row (the bottom row). That distance also flips parity on every vertical move and stays fixed on every horizontal move. The two effects march in lockstep. Add them together and the sum never changes evenness.

P = N + r \pmod 2

Here N is the inversion count and r is the blank's row distance from the bottom row (0 if the blank is already on the bottom row, up to 3 if it is on the top row). The quantity P is even for every solvable board and stays even after any legal move. The sorted target has N = 0 and r = 0, so P = 0, which is even. Any board with P odd can never reach it.

This is why the scramble in the tool only ever uses legal moves. Starting from the solved board and sliding at random can only produce boards with P even, which are exactly the solvable ones. You will never be handed an impossible board by accident.

Reproducing Loyd's impossible board

The 14-15 swap has odd parity

Take the sorted board and swap tiles 14 and 15. The blank is still in the bottom-right corner. Compute the invariant.

Read the board in order: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14, then blank. Every tile is in its home spot except that 15 comes before 14.
Count inversions. Only one pair is out of order: 15 sits before the smaller 14. So N = 1.
Find the blank's row distance. The blank is on the bottom row, its home row, so r = 0.
Combine: P = N + r = 1 + 0 = 1, which is odd.

The solved board has P = 0, even. This board has P = 1, odd. They live in different worlds. No slide can cross between them, so the prize was safe from the start.

The two forever-separate worlds

The 16 squares can be arranged in 16! \approx 2.09 \times 10^{13} ways, about 20.9 trillion. The invariant P splits them cleanly into two equal halves: those with P even and those with P odd. Exactly one half, roughly 16!/2 \approx 1.05 \times 10^{13} arrangements, can reach the sorted board. The other half can never reach it and never mix with the first.

The invariant partitions all arrangements into two equal groups of about 10.46 trillion each. Legal slides keep you inside one group forever.

The widget below lets you build a small version of this idea by hand. Move the blank and watch N and r change while P holds steady.

Common mistakes when judging solvability

The single most common error is counting inversions but forgetting the blank's row. On a 4 by 4 board (an even width), inversions alone do not decide solvability. You must add r. A board with 5 inversions and the blank two rows up from home has P = 5 + 2 = 7, odd, so it is impossible, even though 5 inversions alone might tempt you to guess otherwise.

The exact rule depends on the grid's width. For odd-width boards, solvability is decided by inversion count alone. For even-width boards like the 4 by 4, you must combine inversions with the blank's row. Do not carry a rule from a 3-wide board over to a 4-wide one.

A second mistake is counting inversions including the blank as if it were a tile numbered 16. Leave the blank out of the inversion count entirely and account for it only through r. A third mistake is reading the board column-major instead of row-major. The inversion count must use reading order, left to right then top to bottom, or the whole argument breaks.

How this connects to other invariant puzzles

The parity trick is one instance of a wider idea: find a quantity a system cannot change, and you learn which states it can and cannot reach. The Tower of Hanoi hides a similar structure in its move count, and Nim and Grundy numbers decide every game by a fixed XOR value. Backtracking puzzles like the N-Queens visualizer and the Knight's Tour instead search a space with no such shortcut. For a coloring problem whose answer is guaranteed but whose method is a puzzle, see the Four Color Map. If you enjoy watching order emerge from simple rules, try Langton's Ant or Conway's Game of Life.

Frequently asked questions

How do I know if a scrambled 15-puzzle is solvable?

Count the inversions N among the 15 tiles in reading order, then add the blank's row distance from the bottom row, r. If N + r is even the board is solvable. If it is odd it is impossible.

Why could nobody win Sam Loyd's prize?

The 14-15 swap has one inversion and the blank on its home row, giving P = 1, odd. The solved board has P = 0, even. Legal slides never change the parity of P, so the two boards are unreachable from each other.

Are exactly half of all positions impossible?

Yes. Of the 16! \approx 2.09 \times 10^{13} arrangements, exactly half have P even (solvable) and half have P odd (impossible), about 10.46 trillion in each class.

Does the scramble ever give me an unsolvable board?

No. The tool scrambles by making random legal moves from the solved board. Since legal moves preserve P, every scrambled board keeps P = 0 and stays solvable.

What is the fewest moves needed to solve the worst board?

The hardest solvable 15-puzzle positions require 80 single-tile slides. Most scrambles need far fewer, but no solvable board ever needs more than 80.

Try it yourself in the tool