15-Puzzle Impossibility

Intro to Proofs · Axiom Academy

EXAMPLE 15-Puzzle Impossibility Proving a configuration is unsolvable with a parity invariant Take a solved 15-puzzle and swap only tiles 14 and 15 , leaving the blank in the bottom-right corner. Prove that this configuration can never be returned to the solved state by legal sliding moves. The configuration under analysis: tiles 14 and 15 are swapped (highlighted), everything else solved, blank in the bottom-right. You proved a specific 15-puzzle configuration is impossible to solve — without searching a single move — by tracking one quantity that legal moves can never change. Parity invariant: permutation parity (from inversions) + blank-row parity stays constant under every legal slide. Permutation parity: read tiles in order and count inversions — pairs where a larger number precedes a smaller one. Here that count is 1 , so ODD. Position parity: ODD when the blank sits in an odd-numbered row from the bottom (row 1 here), EVEN otherwise. Why moves preserve it: horizontal slides change neither parity; vertical slides flip both , so their sum is fixed. The verdict: our board is EVEN, the solved board is ODD — different invariant ⇒ no path between them ⇒ unsolvable. This is the heart of an invariant proof : find a quantity nothing in the rules can change, show the start and target disagree on it, and impossibility follows. The same idea — parity and sign of a permutation — reaches far beyond this puzzle into group theory.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.