Recursive Solution to Towers of Hanoi

Towers of Hanoi is a mathematical game or a puzzle in which there are three pegs, and some disks (originally 8) of different radius placed on top of one another such that no larger disk is placed on a smaller disk. The task is to transfer such a column of disks from a source peg to another destination peg. The constraints are we can move only one disk at a time, and we may use the third peg as a temporary storage for the disks, and a larger disk cannot be placed on top of a smaller disk.

The puzzle was invented by the French mathematician Édouard Lucas in 1883. There is a legend about an Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle, since that time. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle is completed, the world will end.[2] It is not clear whether Lucas invented this legend or was inspired by it.

— Wikipedia

In this post I will describe the basic recursive solution to the Towers of Hanoi

Towers of Hanoi

There are three pegs Source, Temp, Destination. There are n concentric rings of different sizes on the Source peg in such a way that the bottom most ring is the largest and the topmost ring is the smallest and a larger ring is not placed on a smaller ring. The task is to move this column on rings from the Source peg to the Destination peg using the Temp peg as temporary storage of the rings. The constraints are that only one ring can be moved from one peg to the other in one move, and a larger ring cannot be placed on top of a smaller ring. The configuration is shown below:

Initial State

                  Source             Temp         Destination

                     +                 +               +
                     |                 |               |
                     |                 |               |
                  +-----+              |               |
                +---------+            |               |
              +-------------+          |               |
            +-----------------+        |               |
   [================================================================]     


Final State

                  Source             Temp         Destination

                     +                 +               +
                     |                 |               |
                     |                 |               |
                     |                 |            +-----+
                     |                 |          +---------+
                     |                 |        +-------------+
                     |                 |      +-----------------+
   [================================================================]     

Let us define (S,T,D,n) as a problem instance where we need to move the disks from Source to Destination through Temp. The first location in the tuple denotes the initial letter of the source peg name, the second location in the tuple denotes the initial letter of the temporary peg name, and the third location in the tuple denotes the initial letter of the destination peg name and the fourth location denotes the number of disks for the current problem being solved. That is, the first, second and third location of the tuple represents the source, temp and destination poles for the current problem, and the third element the number of rings.

Therefore (S,T,D,n) represents the problem to transfer n disks from the source to destination through temp, when source is peg 1, temp is peg 2 and destination is peg 3. (T,S,D,n) means the source is peg 2, destination is peg 3 and temp is peg 1. This representation will be used in the following sections.

Recursive Solution

Although the monks devoted their lives to solve this problem, we won’t. We will see how an algorithm can be used to do the same.

Initially we have the main problem (S,T,D,n), ie. we need to move the disks from peg 1 to peg 3 through temp peg 2, and we have n disks. This problem instance can be broken down in the following sub problems:

1. Move the topmost (n-1) disks from Source (peg 1) to Temp (peg 2)
2. Move the n^th (largest) disk from Source (peg 1) to Destination (peg 3)
3. Move the (n-1) disks from Temp (peg 2) to Destination (peg 3)

The step 2 moves a single disk, but in step 1 and 3 the “Move the (n-1) disks …” is what cannot be done in one step. The work in step 2 and 3 ie. to “Move the topmost (n-1) disks from source peg 1 to temp peg 2” and “Move the n^th (largest) disk from source peg 1 to destination peg 3″ are itself two Towers of Hanoi problems with (n-1) disks, and with different source and destination combinations.

In the first subproblem in Step 1 we are moving the top (n-1) disks from Source to Temp. As the problem from which this subproblem was created was (S,T,D,n) the subproblem is (S,D,T,n-1), ie. it needs to move the (n-1) disks from the peg 1 to peg 2. So, for this subproblem the source peg is peg 1 and destination peg is peg 2, and we can use peg 3 as temporary. The number of disks in this subproblem is m = (n-1). So this can be solved like above:

1. Move the topmost (m-1) disks from Source (peg 1) to Temp (peg 3)
2. Move the m^th (largest) disk from Source (peg 1) to Destination (peg 2)
3. Move the (m-1) disks from Temp (peg 3) to Destination (peg 2)

