Solving Tower of Hanoi (defined sequence of moves)

Introduction

The Tower of Hanoi is a classic problem in mathematics and computer science that demonstrates the principles of recursion. The puzzle consists of three pegs and a number of disks of different sizes that can slide onto any peg. The objective is to move the entire stack of disks from one peg to another, following these 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 an empty peg.
3. No disk may be placed on top of a smaller disk.

#include <stdio.h>

// Function to perform the Tower of Hanoi operation
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); // Move n-1 disks from source to auxiliary
    printf("Move disk %d from %c to %c\n", n, source, target); // Move the nth disk from source to target
    towerOfHanoi(n - 1, auxiliary, target, source); // Move n-1 disks from auxiliary to target
}

int main() {
    int n; // Number of disks

    // Input: number of disks
    printf("Enter the number of disks: ");
    scanf("%d", &n);

    // Solve the Tower of Hanoi problem
    printf("The sequence of moves involved in the Tower of Hanoi are:\n");
    towerOfHanoi(n, 'A', 'C', 'B'); // A, B, and C are names of the rods

    return 0;
}

Explanation

1. Function Definition:
   • The function towerOfHanoi takes four parameters: the number of disks nnn, the source peg, the target peg, and the auxiliary peg.
   • Base Case: If there is only one disk, it is moved directly from the source peg to the target peg.
   • Recursive Steps:
     • Move n−1n-1n−1 disks from the source peg to the auxiliary peg using the target peg as a temporary storage.
     • Move the nnn-th disk directly from the source peg to the target peg.
     • Move the n−1n-1n−1 disks from the auxiliary peg to the target peg using the source peg as temporary storage.
2. Main Function:
   • Prompts the user to input the number of disks.
   • Calls the towerOfHanoi function to solve the puzzle.

Input

When the program runs, it prompts for the number of disks:

Enter the number of disks: 3

Output

The program outputs the sequence of moves required to solve the Tower of Hanoi problem:

The sequence of moves involved in the Tower of Hanoi are:
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

Conclusion

The Tower of Hanoi problem is a classic example of using recursion in programming. This recursive approach not only illustrates the elegance of recursive solutions but also helps in understanding how problems can be broken down into smaller subproblems. While the recursive method is straightforward and clear, it’s worth noting that it can be inefficient for a large number of disks, as the time complexity is O(2n)O(2^n)O(2n). Nonetheless, the Tower of Hanoi remains a fundamental problem that enhances understanding of recursion and algorithm design.