Tower of Hanoi

Please view this website for the application:

http://www.mathsisfun.com/games/towerofhanoi.html

Tower of Hanoi

The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks (initially four in the applet below), initially stacked in increasing size on one of three pegs.

The objective: To transfer the entire tower to one of the other pegs (the rightmost one in the applet below), moving only one disk at a time and never a larger one onto a smaller.

This puzzle touches on the topic of recursive function and stacks, and recurrence relations.

Recursive solution

Let us call the three pegs Src (Source), Aux (Auxiliary) and Dst (Destination). As you solve the problem, sooner or later the bottom disk will have to be moved from Src to Dst. Then, the remaining disks will then have to be stacked in decreasing size order on Aux. After moving the bottom disk from Src to Dst these disks will have to be moved from Aux to Dst. Therefore, for a given number N of disks, the problem appears to be solved if we know how to accomplish the following tasks:

1. Move the top disk from Src to Aux (using Dst as an intermediary peg)
2. Move the bottom disk from Src to Dst
3. Move the smallest disk from Aux to Dst (using Src as an intermediary peg)

Suppose there is a function "Solve" with four arguments - number of disks(N) and three pegs (source, intermediary and destination - in this order). Then the body of the function might be as follows:

 Solve(N, Src, Aux, Dst)

if N is 0        exit

else 

Solve(N-1, Src, Dst, Aux)

Move from Src to Dst

Solve(N-1, Aux, Src, Dst) 

This actually serves as the definition of the function Solve. The function is recursive in that it calls itself repeatedly with decreasing values of N until a terminating condition (in this case N=0) has been met. It is indeed amazing how this puzzle could be solve by a method of such simplicity.

When there are 3 disk, the function thus translates into

1. Move from Src to Dst
2. Move from Src to Aux
3. Move from Dst to Aux
4. Move from Src to Dst
5. Move from Aux to Src
6. Move from Aux to Dst
7. Move from Src to Dst

Of course "Move" means moving the topmost disk. For N=4 we get the following sequence

1. Move from Src to Aux
2. Move from Src to Dst
3. Move from Aux to Dst
4. Move from Src to Aux
5. Move from Dst to Src
6. Move from Dst to Aux
7. Move from Src to Aux
8. Move from Src to Dst
9. Move from Aux to Dst
10. Move from Aux to Src
11. Move from Dst to Src
12. Move from Aux to Dst
13. Move from Src to Aux
14. Move from Src to Dst
15. Move from Aux to Dst

Recurrence relations

Let T_N be the minimum number of moves needed to solve the puzzle with N disks. From the previous section, we can see that T₃ and T₄ are 7 and 15. One can easily convince oneself that T₂ is 3 and T₁, 1 of course. It does not take one to be a trained mathematician to notice that T₀=0.

A general formula:

The recursive solution above involves moving twice (N-1) disks from one peg to another and making one additional move in between. It then follows that

T_N<=T_N-1+1+T_N-1 = 2T_N-1+1

The inequality suggests that it might be possible to move N disks with fewer than 2T_N-1+1 moves, which is actually not the case. Indeed, when the time comes to move the bottom disk (N-1) disks will have been moved from Src to Aux in at least T_N-1 moves. Since we are trying to use as few steps as possible, we may assume that that portion of the task took exactly T_N-1 moves. It takes just one move to move the biggest disk from Src to Dst. One then needs exactly T_N-1 more steps to finish the task. Therefore the minimum number of moves needed to solve the puzzle with N disks equals T_N-1 + 1 + T_N-1 = 2T_N-1 + 1 moves.

In other words,

T_N = 2T_N-1 + 1

Thus we can define the quantity T_N as

T₀ = 0

T_N = 2T_N-1 + 1 for N>0

From here, we may compute T₁ = 2T₀ + 1 = 1, T₂ = 2T₁ + 1= 3, T₃ = 2T₂ + 1 = 7 and so on sequentially. The above expression is known as a recurrence relation which is but a recursive function. T_N is defined in terms of only one of its preceding values.

Returning to the definition of T_N, define S_N = T_N + 1. Then S₀ = 1 and S_N = T_N + 1 = (2T_N-1 + 1) + 1 = 2T_N-1 + 2 = 2(T_N-1 + 1) = 2S_N-1. Which is to say that S_N could be defined as

S₀ = 1

S_N = 2S_N-1 for N>0

The latter is solved easily in the non-recurrent form of S_N=2^N. Wherefrom

T_N = 2^N-1 for N>=0

Enjoy life as it comes,

skk