The 15-puzzle — fifteen numbered tiles in a 4×4 grid with one empty space, slide them into order — seems like it should always be solvable with enough patience. Slide the tiles around, try different sequences, eventually everything lines up. This intuition is completely wrong, and the mathematical reason why teaches something profound about puzzles in general: before you spend time solving something, it's worth confirming that a solution actually exists.
The 1880 Craze and the Impossible Prize
When Sam Loyd popularized a version of the 15-puzzle in 1880, he offered a $1,000 prize for solving a specific configuration: the standard solved arrangement except with the 14 and 15 tiles swapped. Thousands of people tried. Nobody won. Not because they weren't clever enough — but because the configuration is mathematically impossible to solve from the standard starting arrangement. Loyd knew this. The prize was never at risk.
The reason comes down to a property called parity. In the 15-puzzle, every slide of a tile is equivalent to a transposition — a swap of two elements in the sequence of numbered positions. Mathematicians proved that any sequence of moves from the solved state produces a position reachable by an even number of transpositions. Loyd's challenge required an odd number. You cannot get there from here, no matter how many moves you make.
What Parity Actually Means
Think of the 15 tiles as a sequence of numbers from 1 to 15, with the empty space treated as position 16. When you slide a tile into the empty space, you're swapping that tile's position with the blank's position in the sequence. Each swap changes the parity of the arrangement — even becomes odd, odd becomes even.
The solved state has even parity (zero transpositions from the identity sequence). Every legal move toggles the parity. So after any odd number of moves, the arrangement has odd parity — and after any even number of moves, it has even parity. A position that requires an odd number of transpositions from the solved state (like Loyd's 14-15 swap) can only ever be reached by an odd number of moves. Since the solved state has even parity, you'll always arrive at odd-parity states on odd moves and even-parity states on even moves — never reaching an odd-parity target on the way back to even-parity solved.
How to Check Any Position
You can determine whether any 15-puzzle position is solvable before attempting it. Count the number of inversions in the tile sequence — pairs of tiles where a higher-numbered tile appears before a lower-numbered one in the reading order. Add to this count the row number of the blank space from the bottom (1-indexed). If this sum is even, the position is solvable. If it's odd, it's not. This calculation takes about two minutes for any position and will save you hours of fruitless sliding.
The Broader Lesson for Puzzle Solvers
The 15-puzzle teaches a principle that applies across many puzzle types: solvability is not guaranteed, and verifying it before investing effort is a legitimate strategy. In Sudoku, a puzzle with multiple solutions or no solution is broken — knowing this lets you stop trying to logically resolve ambiguous cells. In logic grid puzzles, missing constraints can leave assignments genuinely undetermined. In sliding tile puzzles, parity determines the entire feasibility of a starting position.
The puzzle solver's habit of asking "is this solvable?" before "how do I solve it?" saves enormous amounts of time and frustration. It's not defeatism — it's mathematical hygiene. And in the case of the 15-puzzle, it would have saved a thousand people in 1880 from chasing a prize that was never theirs to win.