Sam Loyd offered $1000 to anyone who could slide the tiles back into order. Nobody ever collected — and the reason is one bit of arithmetic that no move you make can ever flip.
research/fifteen-puzzle/verify.mjs (23/23), computed live from the board being drawn — re-enacted, not quoted; the music is a declared sonification of the same BFS and parity. Reproducible from a fresh checkout: bash research/fifteen-puzzle/film/build.sh.
In January 1880 a small wooden box of fifteen numbered tiles set the United States, and then Europe, briefly out of their minds. You slid the tiles one at a time through the single empty square, trying to put them in order. The puzzle-maker Sam Loyd sharpened the craze to a point: he displayed the tiles in order except for the last two — 14 and 15 swapped — and offered $1000 to the first person who could slide them straight, purely by legal moves.
The money was never paid. Not because nobody was clever enough — because the task is impossible, and Loyd almost certainly knew it. Worse than that: the impossibility isn't a quirk of his one setup. Of all the ways you could ever arrange these tiles, exactly half can never be reached by sliding, no matter how long you push them around. Loyd's box simply started in the wrong half. Here it is — try to fix it.
Stop thinking about tiles and think about the gap. Every legal move does exactly one thing: the gap trades places with a tile next to it. In the language of permutations, that is a single transposition — two items exchanged, nothing else. The whole puzzle is just a long chain of transpositions applied to the starting order.
And transpositions have a property they cannot shake. Mathematicians attach a sign to every arrangement: +1 if it takes an even number of swaps to reach from the solved order, −1 if odd. (This is well-defined — the count's parity never depends on how you swap.) Each move flips the sign, every time: even ⟷ odd. So the sign of the tile arrangement is a coin that turns over on every single move you make.
If the sign were the whole story, you could never get back to a solved board with the gap home — because returning the gap to its corner takes an even number of moves, and you'd need the sign to land where it started only on even move-counts. Loyd's swap is a single transposition away from solved: sign −1, odd. To undo it you'd need an odd number of moves — but any path that brings the gap home uses an even number. The parities can't be made to agree. That mismatch is the wall.
Here is the exact invariant, the thing every legal slide leaves untouched. Take the sign of the arrangement and combine it with where the gap is:
J = sign(arrangement) × (−1)(taxicab distance of the gap from home)
Why is J frozen? A slide flips the sign (one transposition) and moves the gap one step (changing its taxicab distance by exactly one, flipping that second factor too). Two flips multiply to no change. So whatever J was at the start, it stays — through one move or ten million. The solved board has J = +1. Therefore:
a board is solvable ⟺ J = +1
You can read this bit straight off any arrangement without sliding a single tile — and below, you can watch a live search confirm that the bit is never wrong. Set a board, and the oracle reads its J and gives a verdict instantly. Then press prove it by search: the program quietly builds the entire universe of boards you can reach from solved — all 181,440 of them — and checks whether yours is in it. The arithmetic and the brute-force search always agree.
The search isn't just a demo — it settles the claim independently of the parity argument. Run from the solved 3×3, it reaches 181,440 distinct boards and then stops, having found every move dead-ends back into the same set. That is exactly 9! / 2 — precisely half of the 362,880 arrangements three rows of tiles can take. The other half forms a second island the gap can never bridge to. (The full 15-puzzle is too vast to map this way — about 1013 boards — but the same parity bit cleaves it in two all the same: half reachable, half not.)
When the gap is back in its home corner, the reachable boards are exactly the arrangements with even sign — the mathematicians' alternating group, An, which is always precisely half of all permutations. One sharp consequence: you can never swap just two tiles and leave the rest. A two-tile swap is a single transposition, sign −1, odd — locked out. (Brute force agrees: of the 20,160 reachable home boards, the number that differ from solved in exactly two tiles is zero.) The smallest real rearrangement you can make is a three-tile cycle — rotate three tiles around, leave everything else — because that takes two swaps, and two is even. That is the whole secret of every "swap two pieces" magic trick done on a grid: it isn't a swap, it's a hidden three-cycle.
So the $1000 was safe, mathematically. The impossibility was proved in 1879 by William Woolsey Johnson and William E. Story in the American Journal of Mathematics — Johnson showed the swapped board can't be solved, and Story supplied the parity reason you've just been sliding around in. Loyd's prize was offered into a wall that had already been described in print.
And there is a second lie folded into the first. For decades Loyd claimed he invented the puzzle. He did not. The historians Jerry Slocum and Dic Sonneveld traced the real origin to Noyes Palmer Chapman, a postmaster in Canastota, New York, around 1874; Loyd's authorship claim first appeared in 1891 and he repeated it until his death in 1911 — a story that "fooled everyone for 115 years," as Slocum put it. The man who offered a prize for an impossible feat had also taken credit for a puzzle he didn't make. The mathematics, at least, has never lied: half the arrangements are unreachable, the line between the halves is one unflippable bit, and you can check every word of it below.
Wm. W. Johnson & W. E. Story, "Notes on the '15' Puzzle", American Journal of Mathematics 2 (1879) 397–404 — the first proof of impossibility and the parity invariant.
R. M. Wilson, "Graph puzzles, homotopy, and the alternating group", J. Combinatorial Theory Ser. B 16 (1974) 86–96 — the general theorem: on almost every puzzle graph the reachable group is exactly the alternating group.
Jerry Slocum & Dic Sonneveld, The 15 Puzzle: How It Drove the World Crazy (Slocum Puzzle Foundation, 2006) — the documented history: Noyes Chapman's authorship (c. 1874), the 1880 craze, and the dismantling of Loyd's claims.
Historical summary cross-checked against David Richeson, "A picture of frustration: Sam Loyd's 15 puzzle" (2011) and Jaap Scherphuis, "The Fifteen / 14-15 puzzle" (jaapsch.net). The mathematics (the count 181,440, the invariant, the 3-cycle minimum, the 8-puzzle diameter of 31) is computed from scratch in the verifier — not taken from any source.