What Is the Tower of Hanoi?
The Tower of Hanoi is a puzzle about moving a stack of disks between three pegs. You must move every disk to another peg while following two simple rules. The puzzle is easy to learn, yet it reveals a powerful way to solve problems.
Each disk has a different size, and the disks begin in order on one peg. The largest disk sits at the bottom, with smaller disks stacked above it. Your goal is to move the full stack to either of the other pegs.
The challenge grows fast as you add disks. A stack of three needs just seven moves, while a stack of ten needs 1,023. That sharp rise makes the puzzle a useful lesson in planning and recursion.
History and the Legend Behind Its Name
French mathematician Édouard Lucas introduced the puzzle in 1883. He published it under the name N. Claus de Siam, an anagram of Lucas d'Amiens. That playful name helped set up the puzzle's famous legend.
In the legend, priests in a temple move 64 gold disks between three diamond pegs. They must follow the same rules as the puzzle. The story says the world will end when they finish.
The legend is a story, not a record of a real temple task. Still, it gives the puzzle a memorable scale. At one move each second, the 64-disk solution would take about 585 billion years.
Lucas's puzzle joined recreational mathematics, where people explore math through games and challenges. Its rules are simple enough for beginners, yet its move count connects to deep ideas about patterns and growth.
Rules and Gameplay
To play, set up three pegs and place several disks on one peg. Keep the disks in size order, with the largest at the bottom. The other two pegs act as spare spaces during the move.
Every turn moves one disk from one peg to another. You may move only the top disk from a peg. You may never place a larger disk on top of a smaller one.
These rules make each move matter. For example, the largest disk cannot move until every smaller disk above it has been cleared. You must park those disks on the spare peg without breaking their order.
- Move one disk at a time.
- Only move a peg's top disk.
- Never place a large disk on a smaller disk.
- Finish with the full stack on a different peg.
Choose any number of disks to begin. Three disks show the core idea without a long wait, while four or five disks make planning more important.
The Math: Why the Fewest Moves Are 2n − 1
The fewest moves for a stack of n disks is 2 to the power of n, minus one. For one disk, that is one move. For two disks, it is three moves, and for three disks, it is seven.
To move a stack, first move the top n minus one disks to the spare peg. Then move the largest disk to the target peg. Finally, move the smaller stack onto the largest disk.
This pattern gives the rule T(n) = 2T(n−1) + 1. The first part moves the smaller stack, the plus one moves the biggest disk, and the last part moves the small stack again. Solving that pattern gives 2ⁿ − 1.
Here are a few totals:
| Number of disks | Fewest moves |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 10 | 1,023 |
| 64 | 18,446,744,073,709,551,615 |
Each added disk nearly doubles the work. This is exponential growth, a pattern that appears in many computing problems. The Tower of Hanoi makes that growth easy to see and count.
Strategies for Solving the Puzzle
The most reliable approach is to break a large task into smaller ones. To move a stack, clear its top disks, move the largest disk, then rebuild the stack. Repeat that same plan for each smaller stack.
This method is called recursion. A recursive plan calls a smaller version of itself until it reaches a simple case. For the Tower of Hanoi, the simple case is moving one disk directly to its target.
For three disks, the plan is concrete. Move the top two disks to the spare peg, move the largest disk to the target, then move the two smaller disks onto it. The first and last parts each take three moves, so the total is seven.
A useful manual check is to track the largest disk. It moves only once in the optimal solution. Before that move, clear every smaller disk; after it, place the smaller stack on top.
There is also a simple move pattern for repeated play. Number the disks from smallest to largest. Move the smallest disk every other turn, and use the remaining turns for the only legal move that does not involve it.
The direction of the smallest disk depends on the disk count. With an odd number of disks, it moves from the start peg toward the target peg. With an even number, it moves toward the spare peg first. Then repeat the pattern until the stack is complete.
How the Puzzle Helps Explain Algorithms
Computer science uses the Tower of Hanoi to teach recursive algorithm design. The same three-step plan can be written as a program: move a smaller stack, move one disk, then move the smaller stack again. The program stops when only one disk remains.
A simple algorithm needs only a few lines, but its run time grows quickly. For n disks, it makes 2ⁿ − 1 moves. This makes the puzzle a clear example of an easy-to-write method that becomes slow on large inputs.
The puzzle also helps learners trace function calls. A request to move four disks leads to a request to move three, then two, then one. Watching those calls return can make recursion less abstract.
Its value is not limited to code. Teachers can use the puzzle to show why order and constraints matter. Learners can also compare a planned solution with random moves and see how much wasted effort each approach creates.
A Small Puzzle With a Large Lesson
The Tower of Hanoi begins with three pegs and a few disks, but it teaches much more than a move sequence. Its rules introduce careful planning, its math explains exponential growth, and its solution shows recursion in action.
Start with three disks and aim for seven moves. Once the pattern feels clear, add a disk and predict the new total before you begin. The best solution is not a lucky sequence. It is a repeatable plan.



