How to Solve the Tower of Hanoi (Fewest Moves)

Move the smallest disk every other move, always in the same direction, to finish in 2ⁿ − 1 moves.

Move the smallest disk every other move, always in the same direction

• Odd number of disks: the smallest disk goes left → right → middle
• Even number of disks: it goes left → middle → right
• On moves 2, 4, 6… make the only move that doesn’t use the smallest disk

3 disks take 7 moves, 4 take 15, 5 take 31

Disks are numbered from the smallest. L, M and R are the left, middle and right pegs.

3 disks (7 moves)

1. 1L → R
2. 2L → M
3. 1R → M
4. 3L → R
5. 1M → L
6. 2M → R
7. 1L → R

4 disks (15 moves)

1. 1L → M
2. 2L → R
3. 1M → R
4. 3L → M
5. 1R → L
6. 2R → M
7. 1L → M
8. 4L → R
9. 1M → R
10. 2M → L
11. 1R → L
12. 3M → R
13. 1L → M
14. 2L → R
15. 1M → R

5 disks (31 moves)

1. 1L → R
2. 2L → M
3. 1R → M
4. 3L → R
5. 1M → L
6. 2M → R
7. 1L → R
8. 4L → M
9. 1R → M
10. 2R → L
11. 1M → L
12. 3R → M
13. 1L → R
14. 2L → M
15. 1R → M
16. 5L → R
17. 1M → L
18. 2M → R
19. 1L → R
20. 3M → L
21. 1R → M
22. 2R → L
23. 1M → L
24. 4M → R
25. 1L → R
26. 2L → M
27. 1R → M
28. 3L → R
29. 1M → L
30. 2M → R
31. 1L → R

Formula: n disks take 2ⁿ − 1 moves (15 for 4 disks)

With n disks, multiply 2 by itself n times and subtract 1.

n disks take twice the moves for n − 1, plus 1

Before the largest disk can move, every disk above it has to be out of the way.

Add 1 to each count and it doubles every time, so n disks take 2ⁿ − 1.

As a recurrence, a_n = 2a_n−1 + 1 becomes a_n + 1 = 2(a_n−1 + 1), so a_n = 2ⁿ − 1.

Recursive algorithm: n − 1 disks, disk n, n − 1 disks

Move the top n − 1 to the spare peg, move disk n, then stack the n − 1 on top of it. In Python:

def hanoi(n, src, dst, via):
    if n == 0:
        return
    hanoi(n - 1, src, via, dst)
    print(n, src, "->", dst)
    hanoi(n - 1, via, dst, src)

hanoi(3, "L", "R", "M")

It prints the 7 moves of the 3-disk answer. The rule at the top is the same, without recursion.

FAQ

Where does the first move go?

With an odd number of disks, the smallest goes to the right peg. With an even number, to the middle.

Can it be done in fewer moves?

No. Before and after the largest disk moves, all the other disks must be stacked on one peg.

Which disk moves on move k?

Write k in binary. The disk is 1 plus the number of zeros at the end: move 4 (100) moves disk 3.

How many times does each disk move?

The smallest makes about half of all moves (2ⁿ⁻¹). Each larger disk moves half as often.

Is there an easy way to remember it?

In the shortest solution, odd-numbered disks never go on odd ones, and even never on even.

How do I solve it from a mixed-up position?

Largest disk not on the right peg: stack the smaller ones on the third peg, move it, repeat.

What if the goal is the middle peg?

The smallest disk goes the opposite way: with an odd number of disks, left → middle → right.

What about four pegs?

At least 1, 3, 5, 9, 13, 17, 25 and 33 moves for 1 to 8 disks (the jumps go 2, 2, 4, 4, 4, 8…).

Can I practice here?

Yes: 3 to 10 disks, plus a daily puzzle of five scattered disks. “Hint” shows the next best move.