🎮 How to Play
- Click a peg to pick up its top disc, then click another peg to drop it.
- Bigger discs cannot rest on smaller ones.
- Move all discs from the left peg to the right peg.
- Optimal moves = 2^N - 1.
About this tool
Classic recursive puzzle from 1883 by Édouard Lucas. Move N discs from left to right peg using a middle peg. Constraint: never place a larger disc on a smaller one. Minimum moves = 2^N - 1. With 64 discs at 1 move/sec it would take 585 billion years.
About the Tower of Hanoi
The Tower of Hanoi is a mathematical puzzle invented by the French mathematician Edouard Lucas in 1883. You start with a stack of discs of decreasing size on the left peg and must move the whole stack to the right peg, using a middle peg as a helper. Two rules constrain every move: you may only move one disc at a time, taking the top disc off a peg, and you may never place a larger disc on top of a smaller one.
The puzzle is a classic teaching example for recursion and exponential growth. Lucas wrapped it in a legend about monks moving 64 golden discs, claiming the world would end when they finished. With 64 discs the minimum number of moves is so vast that even at one move per second it would take longer than the current age of the universe, which is exactly the point of the story.
How it works: the recursive solution
The minimum number of moves follows a simple exponential formula, and the solution itself is naturally recursive: to move N discs, first move the top N-1, then the biggest disc, then the N-1 stack again.
Minimum moves for N discs M(N) = 2^N - 1 Recursive strategy to move N discs from A to C using B: 1. Move the top N-1 discs from A to B (using C as helper) 2. Move the largest disc from A to C 3. Move the N-1 discs from B to C (using A as helper) Examples: 3 discs -> 2^3 - 1 = 7 moves 5 discs -> 2^5 - 1 = 31 moves 7 discs -> 2^7 - 1 = 127 moves 64 discs -> 2^64 - 1 = 18,446,744,073,709,551,615 moves
Each extra disc roughly doubles the work, which is why the move count explodes so quickly. The counter on this page shows the minimum for your chosen disc count so you can measure yourself against the optimal solution.
Worked example: solving 3 discs
With three discs labelled 1 (smallest) to 3 (largest) on peg A, the goal is to reach peg C in the optimal 7 moves.
- Move disc 1 from A to C.
- Move disc 2 from A to B.
- Move disc 1 from C to B (now 1 sits on 2).
- Move disc 3 from A to C (the largest is placed).
- Move disc 1 from B to A.
- Move disc 2 from B to C.
- Move disc 1 from A to C. Solved.
Move-count reference
The minimum moves and the time to solve at one move per second.
| Discs | Minimum moves (2^N - 1) | Time at 1 move/sec |
|---|---|---|
| 3 | 7 | 7 seconds |
| 4 | 15 | 15 seconds |
| 5 | 31 | 31 seconds |
| 6 | 63 | about 1 minute |
| 7 | 127 | about 2 minutes |
| 20 | 1,048,575 | about 12 days |
| 64 | 18.4 quintillion | about 585 billion years |
Common pitfalls
- Placing a big disc on a small one. The single hard rule. The game blocks the move, but planning around it is the whole challenge.
- Forgetting the helper peg. You cannot move a tall stack directly. The middle peg must temporarily hold most of the discs on the way across.
- Moving the same disc twice in a row. Shuffling the top disc back and forth wastes moves and never makes progress toward the optimal count.
- Aiming the largest disc at the wrong peg. The biggest disc only ever moves once in an optimal solve, and it must land on the destination peg, not the helper.
- Ignoring the odd-even rule. With an odd number of discs the first move of the smallest disc goes toward the target peg; with an even number it goes toward the helper. Getting this backward doubles your effort.
- Confusing fewest moves with fastest clicks. Solving it at all is good; solving it in exactly 2^N - 1 moves is the real benchmark.
Frequently asked questions
What is the minimum number of moves to solve the Tower of Hanoi?
For N discs the minimum is 2 to the power N, minus 1. So 3 discs take 7 moves, 5 discs take 31, and 7 discs take 127. There is no shorter solution; any sequence that solves the puzzle in fewer moves would have to break one of the two rules.
Why does the legend say 64 discs would end the world?
Because 2 to the power 64 minus 1 is about 18.4 quintillion moves. Even at one move per second without a single mistake, finishing would take roughly 585 billion years, far longer than the age of the universe. The legend is a vivid way to illustrate exponential growth, not a real prophecy.
Is there a simple strategy that always works?
Yes. Always move the smallest disc in the same rotational direction every turn, and on every other turn make the only legal move that does not involve the smallest disc. Alternating these two moves solves the puzzle optimally for any number of discs. The recursive method (move N-1, move the big disc, move N-1 again) is the formal version.
How do I move a disc in this game?
Click a peg to pick up its top disc, which lifts to show it is selected, then click the destination peg to drop it. If the move would place a larger disc on a smaller one, the game refuses it and shows a brief warning. Use the disc selector to set the difficulty from 3 to 7 discs.
What does the puzzle teach in computer science?
It is the textbook introduction to recursion: the solution for N discs is defined in terms of the solution for N-1 discs. It also demonstrates exponential time complexity, since the number of steps grows as 2 to the power N, making it a memorable example of why exponential algorithms become infeasible quickly.