Rules

1. Start with n disks stacked on one peg, largest at the bottom and smallest on top.
2. Move the whole ordered stack to a designated destination peg; the remaining peg is the auxiliary (spare).
3. Move only one disk at a time: take the top disk of a peg and place it on another peg.
4. Never place a larger disk on a smaller disk—only on an empty peg or on a strictly larger disk.
5. On three pegs the minimum number of moves is exactly (2^n - 1).

Allowed moves

Illegal attempts (larger onto smaller, or non-top disk) must be rejected with clear feedback; the board state does not change.

How to play

1. Choose n (beginners: 3; standard practice: 4–5; classic toys often 5–8).
2. Mark start peg and goal peg; the third peg is spare.
3. Move disks one by one under the size rule.
4. Recursive strategy for an optimal solve: move the top (n-1) disks to the spare, move the largest disk to the goal, then move the (n-1) stack onto the goal.
5. Finish when every disk sits on the goal peg in size order. Hitting (2^n - 1) moves is an optimal solve.

Board, pieces, and n

The rule focus is the size constraint and the (2^n-1) optimum—not free stacking without the “never larger on smaller” law.

Play modes

You can also play the Tower of Hanoi online.

(1) Lucas’s 1883 product

The Tower of Hanoi entered print and commerce in Paris in 1883. French mathematician Édouard Lucas marketed a boxed peg-and-disk game under the playful pseudonym “N. Claus (de Siam),” an anagram of “Lucas d’Amiens.” The label’s “College of Li-Sou-Stian” is likewise an anagram of the Lycée Saint-Louis, where Lucas taught. Surviving boxes and instruction leaflets—documented by the Puzzle Museum and by Paul Stockmeyer’s transcriptions—show a Tonkin / Hanoi framing that matched contemporary French interest in Indochina. That packaging is marketing geography, not evidence that Lucas had recovered an archaeological object from Vietnam.

(2) The Benares legend as product folklore

The leaflet accompanying the game told a legend: beneath a temple dome in Benares (Varanasi), Brahmins move sixty-four golden disks among three diamond needles under the same size rule; when the last disk is placed, the tower, the priests, and the world end. Variants relocate the temple or rename the priests, but the exponential punch line is constant: (2^{64}-1) moves. Treat the story as packaging folklore that dramatizes growth. It is not independent evidence that a mechanical Tower of Hanoi existed in ancient India. MacTutor and modern surveys state the same caution: Lucas invented the documented puzzle; the Indian setting is attached legend.

(3) Recreational mathematics and recursive popularization

Lucas collected such diversions in Récréations mathématiques (and related booklets). The three-peg solution became a textbook illustration of recursion and mathematical induction: to move n disks, move (n-1) to the spare peg, move the largest disk once, then move (n-1) onto the goal. The closed form (T(n)=2^n-1) follows at once. Later popularizations linked optimal play to binary counting and Gray codes: the disk moved at step k and the parity of peg visits can be read from bit flips. Martin Gardner’s mid-century essays helped fix the puzzle in Anglophone recreational math; MathWorld and discrete-math courses still present it as the canonical exponential-recursion example.

(4) Reve’s puzzle and multi-peg research

A four-peg relative appears in Henry Ernest Dudeney’s early-twentieth-century work as the Reve’s puzzle (cheeses moved among stools). Extra pegs break the simple (2^n-1) formula. In 1941 Frame and Stewart proposed recursive schemes for r pegs that became the presumed-optimal Frame–Stewart family; for decades optimality for four pegs remained open, though the algorithm was widely taught. Thierry Bousch proved Frame–Stewart optimal for four pegs in 2014. Everyday “Tower of Hanoi” still means the classic three-peg game; Reve’s puzzle is a sibling, not a replacement.

(5) Cultural use in computer-science teaching

From the mid-twentieth century onward, introductory programming and algorithms courses adopted the three-peg Tower of Hanoi as a first recursive procedure: base case one disk; inductive step two recursive calls plus one move. Lecturers use it to contrast elegant recursion with the concrete cost (2^n-1), to motivate induction proofs, and sometimes to encode move sequences with binary or Gray-code tricks. Physical classroom kits and online applets keep the same rule set Lucas sold in 1883. The legend of sixty-four disks remains a vivid way to say “exponential growth,” not a claim about temple archaeology.

References

1. MacTutor History of Mathematics, The Towers of Hanoi
2. Puzzle Museum, Eduardo Lucas: La Tour D’Hanoi (1883 box & leaflet)
3. Paul K. Stockmeyer, The Tower of Hanoi (original instructions & bibliography)
4. Wolfram MathWorld, Tower of Hanoi
5. English Wikipedia, Tower of Hanoi
6. Andreas M. Hinz, “The Tower of Hanoi,” 1989 (e-periodica scan)
7. Hinz et al. / Stockmeyer survey material on multi-peg variants