15 Puzzle

Slide the numbered tiles back into order in as few moves as possible. The timeless sliding puzzle.

The 15 puzzle caused a genuine craze in 1880, fuelled by a prize for solving a position that was provably impossible. Sam Loyd claimed to have invented it and did not; he did popularise the unsolvable variant, which is arguably worse.

The mathematics is the interesting part: sliding moves preserve the parity of the permutation combined with the blank's row distance, which splits all arrangements into two classes. Half of every possible board is unreachable from the solved state, which is why swapping two tiles physically turns a solvable puzzle into one that can never be completed.