When you solve the Tower of Hanoi in the fewest moves, the solution has surprisingly beautiful patterns. Here we introduce, in order, the rules you can find for the fewest-moves solution (2ⁿ − 1 moves) that moves a tower of n disks from the left to the right. The disks are numbered 1, 2, 3… from smallest to largest.

The Number of Times Each Disk Moves Is a Power of 2

In the fewest-moves solution, the number of times each disk moves is fixed. With n disks, disk k moves 2ⁿ⁻ᵏ times.

Disk (with 4 disks)Number of moves
18 times
24 times
32 times
41 time
Total15 times

The largest disk moves once, the next moves twice, the next four times… doubling with each smaller disk. The total is 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1, exactly matching the fewest moves.

The reason is clear from the same idea as the minimum-moves formula. To move n disks, you move a tower of n − 1 disks twice. So the disks smaller than disk n move twice as often as when moving n − 1 disks.

Which Disk Moves on Which Move

For the fewest-moves solution with 4 disks, listing the numbers of the disks that move, from move 1 in order, gives this.

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

Disk 1 appears every other move, 2 in every other gap between them, 3 in every other gap between those, and so on. It has the same shape as the lengths of the marks on a ruler (short, medium, short, long…).

You can find this sequence right away by writing the move number in binary.

MoveBinaryNumber of trailing 0sDisk that moves
1101
21012
31101
410023
510101
611012
711101
8100034

On move m, the disk that moves is the one numbered “the number of trailing 0s when m is written in binary, plus 1”. On odd-numbered moves, the binary number ends in 1, so disk 1 always moves. That is the reason for “on odd-numbered moves, move disk 1” in the article on how to solve it.

The poles to move from and to can also be found with just binary calculations (the algorithm article).

The Connection to Gray Code

When you count in binary from 0, the number of digits that change each time you add one varies (from 0111 to 1000, 4 digits change). A way of writing numbers arranged so that only one digit changes with each step is called “Gray code”.

OrderGray codeDigit that changes (from the right)
0000―
10011
20112
30101
41103
51111
61012
71001

The sequence of changing digits, “1 2 1 3 1 2 1”, is exactly the same as the sequence of disks that move in the Tower of Hanoi. If you see each disk as one binary digit, and think “that digit changes = that disk moves”, the fewest-moves solution of the Tower of Hanoi is the same as following Gray code in order.

The Direction Each Disk Goes Around

The article on how to solve it said that disk 1 always goes around in the same direction. In fact, the other disks have the same rule.

  • The odd-numbered disks (1, 3, 5…) all go around in the same direction as disk 1.
  • The even-numbered disks (2, 4, 6…) all go around in the opposite direction to disk 1.

When moving the left tower to the right, with an odd number of disks, disk 1 goes in the direction “left → right → middle”, and with an even number, “left → middle → right”. No disk ever changes direction until the end.

There is also one more rule, introduced in solving 10 disks. In the fewest-moves solution, you never place an odd-numbered disk directly on an odd-numbered disk, or an even-numbered disk directly on an even-numbered disk.

There Are 3ⁿ Arrangements in All

How many arrangements of the disks are there that follow the rules? Every disk can go on any of the 3 poles, and the order of the disks on the same pole is fixed from largest to smallest, so there are 3ⁿ arrangements.

Number of disksArrangements
3 disks27
5 disks243
7 disks2,187
9 disks19,683

What is more, from any arrangement you can always reach any other arrangement while following the rules. It is also known that if you draw every arrangement as a point and connect the points that are one move apart with lines, you get a figure much like the “Sierpinski triangle”, in which small triangles are nested inside a big triangle.

The Tower of Hanoi app’s Puzzles mode makes its puzzles of matching a target shape from among all these arrangements. Even at 5 stars with 9 disks, it checks the fewest moves for all 19,683 arrangements before posing a puzzle.