How to solve the Tower of Hanoi
Three pegs stand in a row. A tower of discs sits on the first, the biggest at the bottom and each one above it smaller. Move the whole tower to the third peg.
The rules
- Move one disc at a time: the top disc of any peg.
- Put it on another peg, either empty or topped by a bigger disc.
- Never put a bigger disc on a smaller one.
Tap a peg to lift its top disc, then tap the peg you want it on. On a keyboard, the keys 1, 2 and 3 lift and put down, and Z takes a move back.
The fewest moves
A tower of n discs takes at least 2n − 1 moves. Every extra disc doubles the work and adds one.
- 3 discs: 7 moves
- 4 discs: 15 moves
- 5 discs: 31 moves
- 6 discs: 63 moves
- 7 discs: 127 moves
- 8 discs: 255 moves
The count at the top shows your moves and the fewest still to go from where you are.
The plan
To move a tower of 5 discs from peg 1 to peg 3, the biggest disc has to get from peg 1 to peg 3 in one move, and for that the four discs above it must all be on peg 2. So the plan is:
- Move the top four discs to peg 2, using peg 3 to help.
- Move disc 5 to peg 3.
- Move the four discs from peg 2 onto it, using peg 1 to help.
Moving four discs is the same puzzle with one disc fewer, and so on down to disc 1. In a shortest solve each disc moves home once, straight there, at the moment the plan needs it.
Disc 1's rhythm
In a shortest solve the smallest disc moves on every other turn, always the same way round. With an odd number of discs it goes peg 1, 3, 2, 1; with an even number, peg 1, 2, 3, 1. On the turns in between there is only ever one legal move that does not touch disc 1. Follow those two rules and the tower solves itself in the fewest moves.
The solution, move by move: all 15 moves for 4 discs
The owl
The owl names the next step of the plan: which disc moves next, and where. If a move adds extra moves, it says how many and which move would have kept you on the shortest solution. When the tower is finished, it lists the moves that took you off it.