Tower of Hanoi

How to play

All the discs start stacked on the left peg, largest at the bottom. Move them all to another peg. You may move one disc at a time, only the top disc of a peg, and you may never place a larger disc on top of a smaller one. Tap a peg to lift its top disc, then tap the peg you want it on. With n discs the puzzle can always be solved, and the shortest possible solution takes exactly two to the power n, minus one moves.

Tips

• Look at the smallest disc. In an optimal solution it moves on every other turn, always in the same rotational direction.
• Think recursively. To move a stack of five, move the top four out of the way, move the biggest, then move the four back on top.
• With an odd number of discs the first move goes to the target peg; with an even number it goes to the spare peg.
• Never undo your last move. If you are stuck, the position before you moved was not the problem.
• The move counter is the real score. Solving it at all is easy, solving it in the minimum is the puzzle.

The legend and the maths

The Tower of Hanoi was introduced by the French mathematician Edouard Lucas in 1883, along with a story about monks moving 64 golden discs, the world ending when they finish. The story is invented but the maths is real. Moving n discs takes a minimum of two to the power n, minus one, moves: 7 for three discs, 15 for four, 31 for five, and so on. For 64 discs that is over eighteen quintillion moves, which at one move per second is longer than the current age of the universe.

The puzzle is a favourite teaching example for recursion because the solution is so cleanly recursive: to move n discs, move n minus one out of the way, move the biggest, then move the n minus one back on top.

Solving it in the minimum

• The smallest disc moves every other turn, and always in the same rotational direction. Get that rhythm and half the moves are automatic.
• The other move is always forced. Between two non smallest discs, only one legal move exists.
• With an odd number of discs, move the smallest to the target peg first. With an even number, move it to the spare peg.
• Never reverse a move. If you feel stuck, the move you want is the one you have not tried, not the one you just made.
• The optimal count is shown. If your moves exceed it, you have wasted at least one, and undo will not fix it, only a restart will.

Common questions

What is the fewest possible moves?

Two to the power of the number of discs, minus one. Three discs need 7, four need 15, five need 31, seven need 127.

Is there a trick to it?

The smallest disc moves every other turn, always in the same direction, and the remaining move is always forced. Follow that and you hit the minimum.

Why does it matter which peg the first move goes to?

With an odd number of discs the first move goes to the target peg; with an even number, to the spare. Get it wrong and the minimum becomes impossible.