Tower of Hanoi in C++

1. Tower of Hanoi
2. Solution of the Tower of Hanoi Problem
3. C++ Program for the Tower of Hanoi Problem

This article will brief the Tower of Hanoi Problem and its recursive solution in C++.

Tower of Hanoi

Tower of Hanoi is a Mathematical puzzle involving three rods and several disks that can move around the rods. The discs are placed in decreasing order of size from top to bottom and form a stack.

The target is to move all the discs in the destination (last) rod, keeping the order the same but following some rules:

1. You can move only one disk at a time.
2. Any disk can’t be placed on a disc that is smaller than itself.

Following these rules, you need to move the discs from the first rod or peg to the last rod. The minimum number of moves required to achieve this task is 2^n -1, where n is the number of disks.

This is illustrated in the picture below:

Now you need to move these three discs in Peg A to the destination Peg C with the help of Peg B.

Solution of the Tower of Hanoi Problem

There can be both iterative and recursive solutions to this problem, but we will discuss the recursive one here as iterative depends on the number of disks. For the recursive solution, suppose there are m discs on Peg A.

1. The same basic method is used to transfer m-1 discs from Peg A to Peg B. Assuming it does not break the rules, the disc m is now the top disc on Peg A.
2. Move the disc m from Peg A to the destination peg, i.e., Peg C, which is a straightforward procedure and follows the general rules.
3. By using the same method, move the m-1 discs we just put on Peg B from Peg B to the target peg, i.e., Peg C, so they may be put on top of the disc m without breaking any restrictions.
4. Repeat these steps till to reach the exit case.
5. The exit case is to move 0 disks, i.e., all disks are in the destination peg.

C++ Program for the Tower of Hanoi Problem

The C++ program to solve this problem is shown below:

void TowerOfHanoi(int m, string first, string middle, string last) {
  cout << "Current iteration " << m << endl;
  if (m == 1) {
    cout << "Moving Disc from " << first << " to " << last << endl;
  } else {
    TowerOfHanoi(m - 1, first, last, middle);
    cout << "Moving disc " << m << " from " << first << " to " << last << endl;
    TowerOfHanoi(m - 1, middle, first, last);
  }
}
int main() {
  int di = 3;
  TowerOfHanoi(di, "PegA", "PegB", "PegC");
}

This will give the following output:

Note that in the function TowerOfHanoi, we recall the function twice for every iteration. First, we move from the first peg to the middle and then from middle to last.

This will make the following tree:

main
  |--> TowerOfHanoi(3, ...)
  |      |
  |      |--> TowerOfHanoi(2, ...)
  |      |     |
  |      |     |--> TowerOfHanoi(1, ...)
  |      |     |--> TowerOfHanoi(1, ...)
  |      |<----|
  |      |--> TowerOfHanoi(2, ...)
  |      |     |
  |      |     |--> TowerOfHanoi(1, ...)
  |      |     |--> TowerOfHanoi(1, ...)
  |      |<----|
  |<-----|
  |