Tower of Hanoi with 4 Disks

Four disks need 15 moves, more than twice as many as three. It is the size where trial and error starts to fail and a rule begins to pay off.

Quick facts

Four is even, so the smallest disk goes to the middle peg first, the opposite of the three-disk case. Sending it the wrong way is the most common mistake: the tower ends up on peg 2 instead of peg 3.

How often each disk moves

The smallest disk does half of all the work. Each disk moves half as often as the one below it, and the largest disk moves exactly once.

A pattern worth remembering

Count how many times 2 divides the move number, and add one: that is the disk to move. Move 1 is odd, so it moves disk 1. Move 2 is divisible by 2 once, so it moves disk 2. Move 4 is divisible by 2 twice, so it moves disk 3. Move 8 is divisible by 2 exactly 3 times, so it is the one move of disk 4. You can check every line of the list below against it.

The complete solution

All 15 moves, in order. Peg numbers are 1 (left), 2 (middle) and 3 (right).

1. Disk 1: peg 1 → 2
2. Disk 2: peg 1 → 3
3. Disk 1: peg 2 → 3
4. Disk 3: peg 1 → 2
5. Disk 1: peg 3 → 1
6. Disk 2: peg 3 → 2
7. Disk 1: peg 1 → 2
8. Disk 4: peg 1 → 3
9. Disk 1: peg 2 → 3
10. Disk 2: peg 2 → 1
11. Disk 1: peg 3 → 1
12. Disk 3: peg 2 → 3
13. Disk 1: peg 1 → 2
14. Disk 2: peg 1 → 3
15. Disk 1: peg 2 → 3

Other sizes

3 disks5 disks6 disks For the rule behind these lists see how to solve the Tower of Hanoi; for why 4 disks need 15 moves see the formula; to finish a position that has gone wrong, use the solver.