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
The 15-puzzle swept North America and Europe as a craze in 1880. The famous puzzle writer Sam Loyd later claimed he had invented it and offered a $1,000 prize to anyone who could solve it starting from the finished arrangement with only the 14 and 15 tiles swapped. Puzzle historians Jerry Slocum and Dic Sonneveld have since shown that Loyd didn't invent it (credit goes to a New York postmaster, Noyes Chapman) and that there's no evidence the prize was offered at the time. The challenge itself, though, is real, and nobody could ever have won it: that position is mathematically impossible to solve.
The reason comes down to a property called parity. Every time you slide a tile, you swap it with the blank space, so each move is one transposition (a swap of two items) among the sixteen squares. Loyd's challenge needs an odd number of swaps, and as the next section shows, any sequence of legal moves that brings the blank back home uses an even number. You cannot get there from here, no matter how many moves you make.
What Parity Actually Means
Think of the 15 tiles plus the blank as sixteen items in the sixteen squares. Every move swaps the blank with a neighbouring tile, and each swap flips the arrangement's parity: even becomes odd, odd becomes even.
Now watch the blank. For it to end up back in its home corner, it has to move left exactly as many times as it moves right, and up exactly as many times as down. That makes the total number of moves even, so the arrangement's parity is back where it started: even. Loyd's position has the blank at home but the 14 and 15 swapped, which is one swap away from solved, an odd arrangement. An even number of moves can never produce it.
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 odd, the position is solvable. If it's even, it's not. (Check it on the finished puzzle: zero inversions plus the blank on row 1 gives 1, which is odd, so it's solvable, as it should be.) 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.