Skip to content

Tower of Hanoi, Binary and Gray Code

Count from zero in binary and you have solved the Tower of Hanoi. Watch the bits and the board move together.

Here is the three-disk solution, with each move’s number written in binary beside it.

MoveIn binaryDiskFrom → to
10011A → C
20102A → B
30111C → B
41003A → C
51011B → A
61102B → C
71111A → C
  1. Move 1 is 001 in binary. Its lowest 1 is bit 0, so it moves disk 1, from A to C.
  2. Move 2 is 010 in binary. Its lowest 1 is bit 1, so it moves disk 2, from A to B.
  3. Move 3 is 011 in binary. Its lowest 1 is bit 0, so it moves disk 1, from C to B.
  4. Move 4 is 100 in binary. Its lowest 1 is bit 2, so it moves disk 3, from A to C.
  5. Move 5 is 101 in binary. Its lowest 1 is bit 0, so it moves disk 1, from B to A.
  6. Move 6 is 110 in binary. Its lowest 1 is bit 1, so it moves disk 2, from B to C.
  7. Move 7 is 111 in binary. Its lowest 1 is bit 0, so it moves disk 1, from A to C.
The move numbers of the three-disk puzzle, counting up in binary, with the lowest 1 in each row marked — the bit that has just switched on. Its column is the disk that moves, so reading the marks down the page gives the disks in order. Notice the row at move 4: it is the only one that reaches the top bit, and the bracketed groups above and below it are the same three rows. That is the recursion, in a counter that knows nothing about towers.

Look at where each binary number’s last 1 is. Moves ending in 1 — every odd move — are disk 1. Moves ending in 10 are disk 2. The one move ending in 100 is disk 3. The disk that moves is one more than the number of zeros at the end of the move number, and that holds for every move of every size of the puzzle.

Why a counter

Adding one to a binary number turns the trailing 1s into 0s and the first 0 above them into a 1. So on step m exactly one bit switches on, and it is bit number z, where z is the number of trailing zeros in m. Bit 0 switches on every other step, bit 1 every fourth, bit 2 every eighth.

The disks keep exactly that schedule. Disk 1 moves on every odd move. Disk 2 first moves on move 2 and then every fourth move. Disk k first moves on move 2ᵏ⁻¹ and then every 2ᵏ moves — the moment bit k − 1 switches on. The reason is the shape of the recursion: the first half of an n-disk solution is the (n − 1)-disk solution, move 2ⁿ⁻¹ is the largest disk, and the second half is the (n − 1)-disk solution again. In binary, the first half counts through the lower bits, move 2ⁿ⁻¹ sets the top bit for the first and only time, and the second half counts through the lower bits again underneath it.

Step through it. The table under the board is the move number in binary, one column per disk with the largest on the left, and the column that lights up is the disk that just moved.

4 disks on tower A. 15 moves to go.Step 0 of 15

Disk4321
Move in binary0000
Gray code0000

Before the first move the counter reads 0: every bit is off, and every disk is on tower A.

The move number in binary and in Gray code. In the binary row several bits can change at once; in the Gray code row exactly one does, and it is always the lit column.

The Gray code

Binary counting has an awkward habit: going from 7 to 8 changes four bits at once, 0111 to 1000. The reflected binary Gray code is an ordering of the same numbers in which each one differs from the last in exactly one bit. It is easy to compute — the Gray code of m is m XOR (m shifted right by one) — and it is named after Frank Gray of Bell Labs, whose patent on it was granted in 1953. The idea is older: in 1872 Louis Gros used the same sequence to describe the solution of the Chinese rings puzzle.

The Tower of Hanoi moves one disk per move, and the Gray code changes one bit per step, and the two line up exactly. The bit that the Gray code changes on step m is the bit of the disk that moves on move m. Follow the Gray code row on the board above and the single changing bit tracks the moving disk the whole way through.

That makes each bit of the Gray code a small record of its disk. Because a bit flips every time its disk moves, and every bit starts at 0, bit k − 1 of the Gray code is 1 exactly when disk k has moved an odd number of times so far.

Reading the towers off the bits

The disk is not the only thing the move number gives away. For move m, with the three towers numbered 0, 1 and 2:

source = (m AND (m − 1)) mod 3destination = ((m OR (m − 1)) + 1) mod 3Towers 0, 1, 2 are A, B, C for an odd number of disks, and A, C, B for an even number.

Try move 5 of the three-disk game. m = 5 is 101 and m − 1 = 4 is 100. 101 AND 100 is 100, which is 4, and 4 mod 3 is 1: tower B. 101 OR 100 is 101, which is 5, plus one is 6, and 6 mod 3 is 0: tower A. The table above agrees — move 5 is disk 1, B → A.

The swap for an even number of disks is the same fact that makes the smallest disk circle the other way round. Every disk circles the towers in one fixed direction for the whole game, alternating direction from one disk size to the next, so after m moves a disk’s tower is simply how many steps it has taken, taken mod 3. Disk k has taken ⌊(m + 2ᵏ⁻¹) / 2ᵏ⌋ steps.

These formulas never look at the board. They are how the C listing prints the solution with no recursion and no towers in memory, and how the board on the 64-disk page knows where the small disks would be after billions of moves without playing a single one of them.

Frequently asked questions

How is the Tower of Hanoi related to binary numbers?

Number the moves of the shortest solution 1, 2, 3 and so on, and write each number in binary. The disk that moves on move m is one more than the number of zeros at the right-hand end of m. Every odd move is disk 1, moves ending in 10 are disk 2, moves ending in 100 are disk 3, and so on — so the whole solution is a binary counter counting up from 0 to 2ⁿ − 1.

What is the connection between the Tower of Hanoi and Gray code?

The reflected binary Gray code changes exactly one bit between each number and the next, and in the Tower of Hanoi exactly one disk moves on each move. They line up exactly: the bit the Gray code changes on step m is the bit for the disk that moves on move m. Each bit of the Gray code also records whether its disk has moved an odd number of times.

How do you find which disk moves on move m of Tower of Hanoi?

Count the zeros at the end of m in binary and add one. Move 12 is 1100 in binary, which ends in two zeros, so move 12 is disk 3. This works at any size, without playing any of the earlier moves.

Can you work out move m without the moves before it?

Yes, completely. The disk is one more than the number of trailing zeros of m, the source tower is (m AND (m − 1)) mod 3 and the destination is ((m OR (m − 1)) + 1) mod 3, with the towers numbered 0, 1, 2 as A, B, C for an odd number of disks and A, C, B for an even number.

Keep reading