Tower of Hanoi

1. It is a classic problem where you try to move all the disks from one peg to another peg using only three pegs.

2. Initially, all of the disks are stacked on top of each other with larger disks under the smaller disks.

3. You may move the disks to any of three pegs as you attempt to relocate all of the disks, but you cannot place the larger disks over smaller disks and only one disk can be transferred at a time.

This problem can be easily solved by Divide & Conquer algorithm

In the above 7 step all the disks from peg A will be transferred to C given Condition:

1. Only one disk will be shifted at a time.
2. Smaller disk can be placed on larger disk.

Let T (n) be the total time taken to move n disks from peg A to peg C

1. Moving n-1 disks from the first peg to the second peg. This can be done in T (n-1) steps.
2. Moving larger disks from the first peg to the third peg will require first one step.
3. Recursively moving n-1 disks from the second peg to the third peg will require again T (n-1) step.

So, total time taken T (n) = T (n-1)+1+ T(n-1)

Relation formula for Tower of Hanoi is:

We get,

It is a Geometric Progression Series with common ratio, r=2
          First term, a=1(2⁰)

B equation is the required complexity of technique tower of Hanoi when we have to move n disks from one peg to another.

T (3) = 2³- 1
          = 8 - 1 = 7 Ans

[As in concept we have proved that there will be 7 steps now proved by general equation]

Program of Tower of Hanoi:

#include<stdio.h>
void towers(int, char, char, char);
 int main()
 {
       int num;
       printf ("Enter the number of disks : ");
        scanf ("%d", &num);
      printf ("The sequence of moves involved in the Tower of Hanoi are :\n");
      towers (num, 'A', 'C', 'B');
      return 0;
 
}
     void towers( int num, char from peg, char topeg, char auxpeg)
 {
           if (num == 1)
 {
       printf ("\n Move disk 1 from peg %c to peg %c", from peg, topeg);
           return;
 }
   Towers (num - 1, from peg, auxpeg, topeg);
    Printf ("\n Move disk %d from peg %c to peg %c", num, from peg, topeg);
   Towers (num - 1, auxpeg, topeg, from peg);
 }

Output:

Enter the number of disks: 3
The sequence of moves involved in the Tower of Hanoi is
Move disk 1 from peg A to peg C
Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
Move disk 3 from peg A to peg C
Move disk 1 from peg B to peg A
Move disk 2 from peg B to peg C
Move disk 1 from peg A to peg