In this chapter we shall learn about below topics:
2.1 Introduction.
2.2 Problem Statement
2.3 Understanding using an example
2.4 Implementation
2.5 Output
2.1 Introduction
Tower of Hanoi is a classic problem that can be solved with the help of recursion.
2.2 Problem statement:
The problem statement is as follows:
There are different size of rings placed on top of each other in ascending order. There might be “n” number of rings, but there will be only 3 towers.
2.3 Understanding using an example
Your goal is to move all the rings from one tower to another tower [final result should be in ascending order] without breaking the below rules.
1. Only 1 ring can be moved at a time.
2. Only the top ring can be moved.
3. always smaller ring sits on larger ring.
To illustrate the solution to the problem, consider the below diagram that has 3 rings.
We follow below steps to move all the 3 rings to the 2nd tower.
So from the above diagram, we can see that, to move only 3 rings we took 7 steps. i.e for n rings it will take 2^n-1 steps.
Most of the steps are repetitive. Hence we use recursion to solve this problem.
So how can we solve the problem programmatically?
So we need to take 3 towers, let us name them as Source, Destination, and temp.
And “n” be the number of rings.
The below image shows which tower refers to Source, Destination and temp.
So to solve the problem recursively, we use below 3 steps:
Step 1 − Move n-1 disks from source to temp.
Step 2 − Move 1 disk from source to dest. This will be the base case for recursion.
Step 3 − Move n-1 disks from temp to dest.
2.4. Implementation
#include <iostream>
using namespace std;
void tower_of_hanoi(int n, char source, char destination, char temp)
{
if (n == 1)
{
cout << "Move disk 1 from the tower " << source << " to tower " << destination<<endl;
return;
}
tower_of_hanoi(n - 1, source, temp, destination);
cout << "Move disk " << n << " from tower " << source << " to tower " << destination << endl;
tower_of_hanoi(n - 1, temp, destination, source);
}
int main()
{
int n = 3;
//let A, B, C be the names of the towers.
tower_of_hanoi(n, 'A', 'B', 'C');
return 0;
}
2.5. Output
Move disk 1 from the tower A to tower B
Move disk 2 from tower A to tower C
Move disk 1 from the tower B to tower C
Move disk 3 from tower A to tower B
Move disk 1 from the tower C to tower A
Move disk 2 from tower C to tower B
Move disk 1 from the tower A to tower B
The time complexity of Tower of Hanoi using recursion is 2^n at worst case. I have written as “recursion” because, there is a way that you can solve this by using Dynamic Programming and Divide and Conquer Methods. As in this tutorial we have solved using recursion, we have taken the time complexity of recursion.