Solution of Tower Of Hanoi Problem in C++

In this tutorial, we will learn about how to solve Tower of Hanoi problem in C++ and we will also look some easy examples to understand the solution.

Solve Tower Of Hanoi Using C++ (Recursion)

In Tower of Hanoi problem, we have three rods and N disks. The objective of this problem is such that we need to place all the disks from one rod(Source) to another rod(destination) by using of third rod.

Tower of Hanoi in c++

tower of hanoi

Some limitations of this problem:-

  • Only one disk can move at a time.
  • No disk may be put on the smaller one.
  • In each move, put the upper disk of one rod on the top of another rod.

Let’s see some examples,




Consider we have three rod A(source), B(auxiliary), C(destination) and we have only 1 disk, so we can easily put the disk from A to C in one step.

Now consider we have 2 disks.

  • Move the disk from rod A to rod B.
  • secondly, Put the disk from rod A to rod C.
  • finally, move the disk from rod B to rod C.

Let’s Suppose we have N disks, So the Algorithm for the recursive funtion is followed:-

if (N>0) go this three steps ,
  1.  firstly Move N-1 disks from rod A to rod B using rod C .
  2. Then secondly move a disk from rod A to rod C .
  3. Finally move N-1 disks from rod B to rod C using rod A.

 

CODE IMPLEMENTATION IN C++

 

//c++ program to implement tower of hanoi problem
#include<iostream>
using namespace std;

//recursive funtion
void TowerOfHanoi(int num,char A,char B,char C){
  if(num>0){
    TowerOfHanoi(num-1, A, C, B);
    cout<<"Move a disk "<<num<<" from "<<" "<<A<<" to"<<" "<<C<<endl;
    TowerOfHanoi( num-1, B, A, C);
  }
}

//main funtion
int main(){
  int numOfDisk;
  cout<<"Enter the no. of disks"<<endl;
  cin>>numOfDisk;
  
  //calling recursive funtion
  TowerOfHanoi(numOfDisk,'A','B','C');//A is the source rod , C is destination rod ,B is auxiliary rod
  cout<<endl;
}

Output

Enter the no. of disks
3
Move a disk 1 from A to C
Move a disk 2 from A to B
Move a disk 1 from C to B
Move a disk 3 from A to C
Move a disk 1 from B to A
Move a disk 2 from B to C
Move a disk 1 from A to C

 

Let’s look on formula,

for N disks, the total number of required steps is 2n -1

lets see for N=1 , 21 -1 = 1 step.
Now see for N=2 , 22 -1 = 3 steps.
and see for N=3 , 23 -1 = 7 steps.

 

for more information, you can see,

https://en.wikipedia.org/wiki/Tower_of_Hanoi

 

you may also learn

Dijkstra’s shortest path algorithm in C++

Dijkstra’s shortest path algorithm in C++


Leave a Reply

Your email address will not be published. Required fields are marked *