In 1880 a sliding-tile puzzle swept the United States. A small square frame held fifteen numbered tiles and one empty square; the tiles could be slid into the empty space, and the goal was to arrange them from to in order. Within months the puzzle had crossed the Atlantic and was reportedly causing brawls in Paris cafés, missed appointments in Berlin offices, and parliamentary motions in London suggesting that workers be banned from playing it on company time.
In the middle of this craze, the famous American puzzle designer Sam Loyd offered a prize: a thousand dollars — perhaps thirty thousand in today’s money — to anyone who could solve a specific variant. Start from the conventional solved position, but swap the tiles labelled and . From this position, slide tiles back into the standard solved order. No one ever collected the prize. Loyd’s money was perfectly safe, because group theory had already proved that the rearrangement was mathematically impossible — though this would not be widely understood for a few more years.
This article is about why Loyd’s swap is impossible, what mathematical invariant rules it out, and how a small piece of permutation theory turns a popular puzzle into a clean and beautiful application of group theory.
The puzzle, and the impossibility
The picture below shows the standard solved position on the left and Loyd’s “swap and ” position on the right. The blank square — the only one that allows any motion — sits in the bottom-right corner in both. The only difference is that two tiles have been exchanged.
To the eye, the two positions are nearly identical. To group theory, they sit on opposite sides of an unbridgeable mathematical barrier.
The invariant
Every legal move slides one tile into the empty square — equivalently, it swaps the tile with the blank. If we think of the puzzle’s state as a permutation of the symbols , then every move is a transposition — a permutation that exchanges exactly two elements. A transposition is what mathematicians call an odd permutation, with sign .
Each legal move also moves the blank by exactly one row: it goes from one row to either the row above or the row below. So each move changes the row parity of the blank (whether it sits in an even-numbered or odd-numbered row, counted from the bottom).
Define the invariant as the product of two parities:
where is the row number of the blank, counted from the bottom. At every legal move, the first factor flips sign (because a transposition is odd) and the second factor flips sign (because the blank moves by one row). The product of two sign flips is no flip at all — the invariant stays the same.
Now compare the two positions in the picture. In the solved state, the tiles are arranged in the identity permutation (no swaps), so the sign is ; the blank is in the bottom row, , so . The invariant is .
In Loyd’s swapped state, the tiles differ from the identity by a single transposition (swap and ), so the sign is ; the blank is still in the bottom row, so again. The invariant is .
The two invariants differ. Since no legal move can change the invariant, the two positions cannot be connected by any sequence of moves. The Loyd configuration is unreachable from the solved configuration — and from every other reachable position. The thousand-dollar prize was safe forever.
Sign as a homomorphism
The deep reason this works is one of the cleanest facts in group theory. The set of all permutations of items forms a group, , called the symmetric group. The set of all integers under multiplication is a group too — the cyclic group of order . There is a function from one to the other:
assigning each permutation its sign. This function is a homomorphism: . The product of two even permutations is even; the product of two odd permutations is even; an even times an odd is odd. The sign respects multiplication, which is exactly what makes it useful as an invariant under group actions.
The kernel of the sign homomorphism — the permutations with sign — is called the alternating group . It has half as many elements as . The 15 puzzle’s invariant is essentially the statement that the configurations naturally split into the two cosets of in , indexed by the row parity of the blank. The reachable configurations form one coset (half of the position pairs), and the unreachable configurations form the other.
A quick check on small cases
For a smaller version — the -puzzle, a grid with eight tiles plus a blank — the same parity argument applies. Exactly half of the “permutation–position” pairs are reachable from the solved state. (Some of these correspond to the same board view because of the relative position of the blank, but the count works the same way.) The invariant turns the question “can position be solved?” into a quick computation: count the number of inversions in the permutation of the tiles, add the row index of the blank from the bottom, and check whether the total is even or odd.
The same algebraic structure governs sliding puzzles of all sizes. The “24-puzzle” obeys the same parity invariant; the “99-puzzle” likewise. The deep reason is always the same: each legal move is a single transposition, and the sign homomorphism is the canonical invariant under products of transpositions.
What the 15 puzzle teaches
The 15 puzzle was the first widely-publicised problem in which a non-trivial algebraic invariant ruled out a seemingly innocuous physical rearrangement. To a puzzle solver of 1880, the question “can I swap two tiles?” looked like a question for trial and error. To a group theorist — even one who had only just learned the sign of a permutation — it was a one-line proof of impossibility. The mathematical content of the answer is exactly the same as the original 19th-century proof, given by W. W. Johnson and W. E. Story in two papers in the American Journal of Mathematics in 1879, before the puzzle had even completed its craze.
This is one of the great pedagogical moments in elementary group theory. The puzzle is concrete, the moves are tangible, and the impossibility is real money. The invariant — the sign of a permutation times the row parity of the blank — is small, computable, and absolutely decisive. From it follow a thousand similar arguments throughout mathematics: every time you need to prove that one configuration cannot be reached from another, look for a quantity that is preserved by every move. Find such an invariant whose values differ on the two configurations, and impossibility follows automatically.
That logical move — identifying a conserved quantity to rule out a transformation — is one of the most general techniques in mathematics. It governs the impossibility of squaring the circle (the conserved quantity is “is algebraic”), of trisecting an angle with compass and straightedge (the conserved quantity is “lies in a field of degree a power of two”), and of solving the general quintic by radicals (the conserved quantity is the solvability of a Galois group). In every case, the question “can I do X?” is converted into the question “does this invariant force the answer no?”
Sam Loyd’s prize money was never in danger. The mathematics that made it impossible to claim was already on the table before he ever offered it, and the moral remains the same a century and a half later: when you want to prove something cannot be done, find an invariant. The 15 puzzle is the simplest non-trivial example in which that recipe pays off completely, and it remains, after all these years, one of the most charming demonstrations of group theory in action that mathematics has to offer.
Frequently asked
Did Sam Loyd really invent the 15 puzzle?
No, despite his lifelong claim. The puzzle was invented by Noyes Palmer Chapman, a postmaster in upstate New York, around 1874. By 1880 it had become a national craze in the United States and a continental craze in Europe. Loyd, a famous puzzle designer, attached his name to the puzzle by offering his thousand-dollar prize, but the historical evidence is clear that he was the populariser and not the inventor. He maintained the misattribution for the rest of his life, and many histories of mathematical puzzles still credit him today.
What does 'parity of a permutation' actually mean?
A permutation rearranges a list of objects. Any such rearrangement can be built up by repeatedly swapping pairs of adjacent (or any two) items, called transpositions. The remarkable theorem of Cauchy is that although a permutation can be written as a product of transpositions in many ways, the number of transpositions is always either even for one permutation, or always odd — never both, and the property is intrinsic. The parity of a permutation (its sign) is therefore well-defined: +1 for even, −1 for odd. The set of even permutations forms a subgroup called the alternating group A_n.
Why does the parity invariant work for the 15 puzzle?
Every legal move slides one tile into the blank's position. As a permutation, this is a single transposition of the tile and the blank — an odd permutation. But it also moves the blank up or down by exactly one row, changing the row parity of the blank. So the product of (the permutation parity of the tile arrangement) and (the parity of the blank's row) changes by an odd factor × an odd factor = an even factor at every move. The product is therefore an invariant: it cannot change. Two positions are reachable from each other only if they have the same value of this invariant.
Does the impossibility argument generalise?
Yes. The same parity invariant rules out exactly half of all the configurations of any 4×4 sliding-tile puzzle, and a closely related invariant works for any rectangular sliding puzzle whose grid has an odd or even number of columns. Computer scientists have studied the optimal solution length for the 8-puzzle (3×3 grid) and 15-puzzle — God's number for the 15-puzzle, the worst-case minimum number of moves needed from any solvable starting position, is 80 — and proved that the n×n puzzle is NP-hard. The puzzle has become a standard benchmark for search algorithms in artificial intelligence.