Tower of Hanoi

8/9/2020 tech

A few weeks ago, I was invited to a friend's house. On the table I saw the Tower of Hanoi game. I immediately realized with intuition that the total number of steps to move should be exponential to the number of disks, but I could not think of a proof at the time. Thus, I write this blog about this interesting ancient problem.

TODO: will publish when the references are explored.

# Origin

French mathematician Édouard Lucas invented this puzzle in 1883. Some legend said that in a temple there were three rods and 64 disks. When the last move of the puzzle is completed, the world will end. The location of the temple or monastery was various and said to be in different parts of the world, including Hanoi, Vietnam, hence the name of the puzzle.

# Problem

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3. No disk may be placed on top of a smaller disk.

# Solution

Let's say the 3 rods are called A, B, C. At first, n=4n=4, from_rod = A, to_rod = B, aux_rod = C. For every nn disks, our strategy is to first move all n1n-1 disks from A to B, move the nnth disk from A to C, and at last move n1n-1 disks from B to C. To move the n1n-1 disks from A to B, we should first move n2n-2 disks from A to C, move the n1n-1th disk from A to B, and at last move n2n-2 disks from C to B. We follow such pattern recursively, until there is only 1 disk left. As the following code shows:

# Recursion

def TowerOfHanoi(n , from_rod, to_rod, aux_rod):
    if n == 1:
        print("Move disk 1 from rod",from_rod,"to rod",to_rod)
    return TowerOfHanoi(n-1, from_rod, aux_rod, to_rod)
    print("Move disk",n,"from rod",from_rod,"to rod",to_rod)
    TowerOfHanoi(n-1, aux_rod, to_rod, from_rod)
1
2
3
4
5
6

# Driver code

n = 4 # can be any positive integer
TowerOfHanoi(n, 'A', 'C', 'B')
1
2

# Proof for Exponential Number of Steps

Let hnh_n be the number of steps with nn disks. Given the recursive function and initial condition:

hn=2hn1+1h_n = 2h_{n-1} + 1
h1=1h_1 = 1

the above two equations give hn=2n1h_n = 2^n - 1, i.e., the Mersenne numbers (opens new window).

hn=2hn1+1=2(2hn2+1)+1substitute the above 2 equations=2n1++20=2n1 \begin{aligned} h_n &= 2h_{n-1} + 1 \\ &= 2(2h_{n-2} + 1) + 1 \\ \text{substitute the above 2 equations} \rightarrow &= 2^{n-1} + \cdots + 2^0 \\ &= 2^n -1 \end{aligned}

The result can also be proofed by induction.

Now come back to the legend. If the priests were able to move disks at a rate of one per second, using the smallest number of moves it would take them 26412^{64} − 1 seconds, or roughly 585 billion years, to finish, which is about 42 times the current age of the universe.

# Further

Following are interesting ways to go deeper but I am good for now.

  • Iterative solutions
  • Relation to Hamiltonian path
  • Solutions to more than 3 rods

# References

The Chinese wikipedia explanation (opens new window) is more succinct and insightful than the English one (opens new window).

This geeksforgeeks post (opens new window) offers the recursive solution code above with a pretty good descriptive video.

Wolfram Mathworld (opens new window) gives some math insights about the proof.