The puzzle that is exactly half solvable

A sliding puzzle has fifteen numbered tiles in a four-by-four tray with one square empty, and the only thing anybody can do to it is push a tile into the gap. The question is which arrangements can be reached, and the honest first answer is that nobody could tell by looking: the puzzle has twenty thousand billion arrangements and no obvious reason to prefer any of them.

Exactly half can be reached. Not roughly half, and not half for a reason that depends on the size of the tray — half, for a reason that fits in a sentence, and the same sentence says which half.

The sign of a permutation is one bit that survives composition, and nothing finer survives. This rung is what that bit forbids. It is the first place on this ladder where the parity is not being established or characterised but used — and used for the thing an invariant is for, which is to rule something out.

A slide is a transposition #

Read the tray as a sequence: the sixteen squares in reading order, each holding a label, with the empty square counted as the sixteenth label. Then an arrangement is a permutation of sixteen things, and a legal move exchanges the blank with a neighbour — which is a transposition of two entries of that sequence.

Every transposition flips the sign. So every legal move flips the sign of the arrangement, whatever the two squares involved are and however far apart they sit in the reading order. That last clause is the part worth pausing on: a vertical slide exchanges two labels four places apart in the reading, a horizontal slide exchanges neighbours, and the sign flips in both cases for the same reason. A transposition is a transposition.

If the blank stayed put, the argument would be finished at that point and would prove too much — it would say that no sequence of moves returns to the start, which is false, since sliding a tile out and back is two moves. The blank does not stay put, and the second half of the invariant is about where it is.

The blank’s taxicab distance from its home square — the number of rows plus the number of columns it must travel — changes by exactly one at every move, because a move takes it one square. So it, too, flips parity at every move.

Two quantities that always flip together have a sum that never changes. That sum, taken modulo two, is the invariant:

the number of pairs out of order in the reading, plus the blank’s distance from home, is even on every arrangement reachable from the solved one.

It is even on the solved board, where both terms are zero. It is odd on the board with two tiles exchanged, where the first term is one and the second is zero. So no sequence of slides connects them, and the puzzle sold with the fourteen and the fifteen swapped is not difficult.

Half, and exactly half #

The invariant rules out at least half the arrangements. It does not by itself say that everything else is reachable — a second invariant could exist and cut the reachable set to a quarter, and nothing said so far excludes it.

That gap is why the figures walk the board rather than quote the theorem. On a board small enough to exhaust, the search settles both halves of the claim at once: the reachable set is found by moving, and it comes out at exactly half.

The two-by-two picture is worth more than its size suggests, because it shows the shape of the answer rather than the count. The reachable arrangements do not merely fail to include the others; they form a component of a graph, and the other component is a component too — the same size, with the same structure, joined to nothing. A reader who has met a Gray code as a walk through a cube’s corners has seen the same object: a set of configurations with an adjacency, and a question about which of them one walk can visit.

On the four-by-four board the exhaustive walk is unavailable — ten million million arrangements is not a search a figure can carry out — so the argument changes shape rather than scale. Instead of listing what is reachable, check that the quantity never changes; and that is a claim about moves, of which there are at most four from any position.

The two figures are doing different jobs and it is worth naming which. The search proves that the reachable set is exactly half, on one board. The invariant proves that it is at most half, on every board. Neither is a substitute for the other, and the standard proof of the full theorem is the two arguments joined: the invariant gives the upper bound, and an explicit procedure for solving any arrangement of the right parity gives the lower one.

The tray’s shape does not matter #

The invariant was stated for a four-by-four tray and nothing in it depends on that. The reading order is whatever the tray’s rows dictate; the taxicab distance is measured on whatever grid there is; and the argument that a move flips both terms is the same argument.

This is the point at which a reader is entitled to ask what the parity is doing, since the answer keeps coming out the same. The honest answer is that the puzzle’s legal moves generate the alternating group’s worth of arrangements and no more, and the reason is that the generators are all transpositions paired with a blank displacement — so the group they generate sits inside the subgroup where the two displacements cancel. The blocks a subgroup cuts out are exactly the two halves in the picture above: one coset each, of a subgroup of index two.

Reading it that way also explains why the answer is half rather than a third or a tenth. The number of pieces is the index of the subgroup the moves generate, and the only labels a permutation carries into a commutative group form a group of order two. A three-valued invariant on permutations would cut the arrangements into thirds; there is no such invariant, so nothing cuts them into thirds. The fraction is a theorem about the symmetric group, not a fact about trays.

Deciding one arrangement, on paper #

The invariant is a recipe as well as a proof, and running it on a particular tray takes under a minute.

Write the tiles out in reading order, skipping nothing and counting the empty square as the highest label. Count the pairs that are out of order — for each tile, how many later tiles carry a smaller label — and add them up. Then count how many rows and columns the blank is from its home corner, and add that. If the total is even the arrangement can be solved; if it is odd it cannot, and no amount of sliding will help.

Two things about that recipe are worth noticing, because both are places a first attempt goes wrong. The first is that the pairs are counted in the reading, not on the tray: two tiles that sit side by side in different rows are far apart in the reading and contribute accordingly. The second is that the blank has to be included somewhere, and it is cleaner to include it as the largest label and then also count its distance than to leave it out. Dropping it entirely gives a quantity that is unchanged by horizontal moves and flipped by vertical ones, which is invariant on a tray with an odd number of columns and useless on a tray with an even number — a discrepancy that has confused generations of readers of the four-by-four case, where the columns happen to be even.

The version stated here has no cases in it, and the reason is the one the figures make: a slide is a transposition of the full reading, and a transposition flips the crossing count whatever the two positions are. Putting the blank into the sequence is what removes the need to argue separately about vertical and horizontal moves.

