Tower of Hanoi Algorithm in C++

The Tower of Hanoi is a classic mathematical puzzle that consists of three rods (or pegs) and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 1) Only one disk can be moved at a time. 2) A larger disk cannot be placed on top of a smaller disk. This article will explore how to solve the Tower of Hanoi puzzle using a recursive algorithm implemented in C++.

Fundamental Concepts / Prerequisites

To understand the C++ implementation of the Tower of Hanoi algorithm, a basic understanding of the following concepts is required:

• Recursion: Recursion is a programming technique where a function calls itself within its definition. This allows for solving problems by breaking them down into smaller, self-similar subproblems.
• C++ Functions: Familiarity with defining and calling functions in C++.
• Call Stack: Understanding how recursive function calls are managed by the call stack.

Core Implementation/Solution

#include <iostream>

using namespace std;

// Recursive function to solve the Tower of Hanoi puzzle
void towerOfHanoi(int n, char source, char destination, char auxiliary) {
    // Base case: If there is only one disk, move it directly
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << destination << endl;
        return;
    }

    // Recursive step:
    // 1. Move (n-1) disks from source to auxiliary rod, using destination as the auxiliary rod
    towerOfHanoi(n - 1, source, auxiliary, destination);

    // 2. Move the largest disk (nth disk) from source to destination rod
    cout << "Move disk " << n << " from " << source << " to " << destination << endl;

    // 3. Move (n-1) disks from auxiliary to destination rod, using source as the auxiliary rod
    towerOfHanoi(n - 1, auxiliary, destination, source);
}

int main() {
    int numDisks;

    cout << "Enter the number of disks: ";
    cin >> numDisks;

    // Solve the Tower of Hanoi puzzle with the given number of disks
    towerOfHanoi(numDisks, 'A', 'C', 'B'); // A, B and C are names of rods

    return 0;
}

Code Explanation

The C++ code above implements the Tower of Hanoi algorithm using recursion. Here's a breakdown:

void towerOfHanoi(int n, char source, char destination, char auxiliary): This function is the core of the algorithm. It takes four parameters:

• n: The number of disks to move.
• source: The rod from which the disks are to be moved. Represented by a character (e.g., 'A').
• destination: The rod to which the disks are to be moved. Represented by a character (e.g., 'C').
• auxiliary: The auxiliary rod that is used to temporarily hold disks during the move. Represented by a character (e.g., 'B').

if (n == 1): This is the base case of the recursion. If there is only one disk to move, it is directly moved from the source rod to the destination rod, and a message is printed to the console indicating the move.

Recursive Steps: If n is greater than 1, the following three steps are performed recursively:

1. towerOfHanoi(n - 1, source, auxiliary, destination);: Move the top n-1 disks from the source rod to the auxiliary rod, using the destination rod as a temporary holding place.
2. cout << "Move disk " << n << " from " << source << " to " << destination << endl;: Move the largest disk (the nth disk) from the source rod to the destination rod.
3. towerOfHanoi(n - 1, auxiliary, destination, source);: Move the n-1 disks from the auxiliary rod to the destination rod, using the source rod as a temporary holding place.

int main(): This is the main function that prompts the user to enter the number of disks and then calls the towerOfHanoi function to solve the puzzle. The rods are initialized as 'A', 'C', and 'B'.

Complexity Analysis

The Tower of Hanoi algorithm has the following complexity characteristics:

Time Complexity: The time complexity of the Tower of Hanoi algorithm is O(2ⁿ), where n is the number of disks. This is because, for each disk, the algorithm effectively doubles the number of operations required. The recurrence relation is T(n) = 2T(n-1) + 1. Solving this relation yields O(2ⁿ).

Space Complexity: The space complexity of the algorithm is O(n), where n is the number of disks. This is due to the recursive calls, which create a stack of function calls on the call stack. The depth of the recursion is proportional to the number of disks.

Alternative Approaches

While the recursive approach is the most common and conceptually clear way to solve the Tower of Hanoi, an iterative approach also exists. This can be implemented using bitwise operations to determine the sequence of moves. While the iterative approach avoids the overhead of recursion, it is generally more complex to understand and implement, often sacrificing readability for potential performance gains. For small number of disks, the recursive solution will likely have better performance due to the simplicity of the implementation.

Conclusion

The Tower of Hanoi puzzle serves as an excellent example for understanding recursion in programming. The recursive C++ implementation, although simple in structure, elegantly solves a complex problem. Understanding the algorithm's time and space complexity is crucial for evaluating its suitability for different problem sizes. While iterative solutions exist, the recursive approach remains a preferred choice due to its clarity and ease of understanding.