Tower of Hanoi Algorithm in C++
Tower of Hanoi is a type of puzzle that consists of three pegs and more than one ring, as shown in this.
![Tower of Hanoi Algorithm in C++](https://static.tutorialandexample.com/cpp/tower-of-hanoi-algorithm-in-cpp1.png)
The rings in the tower of Hanoi are of different sizes and placed in an ascending order, i.e., the smaller ring paced over the larger ring. There can be other variations of the puzzle where the number of disks increases, but the number of towers remains the same.
The Tower of Hanoi is a recursion problem. The algorithm aims to move all n disks from tower A to tower B.
Points about the Tower of Hanoi Algorithm:
- The Tower of Hanoi is the classic problem where all the disks form one tower to another tower using only three towers.
- In the start, all the disks are placed on top of each other, with larger disks under the smaller disks.
- The disks may move to any three towers, but the larger ones should be placed over a smaller disk, and only one disk can be transferred at a time.
The divide-and-conquer algorithm can easily solve this problem.
![Tower of Hanoi Algorithm in C++](https://static.tutorialandexample.com/cpp/tower-of-hanoi-algorithm-in-cpp2.png)
In the above 7 steps, all the disks from peg A will be transferred to C given the Condition:
- Only one disk will be shifted at a time.
- Smaller disks can be placed on larger disks.
Let T (n) be the total time taken to move n disks from peg A to peg C:
- Moving n-1 disks from the first peg to the second peg. This can be done in T (n-1) steps.
- Moving larger disks from the first peg to the third peg will require the first step.
- Recursively moving n-1 disks from the second peg to the third peg will require the T (n-1) step again.
So, total time taken T(n) = T(n – 1) + 1 + T(n – 1)
Therefore, the relation formula for Tower of Hanoi is:
T(n) = 2T(n – 1) + 1
Algorithm for Tower of Hanoi:
START
Function Hanoi(ring, start, goal, aux)
IF ring == 1, THEN
move the ring from start to goal
ELSE
Hanoi(ring - 1, start, aux, goal) // Step 1
move the ring from start to goal // Step 2
Hanoi(disk - 1, aux, gaol, start) // Step 3
END IF
END Function
STOP
Implementation of Tower of Hanoi Algorithm in C++:
#include<iostream>
using namespace std;
void towerOfHanoi(int n, char start, char end, char aux){
if(n==0){
return;
}
towerOfHanoi(n-1, start, aux, end);
cout<<"Move disk "<< n << " from rod "<< start << " to rod " << end <<endl;
towerOfHanoi(n-1, aux, end, start);
}
int main(){
int n = 3;
char a = 'A';
char b = 'B';
char c = 'C';
towerOfHanoi(n,a,b,c);
}
Output:
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 3 from rod A to rod B
Move disk 1 from rod C to rod A
Move disk 2 from rod C to rod B
Move disk 1 from rod A to rod B
Explanation:
The tower of Hanoi is the recursive function that takes the number of disks and the three towers, A, B, and C; our goal is to move the disks from tower A to B. The number of disks is 3. The first disk is moved from A to B, and the second disk is moved from A to C, then the first disk is moved from B to C, then from tower, A to B, 3rd disk is moved from A to B, and 1st disk is moved from rod C to rod A then 2nd disk is moved, and then last 1st disk is moved from A to B.
The time complexity of the tower of Hanoi is O (2N) because there are two possibilities for each disk. It takes O (n) space to solve the problem, which is a function called stack space.