HANOI n-DISK

 Question:

Develop a Program in C for the following Stack Applications

1. Solving Tower of Hanoi problem with n disks

 The Tower of Hanoi problem is a classic example of recursion and stack operations. The goal is to move n disks from the source peg to the destination peg, using an auxiliary peg, while obeying the following rules:

1. Only one disk can be moved at a time.

2. A disk can only be placed on an empty peg or on a larger disk.

3. Disks are moved from the source peg to the destination peg using the auxiliary peg.

Steps to Solve:

1. Move n-1 disks from the source peg to the auxiliary peg.

2. Move the nth disk from the source peg to the destination peg.

3. Move the n-1 disks from the auxiliary peg to the destination peg.

C Program: Solving the Tower of Hanoi Problem

Here's the C program for solving the Tower of Hanoi problem using recursion:

#include <stdio.h>

// Function to perform the movement of disks
void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    // Base case: If there's only one disk to move, move it directly
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, destination);
        return;
    }
    
    // Step 1: Move n-1 disks from source to auxiliary, using destination as auxiliary
    towerOfHanoi(n - 1, source, destination, auxiliary);
    
    // Step 2: Move the nth disk from source to destination
    printf("Move disk %d from %c to %c\n", n, source, destination);
    
    // Step 3: Move n-1 disks from auxiliary to destination, using source as auxiliary
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

int main() {
    int n;
    
    // Get the number of disks from the user
    printf("Enter the number of disks: ");
    scanf("%d", &n);
    
    // Call the recursive function to solve the Tower of Hanoi problem
    printf("The sequence of moves involved in the Tower of Hanoi are:\n");
    towerOfHanoi(n, 'A', 'B', 'C');  // A, B, and C are the names of the source, auxiliary, and destination pegs
    
    return 0;
}

Explanation of the Code:

1. towerOfHanoi function:

   • This function is recursive. It accepts 4 parameters:

     • n: Number of disks.

     • source: The source peg from which the disks need to be moved.

     • auxiliary: The auxiliary peg used to assist in the move.

     • destination: The destination peg where the disks need to be moved.

   • Base Case: When there's only one disk (n == 1), simply move the disk from the source peg to the destination peg.

   • Recursive Case: For n > 1, move n-1 disks to the auxiliary peg, move the nth disk to the destination, then move the n-1 disks to the destination peg.

2. main function:

   • Takes input from the user for the number of disks (n).

   • Calls the towerOfHanoi function to solve the problem with pegs labeled A, B, and C.

Sample Output:

Input:

Enter the number of disks: 3

Output:

ceciot@cec-IOT:~$ cd Desktop/
ceciot@cec-IOT:~/Desktop$ gcc hanoi.c -o abcd
ceciot@cec-IOT:~/Desktop$ ./abcd
Enter the number of disks: 4
The sequence of moves involved in the Tower of Hanoi are:
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
ceciot@cec-IOT:~/Desktop$ 

Complexity:

• Time Complexity: The time complexity of the Tower of Hanoi problem is $O(2^n)$, where n is the number of disks.

• Space Complexity: The space complexity is $O(n)$, due to the recursion stack.

Let me know if you'd like to explore this further, such as:

• Iterative solutions (if possible)

• Visualization of the steps

• Performance considerations with large numbers of disks