Who asked, and the prize nobody collected #

The puzzle reached the public in 1880 and the theorem was already in print. Johnson gave the parity obstruction and Story the converse in the American Journal of Mathematics in 1879 — the two halves of the exact count, published together, before the craze that made the question famous.

Sam Loyd later claimed to have invented the puzzle and to have offered a thousand dollars for a solution to the arrangement with the fourteen and fifteen exchanged. He invented neither. The puzzle was Noyes Chapman’s, the prize was advertised after the impossibility was known, and the money was never at risk — which is the detail that makes the episode worth recording rather than merely amusing. A prize for an impossible task is safe exactly when somebody has proved it impossible, and the proof had been available for a year.

The mathematical content of the story is in what the offer implies about the state of the question. A thousand dollars is a serious sum in 1880, and it was offered in confidence, against a public that had been trying for months and failing. Failure by many people for a long time is not a proof, and the offer would have been reckless without one; with one it is arithmetic. The distance between those two situations is the whole reason to want an invariant rather than a great deal of evidence.

Three at once, and a twelfth #

The cube sold as a puzzle is the same argument run three times, and running it three times is what makes the shape of the argument visible.

A cube’s arrangement is three pieces of data: where the eight corners have gone and how each is twisted, and where the twelve edges have gone and whether each is flipped. Each of the three has a total that no face turn changes — the corner twists add to a multiple of three, the edge flips add to an even number, and the corner and edge permutations have the same sign.

Three independent constraints, of sizes three, two and two, and $3 \times 2 \times 2 = 12$. So one arrangement of the pieces in twelve can be reached, which is the standard count and which arrives here as an index rather than as a search — the search being unavailable at forty-three quintillion.

The three defects in that figure are the three things a cube cannot be taken apart and reassembled into. Each is ruled out by exactly one of the quantities and passes the other two, which is what makes the three constraints independent rather than three readings of one constraint. Prising one corner out and putting it back rotated leaves the edges and the permutation perfect and breaks the corner total; that is the whole diagnosis, and it takes one line of arithmetic rather than any amount of trying.

What an argument of this shape costs #

An invariant proves impossibility and proves nothing else, and the price is easy to overlook because the conclusion sounds so strong.

It says nothing about how hard a reachable arrangement is. The invariant is even on a solved board and even on a board scrambled for an hour, and it distinguishes them not at all. Every question anybody actually asks about these puzzles — how many moves are needed, which arrangement is worst, whether a short solution can be found quickly — is invisible to it.

It says nothing about which arrangements are reachable beyond the parity, on a puzzle where more than one invariant operates. The cube’s count is a twelfth only because the three quantities are the whole of the obstruction, and knowing that requires a construction: a procedure that reaches everything the three permit. Without that half, the honest statement is “at most a twelfth”, and the gap between at most and exactly is where all the work is.

And it is fragile in a way worth stating, because the fragility is instructive. Allow one extra move — lift a tile out and drop it elsewhere, permit the blank to wrap from one edge of the tray to the other — and the invariant is no longer invariant, because the new move need not flip both terms. The theorem is about a generating set, not about a puzzle, and every impossibility proof of this kind inherits that sensitivity. It is the same sensitivity that makes a rusty compass reach as far as a working one surprising: what a set of operations can do is decided by the algebra the operations generate, and small-looking changes to the operations can change that algebra completely, or not at all, with no way to tell by inspection.

What the pictures cannot show #

The exhaustive searches are on boards of four and six squares. Nothing here walks the fifteen-puzzle’s state space, and the claim that its reachable set is exactly half rather than at most half rests on a construction this essay does not draw — the standard cycling procedure that solves any even arrangement.

The cube figure checks the three quantities against the eighteen face turns and against three specific defects. It does not verify that a scrambled cube satisfying all three can always be solved; that is the hard half of the count, it was settled by explicit algorithms rather than by an invariant, and no figure of this kind can carry it.

And the state graph is drawn for a tray of four squares because a tray of six already has 720 nodes. The two-ring picture is exactly right about the structure and is not evidence about any larger board; the invariant is what carries the structure upward, and the ring picture is what makes it believable.

Where the ladder goes next #

Named here as a debt: the distance on these puzzles — how many moves an arrangement needs, where the worst one is, and why the answer for the four-by-four board took a computer search of its own. Parity settles reachability and says nothing about it.

Also unwritten: which groups a puzzle’s moves generate in general, which is a question with a satisfying answer for the sliding puzzles on graphs and is not the parity argument at all.

Sideways, the label that flips at every move is the sign, the theorem that no finer label exists is the rung below, the two halves are a subgroup’s cosets, and the group whose absence of a normal subgroup makes a related impossibility is the quintic’s.

What is worth carrying away #

A quantity that cannot change is worth more than any amount of unsuccessful searching, and finding one is usually easier than the searching would have been.

The reachability question for a sliding puzzle has twenty thousand billion cases and no obvious structure. The invariant has two terms, is checked in a line, and settles every case at once. Nothing about the puzzle suggested it; what suggested it was asking what each move preserves rather than what the positions have in common — which is the move worth copying, because moves are few and positions are many.

The habit worth taking is to look for the invariant on the generators. A property preserved by every generator is preserved by everything they generate, and that sentence converts an infinite or astronomically large search into a check on a handful of operations. It is why the cube’s count can be settled without visiting a single one of its arrangements.

The corollary is about how to read a failure. When a quantity is preserved by every generator but the configurations it forbids turn out to be reachable anyway, the generating set was wrong — a move was missed. And when the quantity forbids more than the true obstruction, as it does whenever at most cannot be improved to exactly, the missing half is a construction, and no further invariant will supply it.