C++ Program to Solve Tower of Hanoi Problem using stacks














































C++ Program to Solve Tower of Hanoi Problem using stacks




Program to Solve Tower of Hanoi problem using stacks


About Tower of Hanoi:


Tower of Hanoi is a Mathematical Puzzle consists of three Rods and a number of discs of different sizes which can be rearranged among them.The Puzzle starts with a neat Stack whose one Rod contains discs placed in ascending order of their sizes ,i.e. smallest at the top and largest at the bottom. 


Objective of Tower of Hanoi:


The Objective of the puzzle is to move all the discs from one Rod (Source Rod) to another Rod (Destination Rod) with the help of third Rod (Auxiliary Rod) but they must follow the listed rules below.


  

 Rules of the puzzle Tower of Hanoi:   


  •      During single iteration only one disc can be moved,i.e. you cannot move more than one discs at a time. 
  •        You cannot place a larger disc over a smaller disc.



 We already know about "Recursive Solution of Tower of Hanoi" ,We have also seen that for n discs the number of moves required is( 2n -1).



Iterative Algorithm:


 1. At First Calculate the number of moves required i.e. "pow(2,n) - 1" where "n" is number of discs.

 

 2. If the number of discs i.e n is even then swap Destination Rod and Auxiliary Rod.


 3. for i = 1 upto number of moves:

        Check if "i mod 3" == 1:

        Perform Movement of top disc between Source Rod and Destination Rod. 

        Check if "i mod 3" == 2:

        Perform Movement of top disc between Source Rod and Auxiliary Rod.

        Check if "i mod 3" == 0:

        Perform Movement of top disc between Auxiliary Rod and Destination Rod.



        

 Example:


 Let us see a simple example of 3 discs.


    Hence number of moves required = 7.






 After iteration i=1 , i % 3 == 1:

    Perform Movement of disc 1 from 'A' to 'C'.




  After iteration i=2 , i % 3 == 2:

       Perform Movement of disc 2 from 'A' to 'B'.




 

After iteration i=3 , i % 3 == 0:

     Perform Movement of disc 1 from 'C' to 'B'.




 

After iteration i=4 , i % 3 == 1:

     Perform Movement of disc 3 from 'A' to 'C'.


 



After iteration i=5 , i % 3 == 2:

   Perform Movement of disc 1 from 'B' to 'A'.





 After iteration i=6 , i % 3 == 0:

     Perform Movement of disc 2 from 'B' to 'C'.




After iteration i=7 , i % 3 == 1:

 Perform Movement of disc 1 from 'A' to 'C'.





 So, After all these iterations our objective is achieved as we have all the discs in our Destination Rod in   ascending order.



Note:- We are only moving the top disc of every Rod, these iterations are the Unique ones. There cannot be any  other solutions of a fixed number of discs "Tower of Hanoi". 



CODE:-


#include <bits/stdc++.h> 
using namespace std;
typedef struct Stack 
{ 
   int size; 
   int top;  
   int *arr;
}Stack_Node; 
     
Stack_Node* Create_stack(int size) 
    {
        Stack_Node* stack= new Stack;
        stack->size =size;
        stack->top =-1; 
        stack->arr = new int[size];
        return stack;
    }
// Function to check stack is full or not
bool Check_Full(Stack_Node* stack) 
    { 
       if(stack->top == stack->size - 1)
          return true;
       else
         return false;
     }
     
// Function to check stack is empty or not 
bool Check_Empty(Stack_Node* stack) 
    { 
       if(stack->top == -1)
         return true;
      else
        return false; 
    }
// Function to Push the element in stack
void push(Stack_Node* stack, int element) 
   { 
      if(Check_Full(stack)) 
         return; 

      stack->arr[++stack->top]= element; 
   }
// Function to Pop the element and return Popped element
int pop(Stack_Node* stack) 
   { 
        if(Check_Empty(stack)) 
           return -1;
           
        return(stack->arr[stack->top--]); 
    }

// Function to Print the Movement of Discs
void Move_Disc(int disc, char from_Rod, char to_Rod) 

   {   

       cout<<"Move the disc "<<disc<<" "<<"from Rod '"<<from_Rod<<"' to Rod '"<<to_Rod<<"'"<<endl;


   } 

