There is no strategy to discover here and no opponent to outwit. The shortest solution for n discs is 2ⁿ−1 moves, it has been provable since the 1880s, and you can look it up in a second.
That is exactly what makes it worth playing. The number on the counter is not a score to beat — it is a statement about you. Seven discs take 127 moves. If you take 140, the puzzle has told you something precise about how well you are holding a plan in your head.
How to play Towers of Hanoi
Move the whole tower from A to C. One disc at a time, and never a larger disc onto a smaller one. Click a peg to lift its top disc, click another to put it down.
That is the entire rule set, and it has not changed since 1883.
The counter above the board does the interesting part. It knows the shortest route from wherever you are — not from the start, from here — so the moment you make a move that cannot be part of a shortest solution, it stops saying still optimal and starts counting what you have thrown away. You do not have to finish to find out that you went wrong.
What is the minimum number of moves?
The proof fits in three sentences, and it is the reason this puzzle is on every first-year computing course.
The largest disc has to move at some point. Before it can, all n−1 smaller discs must be somewhere else, and there is only one other peg they can all be on — so they must first be stacked, in order, on the spare peg. After the big disc moves, that stack has to be rebuilt on top of it.
So solving n discs costs twice the price of solving n−1 plus one move for the big disc:
2 × (2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1
One disc takes one move. Everything else follows. And because each of those steps was forced — there was no choice about stacking the small discs on the spare peg — the count is not just achievable but minimal.
How to solve Towers of Hanoi step by step
There is a way to solve it without planning anything, and we checked it against the solver for every size on this page:
- On every odd-numbered move — the 1st, 3rd, 5th and so on — move the smallest disc, always in the same direction round the pegs.
- On every even-numbered move there is exactly one legal move that does not touch the smallest disc. Make it.
The direction depends on the parity of the disc count. With an odd number of discs the small one cycles A → C → B; with an even number, A → B → C. Follow that blindly and you arrive at 2ⁿ−1 without ever holding a plan.
Which is the second thing this puzzle teaches: a problem that looks like it needs recursion can often be run as a loop, and the loop is the one a machine would rather have.
Towers of Hanoi and the Sierpiński triangle
This is the part that turns a first-year exercise into something worth staring at.
Take every position the puzzle can be in — each disc is on one of three pegs, so there are 3ⁿ of them, and all of them are reachable. Draw each as a dot. Join two dots whenever one legal move takes you between them.
Nobody arranged that. The biggest disc decides which third of the triangle you are in, the next disc decides which third of that third, and so on down — which is precisely the recipe for constructing a Sierpiński triangle.
The highlighted line in the big picture is the shortest solution, and its shape is the recursion again. It crosses 1 + 2 + 4 + 8 + 16 + 32 = 63 edges — one long jump, then two of half that length, then four, and so on. It also never once passes through the third corner, which is the position with every disc on the middle peg: the fastest route past a place you never visit.
How long would 64 discs take?
The story arrived with the puzzle. In a temple, priests are moving 64 golden discs between three diamond needles under the same rule, and when they finish, the world ends.
They will finish after 18,446,744,073,709,551,615 moves. At one move per second that is 584 billion years, against a universe currently about 13.8 billion years old. There is no urgency.
The number is the same one that appears in the wheat-and-chessboard story, for the same reason: doubling sixty-four times is a bigger number than people are built to imagine, and both stories exist to make that felt rather than stated.
Who invented Towers of Hanoi?
Édouard Lucas invented the puzzle in 1883 and sold it as a toy under the pseudonym N. Claus de Siam — an anagram of Lucas d'Amiens, and a small joke about a mathematician from Amiens pretending to be a mandarin. He is better remembered for the Lucas numbers and for the primality test named after him, which held the record for finding large primes for most of the twentieth century.
The four-peg version is a useful reminder of how lucky the three-peg case is. Frame and Stewart conjectured a formula in 1941; it was not proved optimal for four pegs until Thierry Bousch did it in 2014. For five pegs and beyond, nobody knows. The clean answer you get here is the exception.
What to try on this board
Start at four discs and get to 15 without the counter turning red. Then move up until you cannot. Most people hold it together to six or seven and come apart somewhere around eight, which is 255 moves and about the point where you have to stop tracking discs and start trusting the pattern.
Then press Explain each move and let it name the recursion step behind every single move, or set the solver going slowly and simply watch. The sub-tower shuttling back and forth is the same shape as the picture above, and once you have seen the connection it is quite hard to unsee.
