Tower of Hanoi

What is the Tower of Hanoi?

The Tower of Hanoi is the puzzle the French mathematician Édouard Lucas brought out in Paris in 1883, under the made-up name of "Professor N. Claus de Siam", an anagram of "Lucas d'Amiens". It came as a wooden base with three pegs and a tower of eight discs, and a story to go with it: in a great temple, priests move a tower of 64 golden discs from one diamond needle to another, one disc at a time, never a larger disc on a smaller one, and when they finish, the world ends. Played perfectly, 64 discs take 2^64 - 1 moves, over 18 billion billion: at one move a second, about 585 billion years.

The rules fit in one line: move the whole tower to the target peg, one disc at a time, and never put a larger disc on a smaller one. The fewest moves for a tower of n discs on three pegs is 2^n - 1, so every disc you add doubles the work: 4 discs take 15 moves, 6 take 63, 8 take 255.

Here easy is 4 discs on three pegs, medium 6 discs, and hard is the four-peg version Henry Dudeney set in The Canterbury Puzzles in 1907 as "The Reve's Puzzle": eight cheeses of different sizes on four stools. A fourth peg makes the tower much shorter to move, 33 moves for eight discs, but much harder to see. Every day there is also a Daily tower: six discs scattered over three pegs, the same for everyone, to be gathered on the peg with the gold cap.

How to play

Bring every disc to the peg with the gold cap.

• Tap a peg to lift its top disc: it floats above the peg. Tap another peg to drop it there, or its own peg to set it back down.
• Drag a disc with your finger across to another peg and let go.
• On a keyboard, the keys 1 to 4 pick the pegs, the arrow keys move between them, Escape sets a lifted disc back down.
• The one rule. A disc only goes onto an empty peg or onto a larger disc. Try otherwise and the disc shakes its head, and the smaller disc in the way lights up.
• Stars. Three for the fewest moves the tower needs, two within about a quarter more, one beyond. The stars in the header show the most you can still earn from where you are.
• Undo is there on the easy level and takes your last move back off the count. The clock keeps running.
• Hint. Lifts the disc that a shortest way home moves next and lights the peg it goes to, for 20 seconds on your score.
• Score. Your time from the first move, plus 5 seconds for every move beyond the fewest and 20 seconds for every hint. Lower is better.

Strategy tips

1. Think in towers, not discs. To move a tower of six, first move the five above the largest disc out of the way, onto the third peg, then the largest disc goes across in one move, and the five follow it. Each of those smaller towers moves the same way.
2. The smallest disc moves every other turn. In a perfect solution on three pegs, every second move is the smallest disc, and it always travels round the pegs in the same direction. The move in between is the only legal move that does not touch it.
3. Even or odd decides the first move. With an even number of discs, the smallest disc goes first to the middle peg; with an odd number, straight to the target.
4. Scattered towers: start from the largest. Find the largest disc that is not yet on the target. Everything smaller has to gather on the third peg before it can move, and from then on it is an ordinary tower again.
5. Four pegs: split the tower. Move the top four or five discs aside using all four pegs, carry the rest across with the three pegs still free, then bring the top part home. This is the Frame-Stewart method, and for four pegs it is proven to be the shortest.

FAQ

Is the Tower of Hanoi free to play?

Yes. Like every game on Play, it runs free in your browser, with no download and no account needed.

What is the fewest number of moves?

For n discs on three pegs, 2^n - 1: 15 for four discs, 63 for six. The number shown at the top of the board is the fewest for the tower in front of you, worked out by a search over every position, so it is also right for the scattered Daily tower.

Why does the hard level have four pegs?

Eight discs on three pegs take 255 moves, and once you know the method that is a long walk rather than a puzzle. With four pegs the same eight discs take only 33 moves, but the shortest way is far harder to find. The method was described by J. S. Frame and B. M. Stewart in 1941, and Thierry Bousch proved in 2014 that no shorter way exists for four pegs.

What does the hint do?

It lifts the disc that a shortest way home moves next, from wherever your discs stand, and lights the peg it goes to. Tap the lit peg to make the move. Each hint adds 20 seconds to your score.

What is the daily tower?

Every day everyone gets the same six discs scattered over three pegs, with the same target peg, between 40 and 58 moves from home at the fewest, so times compare directly on the daily leaderboard.