How do you play the Tower of Hanoi?
You win by moving the stack of disks from the left peg to the right peg, one disk at a time, so it ends up in the same order. A bigger disk may never sit on a smaller one.
The French mathematician Édouard Lucas published the puzzle in 1883, and it is still the go-to first example of recursion in math and programming classes.
What are the rules?
- One at a time: you can only move the top disk of a peg.
- Small on big: a disk can go on an empty peg or on a larger disk, never on a smaller one.
- Goal: rebuild the whole tower on peg 3, the right peg.
- Stars: three stars for the fewest possible moves, two for up to 1.5 times that, one for anything more.
What is the minimum number of moves?
With n disks the fewest possible moves is 2n - 1. That is 7 moves for 3 disks and 1,023 for 10.
Think about the biggest disk. Before it can go to the right peg, the n - 1 smaller disks on top of it have to be parked on the middle peg. Then the big disk moves once, and the n - 1 small disks come back on top of it. So n disks take twice the moves for n - 1 disks, plus one. One disk takes 1 move, two take 3, three take 7, four take 15, and the pattern works out to 2n - 1. The biggest disk can only move when every smaller disk is out of the way, so there is no shorter route.
| Disks | Fewest moves |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 9 | 511 |
| 10 | 1,023 |
How do you solve it in the fewest moves?
- Pick the first move by the number of disks. With an odd number, move the smallest disk to the goal peg first. With an even number, move it to the middle peg.
- The smallest disk moves every other turn, always cycling in the same direction.
- On the turns in between there is only one legal move that leaves the smallest disk alone. Make it.
- When lost, think about the biggest disk. To move it, everything above it has to be gathered on one other peg.
How does auto solve work?
It finishes the puzzle from wherever the disks are right now, in the fewest possible moves. You can set the speed from 1x to 16x, and from the start it takes exactly 2n - 1 moves.
It follows the same idea as above. If the biggest disk is not on the goal peg yet, the smaller disks are cleared to the spare peg, the big disk moves, and the smaller disks follow it. Moving the smaller disks repeats the same plan one size down.
Legend says the world ends when monks finish moving a tower of 64 disks. That takes 264 - 1 moves, about 18 quintillion, or roughly 585 billion years at one move per second. Games that used auto solve are not saved as records. Your best result for each number of disks is saved in this browser.