Tower of Hanoi – Recursion Based Problem

Tower of Hanoi, is a mathematical puzzle which consists of three towers and more than one disks is as depicted − These disks are of different sizes and stacked upon in an ascending order, i.e. the top most disk is smallest and the bottom most disk is largest in size.

The objective of puzzle is to shift the all rods to the last tower under these constraints ->

1. Only one disk may be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
3. No disk may be placed on top of a disk that is smaller than it.

Approach:

1. First mark the towers as A, B and C. and think for smaller cases, if we have a single disk we can simply put it to tower C from A .
2. Think if we have 2 disks what can we do first we put the upper disk and place in tower B and then pick the remaining disk and place it into tower C and then take the disk from B and place it into C now the tower A and B are empty and all disk are in tower C.
3. Now for any number of disks we use the upper 2 approaches recursively and its guarantee that for any number of disk this puzzle solved using the upper 2 approaches.

Implementation for the above approach in C++:

#include<iostream> 
using namespace std;
void TOH(int n,int A, int B, int C)
{
    if(n>0)
    {
        // From tower 1 to 2 using tower 3
        TOH(n-1,A,C,B); 
        cout<<"from tower "<<A<<" tower "<<C<<"\n";
        // From tower 2 to 3 using 1
        TOH(n-1,B,A,C);
    }
}
int main()
{
    int num_of_disk;
    cin>>num_of_disk;
    // Tower numbered as 1,2,3.
    TOH(num_of_disk,1,2,3);

}

Input:

4

Output:

from tower 1 tower 2
from tower 1 tower 3
from tower 2 tower 3
from tower 1 tower 2
from tower 3 tower 1
from tower 3 tower 2
from tower 1 tower 2
from tower 1 tower 3
from tower 2 tower 3
from tower 2 tower 1
from tower 3 tower 1
from tower 2 tower 3
from tower 1 tower 2
from tower 1 tower 3
from tower 2 tower 3

Time Complexity:

Tower of Hanoi works on recursion so its take order of 2^(number of disk) i.e., O(2^n).

Read Next: Combinatorial Game Theory | Game of Nim