C++ Program to Solve Tower of Hanoi using Stacks

This C++ program displays the iterative solution to the Tower of Hanoi problem. Tower Of Hanoi consists of three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
Only one disk may be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
No disk may be placed on top of a smaller disk.

Here is the source code of the C++ program to step by step disk transfer operations from one pole to another in a Tower Of Hanoi problem. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

```
/*
```

 * C++ Program to Traverse a Graph using DFS

```
 */
```
```
#include<stdio.h>
```
```
#include<conio.h>
```
```
#include<iostream>
```
```
#include<math.h>
```
```
using namespace std;
```
```
struct node1
```
```
{
```
```
    int data1;
```
```
    node1 *next1;
```
```
}*top1 = NULL, *p1 = NULL, *np1 = NULL;
```
```
struct node2
```
```
{
```
```
    int data2;
```
```
    node2 *next2;
```
```
}*top2 = NULL, *p2 = NULL, *np2 = NULL;
```
```
struct node3
```
```
{
```
```
    int data3;
```
```
    node3 *next3;
```
```
}*top3 = NULL, *p3 = NULL, *np3 = NULL;
```
```
void push1(int data)
```
```
{
```
```
    np1 = new node1;
```
```
    np1->data1 = data;
```
```
    np1->next1 = NULL;
```
```
    if (top1 == NULL)
```
```
    {
```
```
        top1 = np1;
```
```
    }
```
```
    else
```
```
    {
```
```
        np1->next1 = top1;
```
```
        top1 = np1;
```
```
    }
```
```
}
```
```
int pop1()
```
```
{
```
```
    int b = 999;
```
```
    if (top1 == NULL)
```
```
    {
```
```
        return b;
```
```
    }
```
```
    else
```
```
    {
```
```
        p1 = top1;
```
```
        top1 = top1->next1;
```
```
        return(p1->data1);
```
```
        delete(p1);
```
```
    }
```
```
}
```
```
void push2(int data)
```
```
{
```
```
    np2 = new node2;
```
```
    np2->data2 = data;
```
```
    np2->next2 = NULL;
```
```
    if (top2 == NULL)
```
```
    {
```
```
        top2 = np2;
```
```
    }
```
```
    else
```
```
    {
```
```
        np2->next2 = top2;
```
```
        top2 = np2;
```
```
    }
```
```
}
```
```
int pop2()
```
```
{
```
```
    int b = 999;
```
```
    if (top2 == NULL)
```
```
    {
```
```
        return b;
```
```
    }
```
```
    else
```
```
    {
```
```
        p2 = top2;
```
```
        top2 = top2->next2;
```
```
        return(p2->data2);
```
```
        delete(p2);
```
```
    }
```
```
}
```
```
void push3(int data)
```
```
{
```
```
    np3 = new node3;
```
```
    np3->data3 = data;
```
```
    np3->next3 = NULL;
```
```
    if (top3 == NULL)
```
```
    {
```
```
        top3 = np3;
```
```
    }
```
```
    else
```
```
    {
```
```
        np3->next3 = top3;
```
```
        top3 = np3;
```
```
    }
```
```
}
```
```
int pop3()
```
```
{
```
```
    int b = 999;
```
```
    if (top3 == NULL)
```
```
    {
```
```
        return b;
```
```
    }
```
```
    else
```
```
    {
```
```
        p3 = top3;
```
```
        top3 = top3->next3;
```
```
        return(p3->data3);
```
```
        delete(p3);
```
```
    }
```
```
}
```
```
int top_of_stack()
```
```
{
```

    if (top1 != NULL && top1->data1 == 1 )

```
    {
```
```
        return 1;
```
```
    }
```

    else if (top2 != NULL && top2->data2 == 1)

```
    {
```
```
        return 2;
```
```
    }
```

    else if (top3 != NULL && top3->data3 == 1)

```
    {
```
```
        return 3;
```
```
    }
```
```
}
```
```
void display1()
```
```
{
```
```
    cout<<endl;
```
```
    node1 *p1;
```
```
    p1 = top1;
```
```
    cout<<"Tower1-> "<<"\t";
```
```
    while (p1 != NULL)
```
```
    {
```
```
        cout<<p1->data1<<"\t";
```
```
        p1 = p1->next1;
```
```
    }
```
```
    cout<<endl;
```
```
}
```
```
void display2()
```
```
{
```
```
    node2 *p2;
```
```
    p2 = top2;
```
```
    cout<<"Tower2-> "<<"\t";
```
```
    while (p2 != NULL)
```
```
    {
```
```
        cout<<p2->data2<<"\t";
```
```
        p2 = p2->next2;
```
```
    }
```
```
    cout<<endl;
```
```
}
```
```
void display3()
```
```
{
```
```
    node3 *p3;
```
```
    p3 = top3;
```
```
    cout<<"Tower3-> "<<"\t";
```
```
    while (p3 != NULL)
```
```
    {
```
```
        cout<<p3->data3<<"\t";
```
```
        p3 = p3->next3;
```
```
    }
```
```
    cout<<endl;
```
```
    cout<<endl;
```
```
}
```
```
void toh(int n)
```
```
{
```
```
    int i, x, a, b;
```
```
    for (i = 0; i < (pow(2,n)); i++)
```
```
    {
```
```
        display1();
```
```
        display2();
```
```
        display3();
```
```
        x = top_of_stack();
```
```
        if (i % 2 == 0)
```
```
        {
```
```
            if (x == 1)
```
```
            {
```
```
                push3(pop1());
```
```
            }
```
```
            else if (x == 2)
```
```
            {
```
```
                push1(pop2());
```
```
            }
```
```
            else if (x == 3)
```
```
            {
```
```
                push2(pop3());
```
```
            }
```
```
        }
```
```
        else
```
```
        {
```
```
            if (x == 1)
```
```
            {
```
```
                a = pop2();
```
```
                b = pop3();
```
```
                if (a < b && b != 999)
```
```
                {
```
```
                    push3(b);
```
```
                    push3(a);
```
```
                }
```

                else if (a > b && a != 999)