void Move_Disc_Helper(struct Stack *source, struct Stack*dest, char s, char d) 
   { 
      int top1=pop(source); 
      int top2 =pop(dest); 
      if (top1 == -1) 
       { 
           push(source,top2); 
           Move_Disc(top2, d, s); 
       } 
      else if (top2 ==-1) 

      { 
              push( dest,top1); 
              Move_Disc(top1, s, d); 
      } 
      else if (top1 >top2) 
      { 
              push(source, top1);
              push(source, top2); 
              Move_Disc(top2, d, s); 
       } 
      else
       { 
             push( dest,top2); 
             push( dest,top1); 
             Move_Disc(top1, s, d); 

       } 
 } 

void TowerOfHanoi(int number_of_discs, struct Stack*source, struct Stack *aux, struct Stack *dest) 

    {  
            char s = 'S', d = 'D',a = 'A'; 
            
            //  if n is even swap aux and dest
            if (number_of_discs % 2== 0) 
            {
                        char var =d;
                        d =a;
                        a =var; 
            } 

            int number_of_moves =pow(2, number_of_discs) - 1; 
            for (int i =number_of_discs; i >= 1; i--) 
            {
                push(source,i); 
            }
            
            // iteration of each i upto number of moves
            for (int i = 1; i <=number_of_moves; i++) 
            { 
                if (i % 3== 0)  
                      Move_Disc_Helper(aux, dest, a, d); 
               else if (i% 3 == 2) 
                      Move_Disc_Helper(source,aux, s, a); 
               else if (i% 3 == 1) 
                      Move_Disc_Helper(source,dest, s, d); 
            } 
    }  

    int main() 

    { 
            int number_of_discs;
            cin>>number_of_discs;
            
            Stack_Node* source;
            Stack_Node* dest;
            Stack_Node* aux;
            
            // Creating 3 stacks for the three Rods           
            source =Create_stack(number_of_discs); 
            aux =Create_stack(number_of_discs); 
            dest =Create_stack(number_of_discs);   

            TowerOfHanoi(number_of_discs,source, aux, dest);
     
            // delete dynamically allocated memory stacks
            delete source;
            delete aux;
            delete dest;
            return 0; 
 

  }   



 INPUT:


   number of discs = 3


  OUTPUT:


     Move the disc 1 from Rod 'S' to Rod 'D'


     Move the disc 2 from Rod 'S' to Rod 'A'


     Move the disc 1 from Rod 'D' to Rod 'A'


     Move the disc 3 from Rod 'S' to Rod 'D'


     Move the disc 1 from Rod 'A' to Rod 'S'


     Move the disc 2 from Rod 'A' to Rod 'D'


     Move the disc 1 from Rod 'S' to Rod 'D'



 INPUT:


    number of discs = 4


   OUTPUT:


     Move the disc 1 from Rod 'S' to Rod 'A'


     Move the disc 2 from Rod 'S' to Rod 'D'


     Move the disc 1 from Rod 'A' to Rod 'D'


     Move the disc 3 from Rod 'S' to Rod 'A'


     Move the disc 1 from Rod 'D' to Rod 'S'


     Move the disc 2 from Rod 'D' to Rod 'A'


     Move the disc 1 from Rod 'S' to Rod 'A'


     Move the disc 4 from Rod 'S' to Rod 'D'


     Move the disc 1 from Rod 'A' to Rod 'D'


     Move the disc 2 from Rod 'A' to Rod 'S'


     Move the disc 1 from Rod 'D' to Rod 'S'


     Move the disc 3 from Rod 'A' to Rod 'D'


     Move the disc 1 from Rod 'S' to Rod 'A'


     Move the disc 2 from Rod 'S' to Rod 'D'


     Move the disc 1 from Rod 'A' to Rod 'D'



 


Comments

  • Puneet
    28-Oct-2019 02:39:55 AM
    Very good article. Very well explained
  • Yashaswi
    27-Oct-2019 08:29:24 PM
    Hello
  • Kumar
    27-Oct-2019 11:43:13 AM
    Many websites I have visited but sir you ace this one.