C++ Program for Tower of Hanoi

What is Tower of Hanoi?

The Tower of Hanoi (also called the Tower of Brahma or Lucas’ Tower, and sometimes pluralized) is a mathematical game or puzzle.

t

It 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 can 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 i.e. a disk can only be moved if it is the uppermost disk on a stack.
  • No disk may be placed on top of a smaller disk.

Animated Solution:

 

tower of hanoi solution

 

 

 We can solve the problem of tower of hanoi in 2 ways:

  1. Using Recursion
  2. Using Stacks

Using Recursion:

#include <iostream>
using namespace std;

void towers(int, char, char, char);

int main()
{
    int num;

    cout<<"Enter the number of disks : ";
    cin>>num;
    cout<<"The sequence of moves involved in the Tower of Hanoi are :n";
    towers(num, 'A', 'C', 'B');
    return 0;
}
void towers(int num, char frompeg, char topeg, char auxpeg)
{
    if (num == 1)
    {
        cout<<"n Move disk 1 from peg "<<frompeg<<" to peg "<<topeg;
        return;
    }
    towers(num - 1, frompeg, auxpeg, topeg);
    cout<<"n Move disk "<<num<<" from peg "<<frompeg<<" to peg "<<topeg;
    towers(num - 1, auxpeg, topeg, frompeg);
}

Sample Output:

Enter the number of disks : 3
The sequence of moves involved in the Tower of Hanoi are :

 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 C

 

Using Stacks:

#include<stdio.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 disksn";
    cin>>n;
    for (i = n; i >= 1; i--)
    {
        push1(i);
    }
    toh(n);
    return 0;
}

Sample 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

 

11 thoughts on “C++ Program for Tower of Hanoi”

  1. //http://66.147.244.173/~proprog1/solution-for-tower-of-hanoi-c/
    //corrected by James H H Rodríguez
    #include
    using namespace std;
    void towers(int, char, char, char);
    void towers(int num, char frompeg, char topeg, char auxpeg)
    {
    if (num == 1)
    {
    cout<<" Move disk 1 from peg "<<frompeg<<" to peg "<<topeg<< endl;
    return;
    }
    towers(num – 1, frompeg, auxpeg, topeg);
    cout<<" Move disk "<<num<<" from peg "<<frompeg<<" to peg "<<topeg<< endl;
    //cout << " Move disk " << n << " from " << src << " to " << dest << endl;
    towers(num – 1, auxpeg, topeg, frompeg);
    }
    int main()
    {
    int num;
    cout<>num;
    towers(num, ‘A’, ‘C’, ‘B’);
    system(“PAUSE”);
    return 0;
    }

    Reply
  2. Enter the mumber or disks : 3
    Move disk 1 from SRC to DEST
    Move disk 2 from SRC to AUX
    Move disk 1 from DEST to AUX
    Move disk 3 from SRC to DEST
    Move disk 1 from AUX to SRC
    Move disk 2 from AUX to DEST
    Move disk 1 from SRC to DEST
    Presione una tecla para continuar . . .

    Reply
  3. how can we get ouput as “invalid input” on entering a negative number(eg -8) in towers of hanoi using recurrsion

    Reply
  4. why when I enter even number it gives me wrong solving !!! when you enter even number it will stay in the second Tower !! but if u add odd nunmber it works without any problem ! please can u solve this problem.

    Reply

Leave a Comment