Tower of Hanoi example

 

     Tower of Hanoi is classic example where recursion allows us to express the problem easily.  Legend has it that monks in a temple of Brahma were given three golden rods. The first rod has a stack of 64 disks. The largest disk is at the bottom, and smallest is on the top. Each disk on the stack is smaller than the one on which it is sitting. The other two rods are empty at the beginning. The goal is to reposition all 64 disks from the first rod onto third rod by moving only one disk at the time. Second rod may be used to put disks on it as well. At no time should a larger disk be placed ot top of a smaller one.  Legend has it that the world would end upon completion of the above  task.  Assuming that moving a disk from one rod to another takes one second and that monks work day and night without resting nor ever making a mistake their work would take more than 500 000 million years, which is 25 times the estimated age of our universe. 

 

    Starting position has 64 (or n in general) disks on the first rod and other two rods are empty.  Final position has 64 (or n in general) disks on the third rod and the other two are empty.

 

The task will be completed if we do the following subproblems

 

First and third part is a subproblem with one disk less than originally.

 

So the entire method can be coded easily as follows.  The three rods will be named from, aux and dest to indicate their role in the problem.  Also we will not provide a code to actually move the disks.  The printout that top disk from rod x should be moved to rod y will be provided instead.  If there is only one disk that one should be moved from the from position to the dest position.  If the number of disks is larger than one we do the mentioned three subtasks.

 

public void hanoi( int n, char from, char aux, char dest)

{

   if (n == 1)

       System.out.println( from + “ -> ” + dest);

   else

       {

  Hanoi(n-1, from, dest, aux);

  Hanoi(1, from, aux, dest);

  Hanoi(n-1, aux, from, dest);

       }

}

 

However, it is not trivial to trace the execution of moves that have to be made.  To make it easier to see actual moves let us trace the method with 3 disks.

                                   

Hanoi(3, a, b, c)

            Hanoi(2, a, c, b)

                        Hanoi(1, a, b, c)                       a -> c              

                        Hanoi(1, a, c, b)                       a -> b

                        Hanoi(1, c, a, b)                       c -> b

            Hanoi(1, a, b, c)                                   a -> c

            Hanoi(2, b, a, c)

                        Hanoi(1, b, c, a)                       b -> a

                        Hanoi(1, b, a, c)                       b -> c

                        Hanoi(1, a, b, c)                       a -> c

 

In order to perform Hanoi(3, a, b, c) the subtask Hanoi (2, a, c, b) should be completed, then the largest disk should be moved from a to c and finally subtask Hanoi (2, b, a, c) should be completed. Each of the recursive calls with 2 disks will require additional calls as specified above. In time, moves are performed from top to bottom as listed. Using the  instructions how to move the top disk from rod x  to rod  y,  task Hanoi (3, a, b, c) will be completed as follows.

Fig  2  Hanoi (3) subtasks

 

Step 1 in Fig 2 is strating state for Hanoi(3, a, b, c)

Step 2 is state achieved after completing subtask Hanoi(2, a, c, b).

Step 3 is state achieved after completing subtask Hanoi(1, a, b, c).

Step 4 is goal state achieved after completing subtask Hanoi(2, b, a, c).

 

Fig 3 shows graphical illustration of actual steps performed in Hanoi(3).  The code only provides the following printout:

 

aà c

aà b

cà b

aà c

bà a

bà c

aà c

 

Fig3  Actual steps performed from left to right in Tower of Hanoi with 3 disks