Tower of Hanoi

How to play the Tower of Hanoi

The puzzle has three pegs and a stack of discs of different sizes, piled on the first peg from largest at the bottom to smallest at the top. Your goal is to move the whole stack to the third peg. There are only two rules:

1. You may move one disc at a time, taking it from the top of a stack.
2. A disc may never be placed on a smaller disc.

Tap a peg to lift its top disc, then tap the peg you want to drop it on. Tap the same peg again to put it back. The move counter shows how many moves you have made and the shortest possible number for your tower. Finish in exactly that many and you have found the perfect solution.

The shortest solution: 2ⁿ − 1 moves

The puzzle has a beautiful recursive answer. To move a tower of n discs from peg 1 to peg 3:

1. Move the top n − 1 discs out of the way, onto peg 2.
2. Move the largest disc to peg 3.
3. Move the n − 1 discs from peg 2 onto peg 3, on top of it.

Steps 1 and 3 are the same puzzle with one disc fewer, so the number of moves doubles, plus one, with every disc you add: 1, 3, 7, 15, 31, 63, 127, 255. In general, a tower of n discs needs 2ⁿ − 1 moves, and no solution can be shorter. Press Show solution to watch it play out.

A rule you can follow without thinking

There is also a simple step-by-step method. Alternate between two kinds of move:

• Odd-numbered moves: move the smallest disc one peg along, always in the same direction. With an even number of discs it travels 1 → 2 → 3 → 1; with an odd number it travels 1 → 3 → 2 → 1.
• Even-numbered moves: make the only legal move that doesn't involve the smallest disc. There is always exactly one.

Follow those two rules and you will finish in the minimum number of moves every time. There is even a link to binary counting: on move number m, the disc that moves is given by how many times 2 divides into m. The smallest disc moves on every odd move, the second disc on moves 2, 6, 10 and so on.

The history and the legend

The Tower of Hanoi was invented by the French mathematician Édouard Lucas and sold as a toy in 1883 under the playful name "N. Claus de Siam", an anagram of "Lucas d'Amiens". It came with a legend: in a great temple, priests move a tower of 64 golden discs according to these same rules, and when they finish, the world will end.

The legend is safe for a while. A tower of 64 discs needs 2⁶⁴ − 1 moves, a little over 18 quintillion. At one move per second, without a single mistake, that would take roughly 585 billion years, many times the current age of the universe. The puzzle has since become a favourite example in teaching recursion in mathematics and computer programming, and it is used in psychology to study planning.

Frequently asked questions

What is the minimum number of moves?

For a tower of n discs the minimum is 2ⁿ − 1 moves: 7 for 3 discs, 15 for 4, 31 for 5, 63 for 6, 127 for 7 and 255 for 8.

Do I have to move the tower to the third peg?

Yes, here the goal is peg 3, the one on the right. The middle peg is your spare. The shortest solution is the same length either way.

Does undo count as a move?

No. Undo takes your last move back and reduces the move count by one, so you can explore without penalty.

What does the best score mean?

Your best is the largest tower you have solved. Start with 3 or 4 discs and work up. Solving 8 discs, in 255 moves or more, is a real test of patience and planning.

Is it free?

Yes, completely free with no sign-up. Your progress is saved in your browser, on your own device.