Tower of Hanoi
A local rule solves it optimally with no planning — but reverse one bit of it and it never solves the puzzle at all.
A rule that solves it with no planning at all
Everyone learns Hanoi as a recursion: move n−1 discs out of the way, move the big one, move them back. That is correct and it is not how you would play it at a table, because you cannot hold a recursion in your head while moving wooden discs.
There is a purely local rule that produces the same optimal sequence, move for move:
- On odd-numbered moves, move the smallest disc one step around a fixed cycle of the three pegs.
- On even-numbered moves, make the only legal move that does not involve the smallest disc. There is always exactly one, so there is nothing to decide.
That is the whole method. It never looks further than the tops of the pegs and whether the move number is odd or even, and it produces the optimal solution for any number of discs.
And the direction depends on the parity of the disc count
With an odd number of discs the smallest goes start → target → spare. With an even number it goes start → spare → target. Get that backwards and the rule does not merely take longer or finish on the wrong peg — checked against the recursive solution for every disc count this page offers, the correct convention matches every time and the reversed one never solves the puzzle at all.
It is a satisfying failure mode: one bit wrong and a rule that is otherwise exactly right produces nothing but a shuffle. Both conventions are pinned in the tests so it cannot come back.
Why the legend takes so long
| Discs | Optimal moves | At one a second |
|---|---|---|
| 3 | 7 | 7 seconds |
| 4 | 15 | 15 seconds |
| 5 | 31 | 31 seconds |
| 8 | 255 | 4.3 minutes |
| 12 | 4,095 | 1.1 hours |
| 20 | 1,048,575 | 12.1 days |
| 64 | 18,446,744,073,709,552,000 | 5.85e+11 years |
The temple legend has 64 discs and monks moving one a second. That is 2⁶⁴ − 1 moves — about 585 billion years, some forty times the age of the universe. The story is usually told as though the monks are nearly finished.
How to use
- Click a peg to pick up its top disc, then click where it goes.
- A larger disc may never sit on a smaller one.
- Use the hint to see the next optimal move and why the rule chose it.
- Move every disc to the right-hand peg.
Frequently asked questions
What is the minimum number of moves for Tower of Hanoi?
Exactly 2 to the power n, minus one. Three discs take seven moves, four take fifteen, eight take 255. There is no shorter solution and the puzzle has exactly one optimal path.
Is there a way to solve Hanoi without recursion?
Yes, and it produces the identical optimal sequence. On odd-numbered moves, move the smallest disc one step around a fixed cycle of the three pegs. On even-numbered moves, make the only legal move that does not involve the smallest disc — there is always exactly one, so there is nothing to decide.
Which way does the smallest disc move?
It depends on whether the number of discs is odd or even. With an odd count it goes start, then target, then spare; with an even count it goes start, then spare, then target. That single bit is the whole rule.
What happens if I get the direction backwards?
The puzzle never gets solved. Checked against the recursive solution for every disc count this page offers, the correct convention matches every time and the reversed one solves none of them. It does not take longer or finish on the wrong peg — it just shuffles.
Why does the temple legend take so long?
Because it uses 64 discs, and 2 to the 64 minus one moves at one a second is about 585 billion years — some forty times the age of the universe. The story is usually told as though the monks are nearly finished.
How do I know how many moves I have left?
Work down from the largest disc: if it is not yet on the target peg it must move once, and everything above it must clear first. That gives an exact count from any legal position, which the tool shows as you play.
Is the optimal solution unique?
Yes. There is exactly one shortest sequence, which is why the local rule can produce it without ever choosing between alternatives — at every point there is only one move that keeps you on the optimal path.
Does this send anything anywhere?
No. Everything runs in your browser and nothing is stored or uploaded.
🔒 This tool runs entirely in your browser. Nothing you enter is uploaded, logged, or stored.