Tower of Hanoi: How to Find the Minimum Number of Moves
The Tower of Hanoi looks like a toy, but it hides one of the cleanest patterns in recreational math. NRICH, the mathematics enrichment project at the University of Cambridge, describes the setup: there are three pegs, a stack of discs sits on the first peg in order of size, and the goal is to move the whole stack to another peg. Only one disc can move at a time, and a disc can never sit on top of a smaller disc.
NRICH asks the natural question: what is the smallest number of moves for one, two, three, or four discs, and can you explain the pattern? The answer is below, followed by a method that never gets lost and five original puzzles, each checked by searching every possible sequence of moves.
1. The rules in one place
- Three pegs. Call them A (start), B (spare), and C (target).
- Move one disc at a time, always the top disc of a peg.
- Never place a larger disc on a smaller one.
- Finish with the whole stack on peg C, in the same order.
2. The key idea: the biggest disc moves once
Think about the largest disc. It can only move when every other disc is out of the way, stacked on the spare peg. So any complete solution has three parts:
- Move the smaller stack (everything except the largest disc) from A to B.
- Move the largest disc from A to C. This is a single move.
- Move the smaller stack from B back on top of it at C.
Parts 1 and 3 are each a full Tower of Hanoi with one fewer disc. That gives a simple rule: the moves for n discs equal twice the moves for n minus 1 discs, plus 1. NRICH hints at exactly this when it asks how 3 moves for two discs can tell you the answer for three discs.
3. The numbers
Start with 1 move for one disc and apply the rule:
| Discs | Minimum moves |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
Each total is one less than a power of 2. In general, n discs need 2 to the power n, minus 1, moves. Each extra disc roughly doubles the work.
NRICH's extension mentions a legend of a 64-disc tower. At one move per second, 2 to the power 64 minus 1 seconds is about 584.5 billion years, counting a year as 365.25 days.
4. A method that never gets lost
This routine produces the shortest solution every time:
- Odd and even moves alternate. Every odd-numbered move (1st, 3rd, 5th...) moves the smallest disc. Every even-numbered move moves the only other disc that can legally move.
- The smallest disc always circles in the same direction. With an even number of discs, it goes A to B, B to C, C to A, and repeats. With an odd number of discs, it goes A to C, C to B, B to A, and repeats.
- On even moves there is never a choice. Ignoring the smallest disc, only one legal move exists between the other two pegs.
NRICH's guidance on working systematically recommends recording results in a structured way. Here, numbering each move keeps the odd and even steps straight.
5. Puzzle 1
What is the fewest number of moves to transfer a stack of 6 discs?
6. Puzzle 2
You solve a 4-disc tower from peg A to peg C in the fewest moves. Which disc moves on move 8, and which disc moves on move 12? (Number the discs 1 to 4, with 1 the smallest.)
7. Puzzle 3
In the shortest solution for 5 discs, how many times does the smallest disc move?
8. Puzzle 4
The three discs are scattered. The smallest is on peg C, the middle disc is on peg B, and the largest is on peg A. What is the fewest number of moves to stack all three on peg C?
9. Puzzle 5
A 10-disc tower is solved in the fewest moves at a steady pace of one move per second. How long does it take?
10. Answers
Puzzle 1: 63 moves. That is 2 to the power 6, minus 1.
Puzzle 2: Disc 4 on move 8, and disc 3 on move 12. A 4-disc solution has 15 moves, and the largest disc moves exactly once, right in the middle, which is move 8. Moves 9 to 15 rebuild the 3-disc stack on top of it, and the 3-disc stack's own middle move (its largest disc, disc 3) falls on move 8 + 4 = 12. The full sequence was generated and checked move by move.
Puzzle 3: 16 times. The smallest disc moves on every odd-numbered move. A 5-disc solution has 31 moves, and 16 of them are odd-numbered. Each larger disc moves half as often as the next smaller one, so for 5 discs the counts are 16, 8, 4, 2, and 1, which add up to 31.
Puzzle 4: 5 moves. Move the smallest disc from C onto the middle disc at B. Move the largest disc from A to C. Move the smallest disc from B to A. Move the middle disc from B to C. Move the smallest disc from A to C. A search of every reachable arrangement found no 4-move route, and this 5-move route is the only shortest one.
Puzzle 5: 17 minutes and 3 seconds. Ten discs need 2 to the power 10 minus 1, or 1,023 moves, and 1,023 seconds is 17 minutes plus 3 seconds.
11. Key takeaways
- The largest disc moves exactly once, so n discs take twice the moves of n minus 1 discs, plus 1.
- The minimum for n discs is 2 to the power n, minus 1: 7 for three discs, 15 for four, 63 for six.
- On odd-numbered moves, move the smallest disc in a fixed circular direction set by whether the disc count is odd or even.
- On even-numbered moves, only one other legal move exists, so the method never asks you to guess.
- Each disc moves half as often as the next smaller one, which is why the smallest disc does most of the work.