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.
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:
We can solve the problem of tower of hanoi in 2 ways:
- Using Recursion
- 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
//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;
}
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 . . .
I am need to implement tours of hanoi
without recursion
how this code will executed… about tracing?
how to trace this code??
this program only we can take 5 numbers also
how can we get ouput as “invalid input” on entering a negative number(eg -8) in towers of hanoi using recurrsion
boop the snoot
i am prefer to use stacks method, thanks bruh
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.
Bro;
Both methods are soo helpfull.