Tower of Hanoi
Move the tower of discs from the first peg to the third, one disc at a time, never putting a larger disc on a smaller one. Can you do it in the fewest possible moves?
How to play
- All the discs start on peg 1, from the largest at the bottom to the smallest on top.
- Each move takes the top disc of one peg and puts it on another.
- A disc can never go on a smaller one. If you try, the game refuses and tells you why.
- You win when the whole tower stands on peg 3, marked goal.
- The counters show your moves and the minimum possible. Match it for a perfect game.
Controls
Tap or click
Tap a peg to lift its top disc, then tap another to drop it there. Tap the same peg again to put the disc back.
Drag
Drag the top disc of a peg and release it over another. Works with a mouse or a finger.
Keyboard
Keys 1, 2 and 3 choose a peg: the first press lifts the disc, the second drops it. U or Backspace undoes the last move and Esc puts a lifted disc back.
Undo and show solution
Undo takes back the last move, as many times as you like. Show solution plays the shortest solution from wherever you are, even after a detour. Using it means the game does not count as a record.
The recursive idea
The trick is to think backwards. To move a 4-disc tower from peg 1 to peg 3:
- Move the top 3 discs to peg 2 (the spare one).
- Move the big disc to peg 3. It is free now.
- Move the 3 discs from peg 2 on top of the big one.
Steps 1 and 3 are the same puzzle with one disc fewer. To move 3 discs you use the same idea with 2, and for 2 with 1. A single disc just moves. That is recursion: solving a problem by leaning on a smaller version of itself, until the case is so simple it solves itself.
From any position the idea is similar: look at the largest disc that is not on the goal peg. All the smaller discs must gather on the spare peg, the large disc moves home, and then the small tower moves on top of it. That is how Show solution works.
The formula 2ⁿ − 1
If moving a tower of n − 1 discs takes M moves, a tower of n takes M + 1 + M: the small tower twice and the big disc once. Starting from 1 disc (1 move) you get 3, 7, 15, 31, 63, 127, 255… Each extra disc doubles the work and adds one: the minimum is 2ⁿ − 1.
- 3 discs: 7 moves
- 4 discs: 15 moves
- 5 discs: 31 moves
- 6 discs: 63 moves
- 7 discs: 127 moves
- 8 discs: 255 moves
A shortcut for playing on autopilot: the smallest disc moves every other turn, always round in the same direction. With an odd number of discs it goes 1 → 3 → 2 → 1…; with an even number, 1 → 2 → 3 → 1… On the other turns there is only one legal move that does not use the smallest disc.
The legend
The puzzle was invented by the French mathematician Édouard Lucas in 1883, and to sell it he told a legend he also made up: in a temple, priests move 64 golden discs between three diamond needles by these same rules, and when they finish, the world will end. No need to worry: 2⁶⁴ − 1 is about 18 quintillion moves. At one per second that would take around 585 billion years, far longer than the age of the universe.
For teachers
The Tower of Hanoi is the classic way to introduce recursion and exponential growth. A few ideas for class:
- Have students solve 3 and 4 discs and record their moves, then discover the 2ⁿ − 1 rule from the table.
- Run Show solution with 4 or 5 discs and ask them to spot when the big disc moves: exactly halfway through.
- Write the recursive function in pseudocode: move(n, from, to, spare).
FAQ
What is the minimum number of moves with 3 discs?
Seven. In general, n discs need 2ⁿ − 1 moves, and it cannot be done in fewer.
Does the solution still work after a mistake?
Yes. Show solution works out the shortest path from the current position, not from the start.
Why won’t it let me drop a disc?
Because it would put a larger disc on a smaller one. The game refuses with a small shake and tells you which discs clash.
Is my record saved?
Yes, in your browser, per number of discs: the fewest moves and the fastest time. If your browser blocks storage, the game still works.