Tower of Hanoi

Tower of Hanoi

Tower of Hanoi is a classic problem to learn recursion. Most of us programmers believe that recursion never easy to understand and truly so. Tower of Hanoi problem is a good problem to learn how recursive solutions are arrived at, base conditions for recursion are generated and how parameters to the successive call to the same function are modified to give the desired output. 

This problem is inspired by a Hindu legend where priests at a temple were given three poles and 64 golden disk each one smaller than other. All of these disk were first places in one pole in such a way that larger disk is always below the smaller. Priest were given task to move these 64 disks from original pole to destination with below conditions:
1. Only one disk can be moved from one pole to another at a time.
2. No larger disk can be placed on smaller any time while moving disks.
And the legend is that when all these disks move to destination, temple will fall down.

For our mortal word problem statement is much simpler:We have three pegs : A, B, C. Peg A contains N disks which are stack in such a way that any disk below is larger that then disk above as shown in figure. Move these N (usually not more than 8) disks to Peg B in same condition mentioned above using the peg C.

Initial state
tower of hanoi-initial state

Final State
tower of hanoi

Tower of hanoi algorithm

Above problem can be solved easily using intuition, problem is to come with a solution in code.
Take a problem with five disks and three poles. Now what is the simplest case to work on in any case? Yes, the case when there is only one disk, we can straight forwardly move it from origin to destination.  Now, we know solution with one disk, if we can some how move 4 other disk from origin to destination using intermediate tower, we are good!

Now how to we move four disks? Again move three disks on intermediate tower and then move last from origin to destination. Then how to move three disks and then how two disks? This continues till we are left with only one disk and that is our base case !!!

Move N-1 disks from peg A to peg C and then move the Nth disk to destination peg B. Now we have a problem left with N-1 disks which need to move from peg C to peg B using peg A as spare. 

Generalized version of this algorithm is :

  1. Move a tower of height-1 to an intermediate pole, using the final pole.
  2. Move the remaining disk to the final pole.
  3. Move the tower of height-1 from the intermediate pole to the final pole using the original pole.

So we get the sight of recursion here? 
First  : We need to do same process to N-1 disk which we did for N disks.
Second : Base case is when we are left with only one disk at source, we directly move that to destination.
Pseudo-code for Tower of Hanoi


Function Tower_Of_Hanoi:
If N==1 : Move disk from source to destination
else
Tower_Of_Hanoi (N-1, source, destination, helper)
Move disk from source to destination
Tower_Of_Hanoi (N-1, helper, destination, source)

Now we would see how stacks can be used to solve this problem. A rule of thumb is :  If a problem can be solved using recursion, it can also be solve using stack. We need to map the recursion calls to stack.

Tower of hanoi implementation

void tower_of_hanoi(int N, char source, char dest, char help){
    if(N>0){
        tower_of_hanoi(N-1, source, help, dest);
        printf("Moving disk from %c to %c\n", source, dest);
        tower_of_hanoi(N-1, help, dest, source);
    }
}

Below is execution of Tower of Hanoi with three disks.

Complexity of tower of Hanoi can be found using this recursive relation
T(n) = T(n-1) + 1 + T(n-1)  = 2 T(n-1) + 1

This means to solve problem of n disks we need move n-1 disk to intermediate tower, then one disk from origin to destination and then again n-1 disk from intermediate to final tower. We can find out the actual complexity by putting in values in equation:

T(1)  = 2 T(0) + 1 =1
T(2)  = 2T(1) + 1 = 3
T(3)  = 2T(2) +1 = 7
T(4)  = 2T(3) + 1 = 15

If one looks closely, it is nothing but T(n)  = 2n -1. Hence complexity of Tower of Hanoi solution is exponential. Coming back to legend we started with, world is not going to end anytime soon as 264 -1 is quite a large number and even if it takes one second to move disk from one tower to another it will take 584, 942,417,355 years to solved this problem!
If you have any creative solution specially iterative, I would appreciate if you can share. Also, if you find something wrong or missing, please leave a comment.