C Program for Tower of Hanoi

The Tower of Hanoi is a classic mathematical puzzle that demonstrates the power of recursion in programming. It is widely used in puzzle-solving exercises and is an excellent example for practicing C programming. In this blog, we will explore the problem, its recursive solution, and a sample C program for Tower of Hanoi.

What is the Tower of Hanoi?

The Tower of Hanoi puzzle consists of three rods and a set of disks of different sizes. The objective is to move all the disks from the source rod to the target rod using an auxiliary rod, following these rules:

• Only one disk can be moved at a time.
• A disk can only be placed on top of a larger disk or on an empty rod.
• The sequence of moves must preserve these rules at all times.

Understanding the Recursive Solution

The Tower of Hanoi problem is best solved using recursion due to its repetitive nature. The solution can be broken down into the following steps:

1. Move n-1 disks from the source rod to the auxiliary rod.
2. Move the largest disk directly to the target rod.
3. Move the n-1 disks from the auxiliary rod to the target rod.

This process repeats until all disks are successfully transferred.

Pseudocode for Recursive Solution

function TowerOfHanoi(n, source, target, auxiliary):
    if n == 1:
        Print "Move disk from" source "to" target
        return
    TowerOfHanoi(n-1, source, auxiliary, target)
    Print "Move disk from" source "to" target
    TowerOfHanoi(n-1, auxiliary, target, source)

Implementing Tower of Hanoi in C

C Program for Tower of Hanoi

#include <stdio.h>

// Function to perform Tower of Hanoi
void towerOfHanoi(int n, char source, char target, char auxiliary) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, target);
        return;
    }
    towerOfHanoi(n - 1, source, auxiliary, target);
    printf("Move disk %d from %c to %c\n", n, source, target);
    towerOfHanoi(n - 1, auxiliary, target, source);
}

int main() {
    int n;
    printf("Enter the number of disks: ");
    scanf("%d", &n);
    printf("Steps to solve Tower of Hanoi with %d disks:\n", n);
    towerOfHanoi(n, 'A', 'C', 'B');
    return 0;
}

Explanation of the Code

• Base Case: If there is only one disk, it is moved directly to the target rod.
• Recursive Calls: The function calls itself to move the remaining disks as per the recursive solution.
• Input: The number of disks is provided by the user.

Complexity Analysis

Applications of Tower of Hanoi

• Teaching recursion in programming courses.
• Solving real-world problems involving recursive breakdowns.
• Understanding the concept of stack-based memory allocation.

FAQs

What is the Tower of Hanoi problem?

The Tower of Hanoi is a mathematical puzzle that involves transferring disks between three rods according to specific rules.

Why is recursion used in solving the Tower of Hanoi?

Recursion is used because the problem can be divided into smaller subproblems of the same nature, making it a perfect fit for recursive solutions.

What is the time complexity of the Tower of Hanoi?

The time complexity of the Tower of Hanoi is O(2ⁿ), where n is the number of disks.

Can the Tower of Hanoi be solved iteratively?

Yes, the Tower of Hanoi can be solved iteratively, but the recursive solution is more intuitive and easier to implement.

Conclusion

The Tower of Hanoi puzzle is a brilliant demonstration of recursion and problem-solving in C programming. By understanding its rules and implementing the solution, you can enhance your programming skills and deepen your understanding of recursive algorithms.