Trusted answers to developer questions

What is the Tower of Hanoi problem?

Get Started With Machine Learning

Learn the fundamentals of Machine Learning with this free course. Future-proof your career by adding ML skills to your toolkit — or prepare to land a job in AI or Data Science.

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

tower
hanoi
recursion
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?