Note how the source, destination and temp pegs change.

Similarly, the second subproblem in Step 3 of the actual main problem is (T,S,D,n-1), the source peg is peg 2 and destination peg is peg 3, and we can use peg 1 as temporary. The number of disks in this subproblem is m = (n-1). So this can also be solved like above:

1. Move the topmost (m-1) disks from Source (peg 2) to Temp (peg 1)
2. Move the m^th (largest) disk from Source (peg 2) to Destination (peg 3)
3. Move the (m-1) disks from Temp (peg 1) to Destination (peg 3)

From the above analysis we can clearly see that after breaking the main problem into two subproblems can again be divided into more sub-subproblems, which in order will be broken down to more subproblem. In each subproblem the number of disks is one less than its immediate parent problem. This recursive subproblem division will stop when we have a problem with one disk to be solved, in which case the solution is trivial, ie. simply move the only disk directly from source to destination. Therefore if we represent a problem with a node and the subproblems as its children nodes, then we form a tree which will have leaf nodes having trivial problems ie. to move only one disk.

For each subproblem we have the Source, Destination and Temp changes. This can be noted from the above example. If you make the problem division tree, then you can see how the Source, Temp and Destination pole numbers change between subproblem hierarchy.

At at each problem the (S,T,D,n) the two subproblems created are (S,D,T,n-1) at step 1 and (T,S,D,n-1) at step 3. That is, the first subproblem is generated by swapping the location 2 and location 3 of the tuple representing the original problem, and the second subproblem is generated by swapping the location 1 and location 2 of the tuple of the original problem. Each will have one less disk, as the bottom most disk is moved in one move. This mechanism is applied recursively to each of the generated subproblems. Therefore the subproblem tree will look like below:

A tree for the Towers of Hanoi subproblem division.
Only the subproblem branches are shown, 
the single disk move lies in between each pair of children are not shown.



                                     (S,T,D,n)
                                         +
                                         |
          +------------------------------+------------------------------+
          |                                                             |
          +                                                             +
     (S,D,T,n-1)                                                   (T,S,D,n-1)
          +-------------------+                     +-------------------+
          |                   |                     |                   |
          +                   +                     +                   +
     (S,T,D,n-2)         (D,S,T,n-2)           (T,D,S,n-2)         (S,T,D,n-2)
          +-------+           +-------+             +-------+           +-------+      
          |       |           |       |             |       |           |       |
     (S,D,T,n-3)  |           |  (S,D,T,n-3)   (T,S,D,n-3)  |           |  (T,S,D,n-3)
                  +           +        .            .       +           +          
          .  (T,S,D,n-3)   (D,T,S,n-3) .            .  (D,T,S,n-3)   (S,D,T,n-3)   .
          .       .           .        .            .       .           .          .
          .       .           .                             .           .          .
                  .           .                             .           .

The left child of each node represents the first subproblem in step 1 and the right child the second subproblem in step 3. Note how the labelling location 2 and 3 swap in each left child of each note (first subproblem of each problem), and the labelling of location 1 and 2 swap in each right child of each node (second subproblem of each problem). This will help writing the following algorithm.

function TowersOfHanoi (Pole S, Pole T, Pole D, Integer n)
{
  IF [ n == 0 ]
    THEN
      RETURN
  ENDIF
  
  TowersOfHanoi (S,D,T,n-1);
  PRINT ("Move disk no 'n' from 'S' to 'D'");
  TowersOfHanoi (T,S,D,n-1);
}

The above recursion will stop whenever n is 0. This is the case when the trivial problem is attempted to be broken down into more subproblems. When n = 0 then no operations are done, and the call simply returns. Therefore for a call TowersOfHanoi (S,T,D,1) only the PRINT statement will be executed, which will simply print the trivial solution which will move the only disk from the current source to destination peg. Note that in each recursive call the actual value of n is preserved in each of the recursion levels.