```
                {
```
```
                    push2(a);
```
```
                    push2(b);
```
```
                }
```
```
                else if (b == 999)
```
```
                {
```
```
                    push3(a);
```
```
                }
```
```
                else if (a == 999)
```
```
                {
```
```
                    push2(b);
```
```
                }
```
```
            }
```
```
            else if (x == 2)
```
```
            {
```
```
                a = pop1();
```
```
                b = pop3();
```
```
                if (a < b && b != 999)
```
```
                {
```
```
                    push3(b);
```
```
                    push3(a);
```
```
                }
```

                else if (a > b && a != 999)

```
                {
```
```
                    push1(a);
```
```
                    push1(b);
```
```
                }
```
```
                else if (b == 999)
```
```
                {
```
```
                    push3(a);
```
```
                }
```
```
                else if (a == 999)
```
```
                {
```
```
                    push1(b);
```
```
                }
```
```
            }
```
```
            else if (x == 3)
```
```
            {
```
```
                a = pop1();
```
```
                b = pop2();
```
```
                if (a < b && b != 999)
```
```
                {
```
```
                    push2(b);
```
```
                    push2(a);
```
```
                }
```

                else if (a > b && a != 999)

```
                {
```
```
                    push1(a);
```
```
                    push1(b);
```
```
                }
```
```
                else if (b == 999)
```
```
                {
```
```
                    push2(a);
```
```
                }
```
```
                else if (a == 999)
```
```
                {
```
```
                    push1(b);
```
```
                }
```
```
            }
```
```
        }
```
```
    }
```
```
}
```
```
int main()
```
```
{
```
```
    int n, i;
```

    cout<<"enter the number of disks\n";

```
    cin>>n;
```
```
    for (i = n; i >= 1; i--)
```
```
    {
```
```
        push1(i);
```
```
    } 
```
```
    toh(n);
```
```
    getch();
```
```
}
```

Output
 
enter the number of disks
5
 
Tower1->        1       2       3       4       5
Tower2->
Tower3->
 
 
Tower1->        2       3       4       5
Tower2->
Tower3->        1
 
 
Tower1->        3       4       5
Tower2->        2
Tower3->        1
 
 
Tower1->        3       4       5
Tower2->        1       2
Tower3->
 
 
Tower1->        4       5
Tower2->        1       2
Tower3->        3
 
 
Tower1->        1       4       5
Tower2->        2
Tower3->        3
 
 
Tower1->        1       4       5
Tower2->
Tower3->        2       3
 
 
Tower1->        4       5
Tower2->
Tower3->        1       2       3
 
 
Tower1->        5
Tower2->        4
Tower3->        1       2       3
 
 
Tower1->        5
Tower2->        1       4
Tower3->        2       3
 
 
Tower1->        2       5
Tower2->        1       4
Tower3->        3
 
 
Tower1->        1       2       5
Tower2->        4
Tower3->        3
 
 
Tower1->        1       2       5
Tower2->        3       4
Tower3->
 
 
Tower1->        2       5
Tower2->        3       4
Tower3->        1
 
 
Tower1->        5
Tower2->        2       3       4
Tower3->        1
 
 
Tower1->        5
Tower2->        1       2       3       4
Tower3->
 
 
Tower1->
Tower2->        1       2       3       4
Tower3->        5
 
 
Tower1->        1
Tower2->        2       3       4
Tower3->        5
 
 
Tower1->        1
Tower2->        3       4
Tower3->        2       5
 
 
Tower1->
Tower2->        3       4
Tower3->        1       2       5
 
 
Tower1->        3
Tower2->        4
Tower3->        1       2       5
 
 
Tower1->        3
Tower2->        1       4
Tower3->        2       5
 
 
Tower1->        2       3
Tower2->        1       4
Tower3->        5
 
 
Tower1->        1       2       3
Tower2->        4
Tower3->        5
 
 
Tower1->        1       2       3
Tower2->
Tower3->        4       5
 
 
Tower1->        2       3
Tower2->
Tower3->        1       4       5
 
 
Tower1->        3
Tower2->        2
Tower3->        1       4       5
 
 
Tower1->        3
Tower2->        1       2
Tower3->        4       5
 
 
Tower1->
Tower2->        1       2
Tower3->        3       4       5
 
 
Tower1->        1
Tower2->        2
Tower3->        3       4       5
 
 
Tower1->        1
Tower2->
Tower3->        2       3       4       5
 
 
Tower1->
Tower2->
Tower3->        1       2       3       4       5

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Stack using Two Queues

» Next - C++ Program to Solve Tower of Hanoi using Binary Value

Next Steps: