15-Puzzle
Slide tiles into order. The solver is IDA* — and parity proves what's impossible.
moves: 0
Solvability is decided by parity, not search: a slide is a transposition, so inversion parity (plus the blank's row on even widths) is invariant. Sam Loyd's “swap 14 and 15” prize puzzle — try the Loyd trap button — is provably unsolvable in O(n²). The IDA* solver uses Manhattan distance + linear conflict and finds a shortest solution.