### 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