Tower of Hanoi in C++

1. Understanding the Tower of Hanoi Problem
2. Solution of the Tower of Hanoi Problem
3. C++ Program for the Tower of Hanoi Problem
4. Analyzing the Time Complexity
5. Conclusion
6. FAQ

The Tower of Hanoi is a classic problem in computer science that challenges both beginners and experienced programmers alike. This intriguing puzzle consists of three rods and a number of disks of different sizes, which can slide onto any rod. The objective is to move the entire stack to another rod, obeying specific rules: only one disk can be moved at a time, and a disk can only be placed on top of a larger disk.

In this article, we’ll explore the Tower of Hanoi problem and provide a clear solution using C++. Whether you’re brushing up on your coding skills or tackling this problem for the first time, you’ll find the following sections informative and engaging.

Understanding the Tower of Hanoi Problem

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, ...)
  |      |<----|
  |<-----|
  |

Analyzing the Time Complexity

When discussing the Tower of Hanoi, it’s essential to consider its time complexity. The recursive solution has a time complexity of O(2^n), where “n” is the number of disks. This exponential growth means that the number of moves required doubles with each additional disk. For example, with just three disks, you’ll need seven moves, but with four disks, it jumps to 15 moves. This rapid increase highlights the challenge of the problem and serves as a reminder of the power of recursion in solving complex issues.

Conclusion

The Tower of Hanoi is not just a puzzle; it’s a gateway to understanding recursion and problem-solving in programming. With its simple rules and complex solutions, it serves as an excellent exercise for anyone looking to sharpen their coding skills. By implementing the solution in C++, we’ve demonstrated how recursion can simplify seemingly complicated tasks. Whether you’re a beginner or an experienced programmer, mastering the Tower of Hanoi can enhance your understanding of algorithmic thinking and recursive programming.

FAQ

1. What is the Tower of Hanoi problem?
   The Tower of Hanoi is a mathematical puzzle that involves moving disks between rods while following specific rules.

2. How does recursion work in solving the Tower of Hanoi?
   Recursion breaks the problem into smaller subproblems, moving disks between rods in a systematic way.

3. What is the time complexity of the Tower of Hanoi solution?
   The time complexity is O(2^n), where “n” is the number of disks.

4. Can the Tower of Hanoi be solved iteratively?
   Yes, while the classic solution is recursive, it can also be solved using an iterative approach.

5. How many moves are required for “n” disks?
   The minimum number of moves required is 2^n - 1.