C++ Program to Solve the Tower of Hanoi Problem

by

Introduction

The Tower of Hanoi is a classic problem in the realm of computer science and mathematics, often used to illustrate the concept of recursion. The problem involves three pegs and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in ascending order of size on one peg, the smallest at the top, making a conical shape. The objective is to move the entire stack to another peg, obeying the following rules:

  1. Only one disk can 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 peg.
  3. No larger disk may be placed on top of a smaller disk.

This article will guide you through the implementation of a C++ program to solve the Tower of Hanoi problem, explaining the steps and providing examples to illustrate the solution.

Prerequisites

Before proceeding, it is beneficial to have:

  • Basic understanding of algorithms: Knowledge of recursion is particularly useful.
  • Familiarity with C++ programming: Proficiency in C++ syntax, functions, and standard I/O.
  • Understanding of data structures: Particularly stacks, though this is more for conceptual clarity than practical necessity.

Tower of Hanoi Algorithm

Definition and Formula

The Tower of Hanoi problem can be solved using a recursive algorithm. The idea is to break the problem into smaller subproblems, each of which is a simpler instance of the same problem. The recursive solution can be defined as follows:

  1. Move n−1 disks from source peg to auxiliary peg.
  2. Move the nth disk from source peg to destination peg.
  3. Move n−1 disks from auxiliary peg to destination peg.

The base case of the recursion is moving a single disk, which is a straightforward operation.

The minimum number of moves required to solve the Tower of Hanoi problem is 2n−12^n – 12n−1, where nnn is the number of disks.

Implementing the Tower of Hanoi in C++

1.1 Basic Implementation

Below is a basic implementation of the Tower of Hanoi problem in C++.

C++
#include <iostream>

// Function to solve Tower of Hanoi problem
void towerOfHanoi(int n, char source, char destination, char auxiliary) {
    if (n == 1) {
        std::cout << "Move disk 1 from " << source << " to " << destination << std::endl;
        return;
    }
    towerOfHanoi(n - 1, source, auxiliary, destination);
    std::cout << "Move disk " << n << " from " << source << " to " << destination << std::endl;
    towerOfHanoi(n - 1, auxiliary, destination, source);
}

int main() {
    int n = 3; // Number of disks
    towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
    return 0;
}

1.2 Example Usage

The example above initializes the Tower of Hanoi with 3 disks. The output will show the sequence of moves required to transfer the disks from the source peg to the destination peg.

1.3 Output for Example 1

C++
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Additional Examples

2.1 Example 2: Increasing the Number of Disks

In this example, we increase the number of disks to 4 to illustrate how the solution scales.

C++
int main() {
    int n = 4; // Number of disks
    towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
    return 0;
}

Output for Example 2

C++
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
Move disk 4 from A to C
Move disk 1 from B to C
Move disk 2 from B to A
Move disk 1 from C to A
Move disk 3 from B to C
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

2.2 Example 3: Customizing the Disk Labels

Here, we use different labels for the pegs to show the flexibility of the solution.

C++
int main() {
    int n = 3; // Number of disks
    towerOfHanoi(n, 'X', 'Y', 'Z'); // X, Y and Z are names of rods
    return 0;
}

Output for Example 3

C++
Move disk 1 from X to Y
Move disk 2 from X to Z
Move disk 1 from Y to Z
Move disk 3 from X to Y
Move disk 1 from Z to X
Move disk 2 from Z to Y
Move disk 1 from X to Y

Conclusion

The Tower of Hanoi problem is a perfect example to illustrate the power of recursion. By breaking down the problem into smaller, manageable subproblems, it demonstrates how complex tasks can be simplified using a recursive approach. This article has provided a detailed C++ implementation of the Tower of Hanoi algorithm, complete with examples and outputs to illustrate its practical application.