a shot of dev knowledge

RELATED TAGS

What is the Tower of Hanoi problem?

The Tower of Hanoi, is a mathematical problem which consists of three rods and multiple disks. Initially, all the disks are placed on one rod, one over the other in ascending order of size similar to a cone-shaped tower.

The objective of this problem is to move the stack of disks from the initial rod to another rod, following these rules:

  • A disk cannot be placed on top of a smaller disk
  • No disk can be placed on top of the smaller disk.

The goal is to move all the disks from the leftmost rod to the rightmost rod. To move N disks from one rod to another, 2^𝑁−1 steps are required. So, to move 3 disks from starting the rod to the ending rod, a total of 7 steps are required.

1 of 8

Example

This example runs for 3 disks and 3 rods as described in the diagram above. It displays all the steps it follows to take the stack of disks from start to end.

Note: An Aux is the rod helping the movement of the disk. This rod contains the disks which are not to be moved in the current function call.

Initially, aux rod is set as middle tower.

#include <iostream> 
#include <string>
using namespace std; 
  
void TowerOfHanoi(int n, string from_tower, string to_tower, string aux_tower)  
{  
    if (n == 1)  
    {  
    cout << "Move disk 1 from rod " << from_tower <<  " to rod " << to_tower<<endl;  
    return;  
    }  
    TowerOfHanoi(n - 1, from_tower, aux_tower, to_tower);  
    cout << "Move disk " << n << " from rod " << from_tower << " to rod " << to_tower << endl;  
    TowerOfHanoi(n - 1, aux_tower, to_tower, from_tower);  
}  
  

int main()  
{  
    int n = 3; // Number of disks  
    TowerOfHanoi(n, "Start", "End", "Mid");  //names of the towers
    return 0;  
}  

RELATED TAGS

RELATED COURSES

View all Courses

Keep Exploring