Rubik's Cube & puzzles
How to solve the Tower of Hanoi (and why it takes 2ⁿ − 1 moves)
The Tower of Hanoi explained: the rules, the easy pattern for solving it by hand, the minimum number of moves for 3 to 8 disks, the recursive algorithm, and variants with four pegs.
The Tower of Hanoi is a puzzle of three pegs and a stack of disks, smallest on top. The goal is to move the whole tower to another peg. It was invented by the French mathematician Édouard Lucas in 1883, and it is still the classic example of recursion in maths and computer science.
The rules
- Move one disk at a time.
- Only the top disk of a peg can move.
- A disk may never sit on a smaller disk.
The easy pattern for solving it by hand
You can solve any Tower of Hanoi with two alternating moves:
- Every odd move, move the smallest disk, always one peg in the same direction. With an odd number of disks, go towards the goal peg; with an even number, go the other way round.
- Every even move, make the only legal move that doesn't use the smallest disk.
Repeat until the tower is rebuilt. It feels like a rhythm once you get going.
How many moves does it take?
The fewest moves for n disks is 2ⁿ − 1.
| Disks | Fewest moves |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
Each extra disk doubles the work, plus one. A legend says monks are moving a tower of 64 golden disks; at one move a second, they would need about 585 billion years.
Why 2ⁿ − 1? Thinking recursively
To move a tower of n disks from A to C:
- Move the top n − 1 disks from A to B (a smaller Tower of Hanoi).
- Move the biggest disk from A to C.
- Move the n − 1 disks from B onto C (the same smaller puzzle again).
So the moves for n disks are twice the moves for n − 1, plus one: M(n) = 2·M(n − 1) + 1. Starting from M(1) = 1, that gives 1, 3, 7, 15, 31… which is 2ⁿ − 1. Solving a big problem by solving smaller copies of it is called recursion, and programmers use it every day.
Variants to try
- Neighbour moves only: if disks may only move to the peg next door, you need 3ⁿ − 1 moves (26 for three disks).
- Four pegs (Reve's puzzle): an extra peg makes it much faster. Eight disks take 255 moves on three pegs but only 33 on four.
Play it
Our free Tower of Hanoi game has 24 towers in three tiers: classic towers from 3 to 7 disks, scrambled mid-game starts, and variants with neighbour-only moves and four or five pegs. It shows the best possible number of moves for every level, gives perfect hints, and can play the solution for you.
Common questions
What is the minimum number of moves for 3 disks?
Seven. In general, n disks need 2ⁿ − 1 moves, so 4 disks need 15 and 5 disks need 31.
What is the Tower of Hanoi used to teach?
Recursion, powers of two, planning and pattern spotting. It appears in maths lessons on sequences and in computer science courses on algorithms.
Can the Tower of Hanoi be solved from any starting position?
Yes, as long as no disk is on a smaller one. Our game's tier 2 starts from scrambled positions and tells you the shortest finish.
This guide is general information. For exams, follow your school, teacher and official exam board, and use your own judgement about what suits your child.