The Tower of Hanoi has three pegs and a stack of disks in size order. Move one disk at a time, never place a larger disk on a smaller one, and rebuild the stack on another peg. The French mathematician Édouard Lucas published it in 1883, and it is still a standard first example of recursion.
How many moves does it take?
A full stack of n disks takes 2n − 1 moves at minimum. Each extra disk slightly more than doubles the work: you move the smaller stack out of the way, move the new largest disk once, then move the smaller stack back on top of it. We ran the solver at every size below, and its answers match the formula.
| Disks | Minimum moves | Possible positions |
|---|---|---|
| 1 | 1 | 3 |
| 2 | 3 | 9 |
| 3 | 7 | 27 |
| 4 | 15 | 81 |
| 5 | 31 | 243 |
| 6 | 63 | 729 |
| 7 | 127 | 2,187 |
| 8 | 255 | 6,561 |
The puzzle is often told with a legend of 64 golden disks. At one move per second, the 18,446,744,073,709,551,615 moves would take about 585 billion years.
The three-disk solution
Moving a stack of three from peg A to peg C takes these seven moves, and no shorter route exists:
- Move disk 1 from peg A to peg C.
- Move disk 2 from peg A to peg B.
- Move disk 1 from peg C to peg B.
- Move disk 3 from peg A to peg C.
- Move disk 1 from peg B to peg A.
- Move disk 2 from peg B to peg C.
- Move disk 1 from peg A to peg C.
Solving it by hand
The recursive method
To move a stack of n disks, move the top n − 1 disks to the spare peg, move the largest disk to the goal, then move the n − 1 disks onto it. Each smaller stack is the same problem again, so you only ever need to think about the next largest disk that has to move.
The alternating rule
This version needs no planning, which makes it easier to follow by hand:
- Move the smallest disk on every odd-numbered move. It always travels in the same direction around the three pegs. With an odd number of disks, its first move goes straight to the goal peg. With an even number, its first move goes to the spare peg.
- On every even-numbered move, make the only other legal move. Once the smallest disk is set aside, exactly one move is available that does not touch it.
The solver confirms this pattern on every optimal full-stack route from one to eight disks: disk 1 moves on every odd-numbered move and on no even-numbered one.
Starting from the middle of a game
The formula above only covers a full stack. From a mixed position, the distance depends on where the disks are, so a formula is less useful than a search. The solver treats each position as a point on a map, with legal moves as the roads between them, and explores outward in order of distance until it reaches the goal. The first route it finds is therefore a shortest one.
Reaching a full stack from any position never takes more than 2n − 1 moves. A mixed position can never be worse than the full stack on the wrong peg. We confirmed that limit exhaustively for every position at every size from one to eight disks.
Using the solver
Set the number of disks, choose a goal peg and pick a starting peg for each disk. The route updates straight away. Step through it with Previous and Next, or choose Play to watch it run. Controls are standard form fields and buttons, every move is written out as text, and each step is announced to screen readers.
Tower of Hanoi solver questions
What is the minimum number of moves for the Tower of Hanoi?
For a full stack of n disks moving to another peg, the minimum is 2ⁿ − 1 moves: 7 for three disks, 15 for four, 31 for five and 255 for eight.
Can I start from a position that is already partly solved?
Yes. Choose a peg for each disk and the solver finds the shortest route from there. Any arrangement is legal as long as larger disks sit below smaller ones, and the tool always stacks them that way.
Is there more than one shortest route?
Not when every disk ends on one peg. We checked every position with up to eight disks: the route the solver gives is the only one of that length to a full stack.
Why does the solver stop at eight disks?
Eight disks need 255 moves from a full stack, which is about as long as a list worth stepping through. The method itself is not the limit, because the number of positions only grows to 6,561 at eight disks.
Does it handle four pegs?
No. This solver covers the classic three-peg puzzle only. The four-peg version, often called Reve’s puzzle, is a different problem.