The classical recursion puzzle — three pegs, n disks, 2ⁿ − 1 moves.
Play It
Characterization
The Tower of Hanoi was invented in 1883 by the French mathematician Édouard Lucas, under the pseudonym N. Claus de Siam, and sold as a child’s toy. Three pegs; a stack of n disks of increasing size; move the stack from one peg to another, never placing a larger disk on a smaller. The minimum number of moves is exactly 2ⁿ − 1 — the simplest non-trivial closed form a beginning programmer can discover for themselves. Lucas dressed the puzzle in a legend (a Brahmin temple where sixty-four golden disks are being moved by priests, the world to end on completion) chiefly to fix the magnitude of 2⁶⁴ − 1 in the popular imagination. The puzzle has since become the canonical introduction to recursion in computer science: the first proof many students encounter that a problem can be solved by reducing it to a smaller copy of itself. It belongs to the Academy as the wonder of a single trick — recurse on n − 1 — that, once seen, can never be unseen.
Lineage
Invented 1883 by Édouard Lucas in Paris. The recursive solution is treated as foundational by Donald Knuth in The Art of Computer Programming, Volume 1 (1968). The four-peg generalisation is the Frame–Stewart conjecture (1941; proved optimal for small n by Bousch in 2014).
Quests
The Magus
Generalise the Tower of Hanoi to four pegs and derive (or implement) a solution strategy. Compare the move count you achieve, for at least one value of n ≥ 10, to the Frame–Stewart conjecture.
The Adventurer
Solve a physical or rendered Tower of Hanoi with at least eight disks using only legal moves. Time yourself across two separate attempts and note what changed between them.
The Sage
Explain the recursive solution to the Tower of Hanoi to someone learning to program. Derive the closed form 2ⁿ − 1 from the recursion. Cite Lucas’s 1883 original presentation.