Explain about Towers of Hanoi with Program, Towers of Hanoi Problem

Towers of Hanoi:

                          Towers of Hanoi is a classical example of recursion problem. It is easier, efficient and do not make use of complex data structures.
                          In this problem, there are three towers named as Source, Auxiliary and Destination. The Source tower consists of three disks of different sizes, where each disk resting on the one just larger than it which is shown below.

                     
                         The task is to move all the three disks from Source to Destination without violating the following rules.
--> At a time, only one disk may be moved.
--> Larger disk should not be placed on top of a smaller disk.
--> For the purpose of intermediate storage of disks, only one auxiliary tower should be used.

Example:

     Let us consider three disks

The Source tower consisting of three disks.

Step1:

    

          Shift one disk from Source to Destination

Step2:

   

         Shift the second disk from Source to Auxiliary

Step3:

         Shift the first disk from Destination to Auxiliary.

Step4:

         Shift the third disk from Source to Destination.

Step5:

          Shift the first disk from Auxiliary to Source.

Step6:

         Shift the second disk from Auxiliary to Destination.

Step7:

         Shift the first disk from Source to Destination.

                    Finally, the three disks are moved from Source to Destination with satisfying the given rules.

--> The Number of moves from Source to Destination are 2ⁿ-1 = 2³-1=8-1=7 moves.

Program Logic:

Program:

#include<stdio.h>
#include<math.h>
void towers(int, char, char, char);
void main( )
{
                int d,m;
                printf("\nEnter the Number of Discs: ");
                scanf("%d", &d);
                m = pow(2,d)-1;
                printf("The Number of moves required are: %d", m);
                towers(d,'A','C','B');
}
void towers(int d, char from, char to, char aux)
{
                if(d==1)
                {
                         printf("\nMove the disc from %c to %c", from, to);
                }
                else
                {
                         towers(d-1,from,aux,to);
                         printf("\nMove the disc from %c to %c", from, to);
                         towers(d-1,aux,from,to);
                 }
}





Thanks for visiting.........