The biggest disk needs an empty peg
The biggest disk can only move to an empty peg. Everything above it has to be somewhere else first, and the only somewhere else is the spare peg, the one that is neither start nor goal.
So moving a tower of any size is three jobs. Move the smaller tower above the biggest disk to the spare peg. Move the biggest disk to the goal peg. Move the smaller tower back on top of it.
The middle job is one move. The other two are the same problem again, one disk shorter, which is why the number of moves doubles and adds one each time a disk is added.
Three disks in seven moves
Here are the seven moves, with the pegs numbered 1, 2 and 3 from the left.
Disk 1 to peg 3. Disk 2 to peg 2. Disk 1 to peg 2. Disk 3 to peg 3. Disk 1 to peg 1. Disk 2 to peg 3. Disk 1 to peg 3.
Watch the smallest disk. It moves on every other turn, and it always goes the same way round the three pegs. The moves in between are forced: there is only ever one other legal move.
Which way does the first move go?
In a shortest solution, the smallest disk always travels the same way round. With an odd number of disks it starts towards the goal peg. With an even number it starts towards the spare peg.
Five disks are stacked on the left peg, and every disk has to end on the right peg.
Try it
To move five disks from left to right in the fewest moves, where must the smallest disk move first?
- On the right peg
- On the middle peg
Show the answer
On the right peg
Correct. Five is odd, so the smallest disk starts towards the goal peg and keeps going that way round.
Enable JavaScript to answer interactively and save your place.
Practice Tower of Hanoi