Tower of Hanoi: Strategy and Solution
Move a stack of discs from one peg to another, never putting a larger disc on a smaller one. Once you see the pattern, any number of discs is solvable.
Ready to practise? Play Tower of Hanoi Lite free, no sign-up.
1. Know the minimum moves
The fastest solution for n discs takes 2^n - 1 moves: 7 for three discs, 15 for four, 31 for five.
2. Move the smallest disc every other turn
On odd turns, move the smallest disc. On even turns, make the only other legal move.
3. Pick the smallest disc's direction
With an odd number of discs, the smallest disc moves toward the target peg each time. With an even number, it moves toward the spare peg first. It keeps cycling in the same direction.
4. Think in sub-towers
To move n discs, first move the top n-1 discs to the spare peg, move the biggest disc, then move the n-1 discs on top of it. This is the same problem, only smaller.
5. Do not undo the last move
Never move the same disc twice in a row. If you notice yourself doing it, you have taken a wrong turn.
Frequently asked questions
- Why is it 2^n - 1?
- Each extra disc doubles the work and adds one move for the largest disc.
- Is the pattern the same for four discs?
- Yes. The same rule solves any number of discs; only the direction of the smallest disc depends on whether the count is odd or even.