How to Solve the Tower of Hanoi
There is a short recipe that solves the puzzle for any number of disks. Here are two ways to see it: a rule you can follow on autopilot, and the idea that explains why it works.
The puzzle in 30 seconds
There are three pegs and a tower of disks, largest at the bottom, on peg 1. The goal is to move the whole tower to peg 3. You may move one disk at a time, only the top disk of a peg, and never place a disk on a smaller one.
- Moves
- 0
- Minimum
- 7
- Fewest from here
- 7
- Time
- 0:00
Method 1: the smallest-disk rule
This works for any number of disks and needs no planning. First, find out which way the smallest disk travels, which depends only on whether the number of disks is odd or even:
| Number of disks | The smallest disk goes |
|---|---|
| Odd (3, 5, 7, 9) | peg 1 → 3 → 2 → 1 → 3 … |
| Even (4, 6, 8, 10) | peg 1 → 2 → 3 → 1 → 2 … |
Then repeat these two steps until the tower is on peg 3:
- Move the smallest disk one step along its route.
- Make the only legal move that does not involve the smallest disk. There is always exactly one.
You never have to decide anything. Every other move is forced, and the whole puzzle takes exactly the minimum number of moves (see the formula).
Worked example: 3 disks
Three is odd, so the smallest disk (disk 1) goes 1 → 3 → 2 → 1. The seven moves are:
| Move | Disk | From peg | To peg |
|---|---|---|---|
| 1 | 1 | 1 | 3 |
| 2 | 2 | 1 | 2 |
| 3 | 1 | 3 | 2 |
| 4 | 3 | 1 | 3 |
| 5 | 1 | 2 | 1 |
| 6 | 2 | 2 | 3 |
| 7 | 1 | 1 | 3 |
Notice that disk 1 moves on every odd-numbered move, always along the same route, and the other disks fill in the even moves.
Method 2: think recursively
To move a tower of n disks from peg 1 to peg 3:
- Move the top n − 1 disks from peg 1 to peg 2. (This is the same puzzle with one disk fewer.)
- Move the largest disk from peg 1 to peg 3.
- Move the n − 1 disks from peg 2 onto peg 3. (Again the same puzzle, one disk fewer.)
The trick is that step 1 and step 3 are smaller copies of the whole problem, so you can apply the same recipe to them, and so on down to a single disk, which is trivial to move. For 3 disks: move the top 2 disks to peg 2 (that is the 3-move puzzle), move disk 3 to peg 3, and move the 2 disks on top of it.
Stuck halfway? Find the largest disk that is out of place
You do not have to start over after a mistake. Find the largest disk that is not on its goal peg. All smaller disks must gather on the one peg that is neither where that disk is nor where it is going; then it moves; then the smaller disks follow. The solver does exactly this from any position, and shows you the moves.
Common mistakes
- Sending the smallest disk the wrong way. If the tower keeps ending up on peg 2, check whether the number of disks is odd or even and use the matching route.
- Moving the smallest disk twice in a row. It moves on every other move; in between, move a different disk.
- Undoing your last move. Moving a disk back where it came from wastes two moves. If you are about to do that, you are probably missing the forced move.
Where next
See why the minimum is 2n − 1 on the formula page, or let the solver finish a position for you.