All the moves are done by the Step 2 of each subproblem, the other two steps simply divides the problem into smaller problems. The step 2 for each subproblem of size m moves the m^th bottom disk from source to destination thus placing one disk into position.

Intuitively the recursive algorithm could be seen like this. The “for this …” can be thought as the problem division.

To move 3 disks from peg 1 (source) to peg 3 (destination)

• first we need to transfer first the top 2 disks from peg 1 to peg 2, for this …
  • … we need to transfer top 1 disk from peg 1 (source) to peg 3 (temp)
  • then transfer the bottom most disk of this subproblem, the disk 2 from peg 1 (source) to peg 2 (destination)
  • at last transfer the disk 1 from peg 3 (temp) to peg 2 (destination)
• next, we need to transfer the bottom most disk of this subproblem, disk 3, from peg 1 (source) to peg 3 (destination).
• After which we need to transfer the pile of disk 2 and 1 on the peg 2 (temp) to peg 3 (destination), for which …
  • … we need to transfer top 1 disk from peg 2 (source) to peg 1 (temp)
  • transfer the bottom most disk of this subproblem, the disk 2 from peg 2 (source) to peg 3 (destination)
  • transfer the disk 1 from peg 1 (temp) to peg 3 (destination)

Here is a C Language implementation:

Sourcecode

 

#include <stdio.h>

void towers_of_hanoi (char source, char temp, char destination, int n)
{
  if (n == 0)
  {
	return;
  }
  
  // (S,D,T,n-1)
  towers_of_hanoi (source, destination, temp, n-1);  
  
   // move the bottom most disk from `source' to `destination' of the current problem
  printf ("\n%d disk (%c -> %c)", n, source, destination); 
  
  // (T,S,D,n-1)
  towers_of_hanoi (temp, source, destination, n-1);         
}

int main (void)
{
  int n;
  printf ("\nNumber of Disks \"n\": ");
  scanf ("%d", &n);

  towers_of_hanoi ('S', 'T', 'D', n);
  
  printf ("\n");
  return 0;
}

The code follows exactly the form presented in the algorithm. The function towers_of_hanoi ('S', 'T', 'D', n) is called. This provides the actual problem’s source, temp and destination peg name identifiers ‘S‘, ‘T‘, ‘D‘ characters respectively. Inside the recursive call, these parameters are in effect swapped when calling recursively in the next depth. When we print the Step 2, ie. the print statement at any depth, it gives the actual move which is needed to solve the actual problem.

Time and Space

Now we can have a look at the time taken by this algorithm to execute and show each move for a solution for n disks. The analysis is easy. Let there be total number of steps required to solve a Towers of Hanoi problem for n disks. From the above recursive algorithm we can see that the problem is broken down to 2 subproblems of size (n-1), and one operation to print the movement of the bottom most disk, which requires constant time, and can be seen as one operation.

Therefore the growth of time with respect to the input problem size is with as the trivial case and base condition of the recurrence relation. This homogeneous recurrence relation can easily be solved to . Therefore total number of moves required to solve a Towers of Hanoi problem instance of size n is . Like for 2 disks we have 3 moves, 3 disks we have 7 moves, and 10 disks we have 1023 moves. Clearly the time growth of the problem is . Therefore even for a computer is supplied with an enough large value its CPU time can be entirely devoted to solve the input problem instance.

It will be interesting to investigate about its space requirements. As it is using recursion and actually performing a DFS therefore the memory requirements are modest. Only the longest path down the recursion tree needs to be stored in the system stack. Each branch will do down until a node does not reach n = 0. Therefore the maximum length of stored nodes (actually function stack frames for each call) will be n. Therefore the memory growth is

Related Post

Here is another similar post from this blog: Towers of Hanoi Iterative process: simulating recursion

Links

Have a look at these links too:

• http://en.wikipedia.org/wiki/Tower_of_Hanoi
• http://www.cut-the-knot.org/recurrence/hanoi.shtml
22.505694 88.351861

Share this:

• Twitter
• Facebook
• More

• Reddit
• LinkedIn
• Pinterest
• Print
• Email

Like Loading...

Related