Program for Tower of Hanoi using stack in C++

In this tutorial, we will learn how to solve Tower of Hanoi using stack in C++.

Let’s first understand the problem and it’s rules.

Tower of Hanoi is a very famous puzzle that involves disks numbered from 1 to a number n and three poles. The size of the disk is directly proportional to the number on it and the three poles are known as source pole, auxiliary pole and destination pole. The disks are first on the source pole in a descending order from bottom to top i.e. the disk numbered 1(smallest disk) is on the top of the stack. The objective is to move the disks from the source pole to the destination pole according to the following rules-

1) You can move any one disk at a time.
2) You cannot place a larger disk on top of a smaller disk.

The problem and the goal for n=3 looks like this
Program for Tower of Hanoi using stack in C++

Approach

The way to go about this problem is to first take examples with n being a very small number. Solving for n=2, first we move disk 1 from the source to the auxiliary pole, then disk 2 from the source to the destination pole and at last disk 1 from the auxiliary to the destination pole taking us a total of 3 steps. Similarly, If we solve for n=3, we find that it takes 7 steps to move all three disks from the source. The 7 steps being-
disk 1 from source to destination
disk 2 from source to auxiliary
disk 1 from destination to auxiliary
disk 3 from source to destination
disk 1 from auxiliary to source
disk 2 from auxiliary to destination
disk 1 form source to destination

So we notice that for a number of disks, n, it takes us 2^n-1 steps.

The second step is to make two cases, one for n being an even number and the other for n being an odd number. We notice that for n being an even number, there are 3 transfers being repeated in an order-
1) First transfer between source and auxiliary pole
2) Second transfer between source and destination pole
3) Third transfer between auxiliary and destination pole

Similarly for n being an even number the 3 transfers being repeated in an order are-
1) First transfer between source and destination pole
2) Second transfer between source and auxiliary pole
3) Third transfer between destination and auxiliary pole

This implies that we can iteratively implement Tower of Hanoi using stacks in C++.

std::to_address in C++ with example

C++ Program: Tower of Hanoi using stack

An important point that we have to consider while writing our code is that this transfer should be a valid transfer i.e. It is not possible to place a larger disk on top of a smaller disk. Now that you have understood the approach, let’s take a look at the code to understand how exactly stack implementation of Tower of Hanoi takes place-

#include <iostream>
using namespace std;
#include <stack>
#include <cmath>

int transfer_disk(stack<int>& a,stack<int>& b){
    if(b.empty()==true){
        b.push(a.top());
        a.pop();
        return 1;
    }
    else if(a.empty()==true){
        a.push(b.top());
        b.pop();
        return 2;
    }
    else{
        if(b.top()>a.top()){
            b.push(a.top());
            a.pop();
            return 1;
        }
        else{
            a.push(b.top());
            b.pop();
            return 2;
        }
    }
}

int main(){
    stack<int> s,a,d;
    int n=0;
    cin>>n;
    for(int i=n;i>=1;i--){
        s.push(i);
    }
    
    int x=pow(2,n)-1;
    int i=1;
        
if(n%2==0){
    while(i<=x){
            if(i%3==1){
            int y=transfer_disk(s,a);
            if(y==1){
                cout<<"Move the disk "<<a.top()<<" from source to auxiliary"<<endl;
            }
            else
                cout<<"Move the disk "<<s.top()<<" from auxiliary to source"<<endl;
            }
            else if(i%3==2){
            int y=transfer_disk(s,d);
            if(y==1){
                cout<<"Move the disk "<<d.top()<<" from source to destination"<<endl;
            }
            else
                cout<<"Move the disk "<<s.top()<<" from destination to source"<<endl;
            }
            else{
            int y=transfer_disk(a,d);
            if(y==1){
                cout<<"Move the disk "<<d.top()<<" from auxiliary to destination"<<endl;
            }
            else
                cout<<"Move the disk "<<a.top()<<" from destination to auxiliary"<<endl;
            }
            i++;
    }
}
else{
    while(i<=x){
            if(i%3==1){
            int y=transfer_disk(s,d);
            if(y==1){
                cout<<"Move the disk "<<d.top()<<" from source to destination"<<endl;
            }
            else
                cout<<"Move the disk "<<s.top()<<" from destination to source"<<endl;
            }
            else if(i%3==2){
            int y=transfer_disk(s,a);
            if(y==1){
                cout<<"Move the disk "<<a.top()<<" from source to auxiliary"<<endl;
            }
            else
                cout<<"Move the disk "<<s.top()<<" from auxiliary to source"<<endl;
            }
            else{
            int y=transfer_disk(a,d);
            if(y==1){
                cout<<"Move the disk "<<d.top()<<" from auxiliary to destination"<<endl;
            }
            else
                cout<<"Move the disk "<<a.top()<<" from destination to auxiliary"<<endl;
            }
            i++;
    }
}
    

while(d.empty()!=true){
        cout<<d.top()<<endl;
        d.pop();
    }
    
    
return 0;
}

 

We have used the inbuilt stack function in the header file <stack.h> to implement stack in this problem. We create three integer stacks named s,a and d(source, auxiliary and destination poles) and take the input n, for the number of disks. Let’s understand the transfer_disk() function first to see how we have implemented the valid transfer of disks.

The transfer_disk() function takes two parameters by reference so that the changes made to them are reflected in the main program. The function checks if either of the two stacks are empty and pushes the top element of the one which is not empty into the one which is empty. If neither the stacks are empty it compares the top element of both and pushes the smaller one of the two into the stack which has the bigger top element. This is how the transfer of the top element from one stack to the other is ensured to be valid. The main() function divides the problem into two cases as mentioned above(n=odd number and n=even number) and calls the transfer_disk() function according to the corresponding transfers of the two cases, also as mentioned above.

Output

The main() function prints the number of the disk that was transferred and the name of the poles from and to which it was transferred. It prints the top element of the stack to which the disk was transferred as that disk is now the top element of that stack.
Lastly, it prints the elements of the destination stack to see whether our output is correct. Let’s look at the output.

for n=4 the output looks like this-

4
Move the disk 1 from source to auxiliary
Move the disk 2 from source to destination
Move the disk 1 from auxiliary to destination
Move the disk 3 from source to auxiliary
Move the disk 1 from destination to source
Move the disk 2 from destination to auxiliary
Move the disk 1 from source to auxiliary
Move the disk 4 from source to destination
Move the disk 1 from auxiliary to destination
Move the disk 2 from auxiliary to source
Move the disk 1 from destination to source
Move the disk 3 from auxiliary to destination
Move the disk 1 from source to auxiliary
Move the disk 2 from source to destination
Move the disk 1 from auxiliary to destination
1
2
3
4

Leave a Reply

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