The Tower of Hanoi is solved in the fewest moves by a simple recursive idea: to move a stack of n discs, move the top n − 1 out of the way, move the biggest disc, then move the n − 1 back on top of it. That gives a minimum of 2ⁿ − 1 moves: 7 for three discs, 15 for four and 255 for eight. Below are the full move lists for 3 and 4 discs, a two-line rule that solves any size without thinking recursively, and a table of minimum moves. Try each method on our free Tower of Hanoi, which goes from 3 to 8 discs and has a hint button.
Move only one disc at a time.
Only the top disc of a peg can move.
Never place a larger disc on a smaller one.
Move the whole stack from the first peg (A) to the last peg (C).
Number the discs 1 (smallest) to 3 (largest). Pegs are A (start), B (spare) and C (goal).
Disc 1: A → C
Disc 2: A → B
Disc 1: C → B
Disc 3: A → C
Disc 1: B → A
Disc 2: B → C
Disc 1: A → C
Moves 1 to 3 move the top two discs to B, move 4 puts the biggest disc on C, and moves 5 to 7 move the two-disc stack from B onto it. That is the recursive idea in action.
With an even number of discs the smallest disc's first move goes to the spare peg, not the goal. The full sequence:
Moves 1 to 7 are a 3-disc solution to peg B, move 8 moves the largest disc, and moves 9 to 15 are a 3-disc solution from B to C.
| Move | Disc | From → To |
|---|---|---|
| 1 | 1 | A → B |
| 2 | 2 | A → C |
| 3 | 1 | B → C |
| 4 | 3 | A → B |
| 5 | 1 | C → A |
| 6 | 2 | C → B |
| 7 | 1 | A → B |
| 8 | 4 | A → C |
| 9 | 1 | B → C |
| 10 | 2 | B → A |
| 11 | 1 | C → A |
| 12 | 3 | B → C |
| 13 | 1 | A → B |
| 14 | 2 | A → C |
| 15 | 1 | B → C |
You do not need to think recursively. Alternate between two kinds of move:
Odd moves: move the smallest disc one peg along in a fixed direction. With an odd number of discs go A → C → B → A; with an even number go A → B → C → A.
Even moves: make the only legal move that does not involve the smallest disc. There is always exactly one.
Repeat until the stack is on C. This gives the minimum solution every time, for any number of discs, and it is the easiest method to use on 6, 7 or 8 discs in our game.
The 64-disc line comes from the legend attached to the puzzle when the French mathematician Édouard Lucas published it in 1883: monks moving 64 golden discs would end the world when they finished. At one move a second, that would take far longer than the age of the universe.
| Discs | Minimum moves | At one move per second |
|---|---|---|
| 3 | 7 | 7 seconds |
| 4 | 15 | 15 seconds |
| 5 | 31 | 31 seconds |
| 6 | 63 | about 1 minute |
| 7 | 127 | about 2 minutes |
| 8 | 255 | about 4 minutes |
| 10 | 1,023 | about 17 minutes |
| 64 | 18,446,744,073,709,551,615 | about 585 billion years |
Call the minimum for n discs M(n). To move n discs you must first clear n − 1 discs off the biggest one (M(n − 1) moves), move the biggest disc (1 move), then put the n − 1 back on top (M(n − 1) moves). So M(n) = 2 × M(n − 1) + 1. Starting from M(1) = 1 gives 1, 3, 7, 15, 31…, which is always one less than a power of two.
This is why the Tower of Hanoi is a standard example of recursion in computer science and a planning test in psychology: you must hold a sub-goal in mind while working towards the main goal. For more puzzles that reward planning, try Lights Out, Knight's Tour and the tile slide puzzle.
2ⁿ − 1, where n is the number of discs: 7 moves for 3 discs, 15 for 4, 31 for 5 and 63 for 6.
Move the smallest disc. With an odd number of discs move it straight to the goal peg; with an even number move it to the spare peg.
A→C, A→B, C→B, A→C, B→A, B→C, A→C, moving the smallest, middle, smallest, largest, smallest, middle, smallest discs in turn.
Yes: on every odd move shift the smallest disc one peg in a fixed direction, and on every even move make the only other legal move.
The French mathematician Édouard Lucas published it in 1883.
Remember the shape of the solution: clear the stack above the biggest disc, move the biggest disc, rebuild on top. Use the odd-even rule on bigger towers and you will hit the minimum 2ⁿ − 1 moves every time. Test it on the free Tower of Hanoi, from 3 up to 8 discs.