Tower of Hanoi

The Tower of Hanoi puzzle: move the whole stack of discs from peg A to another peg by the rules. Solve it yourself, or watch the automatic solution and the move list, for example in a lesson on recursion.

How to use

1. Choose the number of "Discs", from 3 to 10.
2. Drag the top disc to another peg, or tap a peg to pick up its top disc and tap another peg to put it down. Keys 1, 2 and 3 also work.
3. Press "Undo" to take back a move, or "Start over" to begin again.
4. If you are stuck, press "Show the solution" to watch it from the current position. You can change the "Speed", or press "Pause" and use "One step".

How it works

• The rules: move one disc at a time, move only the top disc of a peg, and never place a larger disc on a smaller one.
• The fewest possible moves is 2ⁿ − 1 for n discs. To move n discs, you move n − 1 discs aside, move the largest disc once, then move the n − 1 discs back on top.
• The best record for each number of discs is saved in this browser. Games that used the automatic solution are not recorded.

Questions and answers

What is the minimum number of moves for the Tower of Hanoi?

For n discs it is 2ⁿ − 1: 7 moves for 3 discs, 15 for 4, 31 for 5 and 1,023 for 10.

Is there a simple method to solve the Tower of Hanoi?

On every odd-numbered move, move the smallest disc one peg onward, always in the same direction. On every even-numbered move, make the only legal move that does not use the smallest disc.

Why is the Tower of Hanoi used to teach recursion?

The solution for n discs is made of two solutions for n − 1 discs plus one move of the largest disc, so T(n) = 2·T(n − 1) + 1.

Can I see all the moves at once?

Open "Solution move list" to see every move in the form "Disc 1: A → C".