Invariants

An invariant is something no allowed move changes. Slide the puzzle, cut squares from the board, or add bridges to Königsberg, and the page keeps the invariant in view: the parity of the inversion count, black against white, the land masses with an odd number of bridges. When it differs between the start and the goal, no sequence of moves gets there.

Worked example — Invariants

Inversions	1
The invariant: inversions mod 2	odd
Moves from solved	unreachable
Click a tile next to the gap to slide it	12345687

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Invariants

An invariant is a quantity that no allowed move changes. If it has one value at the start and a different value at the goal, the goal cannot be reached, whatever moves are tried, and nothing has to be searched to know it.

What each symbol means

I: the invariant: here the parity of the inversion count, the difference between black and white squares, or the number of land masses with an odd number of bridges
d(v): the degree of a land mass v: how many bridges end there

Where the formula comes from

Why a slide keeps the parity. Read the eight tiles row by row, ignoring the gap. A sideways slide does not change that reading order at all. An up-or-down slide moves one tile three places along it, past the two tiles between its old square and its new one. Each of those two pairs gains or loses an inversion, so the count changes by −2, 0 or +2, never by an odd number. Solved has 0, so a position with an odd count cannot be reached. That every position with an even count can be reached is the harder half: for the 8-puzzle the page’s search shows it directly.
Why a domino keeps the difference. On a chessboard every square’s neighbours are the other colour, so a domino, which covers two neighbouring squares, covers one black and one white. Laying dominoes therefore never changes black minus white among the uncovered squares. A finished tiling leaves nothing uncovered, a difference of 0, so it needs a difference of 0 at the start: as many squares of one colour as of the other.
Why at most two odd land masses. Follow the walk. Each time it passes through a land mass it arrives by one bridge and leaves by another, so the bridges at a land mass are used in pairs, except at the start, where one is used leaving, and at the end, where one is used arriving. If the walk ends where it started, every land mass has an even number of bridges; otherwise exactly the start and the end have an odd number. The converse also holds when the bridges join everything up, and the page finds the walk by building it in loops and splicing them together.

Half of a 3 × 3 sliding puzzle can never be reached, and you can tell which half without searching 🖖

Press 7 and 8 swapped and try to solve it. Count the pairs of tiles that stand in the wrong order, reading row by row: here one, 8 before 7. A sideways slide leaves that count alone, and an up-or-down slide carries one tile past two others, changing it by 0 or 2. So the count stays odd for ever, and solved has 0. The page also searched every position from solved: 181,440 of the 362,880 arrangements are reachable, exactly the ones with an even count, and the farthest two need 31 moves. The 15-puzzle swept America in 1880, and in the 1890s Sam Loyd offered $1,000 for undoing a swap of 14 and 15, a prize nobody could ever win.

Cut two opposite corners off a chessboard and no domino tiling survives 🖖

Press Opposite corners. The whole board can be covered by 32 dominoes in 12,988,816 ways. Cut two opposite corners and it cannot be covered at all: both corners are the same colour, so 30 squares of one colour remain against 32 of the other, and every domino covers one of each. Cut the two corners at the ends of one edge instead, one of each colour, and there are 2,436,304 tilings. Then press Walled-off corner: 30 and 30, perfectly balanced, and still none, because the corner square has no neighbour left. The colour count can prove a board impossible; it can never prove one possible.

Königsberg’s walk fails on a count you can do in your head 🖖

Press Königsberg. The island has 5 bridges and each of the three other land masses has 3. A walk that crosses each bridge once arrives at and leaves every land mass it passes through, using its bridges in pairs; only where the walk starts and where it ends can one be left over. So at most two land masses may have an odd number, and here all four do. Euler settled it in a paper written in 1735. Add one bridge between the two banks with the + beside B–C: two odd land masses remain, and the page finds the walk, from A to D. The four counts always add up to twice the number of bridges, which is why the odd ones always come in pairs.

Problem solved in full

Could anyone win Sam Loyd’s $1,000? 4 steps
On the 4 × 4 board, swap only 14 and 15 and leave the gap in its corner. Sam Loyd offered $1,000 to anyone who could slide that back to solved. Could it be done?

Open this problem in the tool
1. On this page’s 3 × 3 board, the invariant was the parity of the inversion count:
  
  $3 wide: a vertical slide passes 2 tiles \Rightarrow Δ I \in {- 2, 0, + 2}$
2. On a board four wide, an up-or-down slide carries a tile past three others, so the count changes by an odd number, and the gap changes row:
  
  $4 wide: a vertical slide passes 3 tiles \Rightarrow Δ I \in {- 3, - 1, + 1, + 3}, Δ row = \pm 1$
3. Every slide flips both parities or neither, so their sum, taken mod 2, never changes:
  
  $I + row of the blank (mod 2) never changes$
4. Compare the two positions, with the gap in row 4 in both:
  
  $solved: 0 + 4 = 4 (even), 14 \leftrightarrow 15 : 1 + 4 = 5 (odd)$
Answer

Nobody could win it: the swap lies on the wrong side of the invariant. Exactly half of the 16! arrangements, 10,461,394,944,000, can be reached from solved. Press 7 and 8 swapped for the 3 × 3 version of the same trap.

$unreachable; \frac{16 !}{2} = 10, 461, 394, 944, 000 arrangements can be reached$

Learning path

Methods of proof

References (3)

The parity argument for the 15-puzzle, the history (made in upstate New York in the 1870s, a craze in early 1880, analysed in the American Journal of Mathematics that year) and Sam Loyd's later $1,000 prize for a swap that cannot be done: K. Conrad, "The 15-Puzzle (and Rubik's Cube)", expository notes, University of Connecticut.
Euler's paper on the seven bridges of Königsberg, which reduced the walk to the number of bridges at each land mass: L. Euler, "Solutio problematis ad geometriam situs pertinentis", Commentarii academiae scientiarum Petropolitanae 8, 128–140 (written 1735, published 1741); Eneström number E53, The Euler Archive.
The number of domino tilings of square boards, with 12,988,816 for the 8 × 8 chessboard: OEIS Foundation, "A004003: Number of domino tilings (or dimer coverings) of a 2n X 2n square", The On-Line Encyclopedia of Integer Sequences.

By the 42Math team · Reviewed against published sources. Corrections welcome.