Tower of Hanoi
A mathematical puzzle of disks and rods.
The Tower of Hanoi is a mathematical game or puzzle consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, approximating a conical shape. The objective is to move the entire stack to one of the other rods, obeying specific rules. The puzzle game was named after the capital city of today's Vietnam.
- Inventor
- Édouard Lucas
- Field
- Mathematics
- Nationality
- French
- Known for
- Tower of Hanoi puzzle
- Minimum moves formula
- 2^n − 1 (where n is the number of disks)
Lore & Background
Accompanying the game was an instruction booklet, describing the game's purported origins in Tonkin, and claiming that according to legend, Brahmins at a temple in Benares have been carrying out the movement of the 'Sacred Tower of Brahma', consisting of 64 golden disks, according to the same rules as in the game, and that the completion of the tower would lead to the end of the world. Numerous variations on this legend exist, regarding the ancient and mystical nature of the puzzle.
Reader's Guide
The Tower of Hanoi is significant as a classic mathematical puzzle that demonstrates key concepts in recursion and algorithm design. The minimum number of moves required to solve a Tower of Hanoi puzzle with n disks is 2^n − 1. With three disks, the puzzle can be solved in seven moves. The puzzle has iterative and recursive solutions; the recursive solution is often used as an example when teaching programming. The puzzle's legend claims that Brahmins at a temple in Benares have been moving a 'Sacred Tower of Brahma' of 64 golden disks, and that completion would end the world. The puzzle's name comes from the capital city of today's Vietnam. Its legacy endures as a tool for teaching mathematical induction and problem-solving.
Did You Know?
- The minimum number of moves required to solve a Tower of Hanoi puzzle with n disks is 2^n − 1.
- With three disks, the puzzle can be solved in seven moves.
Frequently Asked Questions
What is the minimum number of moves to solve Tower of Hanoi?
The optimal solution for n disks always requires exactly 2^n − 1 moves. A standard three-disk version takes seven moves, while a 64-disk version would demand over 18 quadrillion moves.
What are the rules you must follow in Tower of Hanoi?
You may slide only one disk at a time, and a larger disk can never rest on top of a smaller one. The objective is to move the whole stack from the starting peg to a different peg while respecting those two constraints.
Why is Tower of Hanoi so important in computer science?
It is a go-to teaching example for recursion, because the optimal strategy naturally decomposes into solving a smaller sub-puzzle, moving the base disk, then solving the sub-puzzle again. It also appears in discussions of state-space search and computational complexity.
What is the 'N. Claus de Siam' story behind the puzzle?
Lucas credited a made-up Siamese temple priest named N. Claus de Siam as the puzzle's original discoverer. That name is actually an anagram of 'Lucas d'Amiens,' a wink pointing to his own name and his hometown of Amiens, France.
More in Board Games & Puzzles 1-18
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record