Tower of Hanoi — the classic disc puzzle, free in your browser

Five discs sit stacked on the left peg, largest at the bottom. Move the whole stack to the right-hand peg. You may move only 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. That is the entire rule set, and it has been keeping people busy since a French mathematician published it in 1883.

Your score is the number of moves you take, so lower is better. The best possible is 31 — and that is not an estimate, it is provable. Free, no download, and it plays with two taps: one on the peg you are taking from, one on the peg you are putting it on.

How to play

• Tap a peg to lift its top disc, then tap another peg to drop it.
• Tap the same peg again to put the disc back down without spending a move.
• A larger disc can never sit on a smaller one — the move is simply refused.
• Your score is moves. The optimal solution is 31; anything under 40 is a good run.

Why it is exactly 31 — and the two-move rule that gets you there

The reason the minimum is knowable comes from the structure of the problem. To move five discs, you must at some point move the bottom one — and to do that, the four above it have to be sitting on the spare peg, out of the way. So solving five discs means solving four discs, making one move, and then solving four discs again: H(n) = 2·H(n−1) + 1. Starting from H(1) = 1, that gives 1, 3, 7, 15, 31 — one less than a power of two every time. Five discs is 2⁵ − 1 = 31 moves, and no cleverness can beat it, because that recursion is not a strategy, it is a description of what the rules force.

You do not have to think recursively to play it well, though, because there is a mechanical version that never goes wrong. Alternate two kinds of move. On every odd move, move the smallest disc. On every even move, make the only legal move that does not involve the smallest disc — and there is always exactly one. Repeat until the puzzle solves itself in the minimum number of moves.

The one thing to get right is the direction the smallest disc travels: it must always move the same way around the three pegs, and which way depends on whether you have an odd or even number of discs. With five (odd), the small disc cycles left → right → middle → left. That is why your first move has to be onto the right-hand peg — start it the other way and you are still solving the puzzle, just the mirror image of it, and you will land the stack on the wrong peg. And if the recursion has left you wondering about the legend: the version with 64 golden discs, at one move per second, takes about 585 billion years.

More games

More move-counting puzzles: Peg Solitaire, the 15 Puzzle, Lights Out, or Solitaire. Or browse all games.