Tower Of Hanoi In C [SOLVED]

In this article, we will implement the solution to the classical problem of Tower Of Hanoi using the C programming language.

What is Tower of Hanoi?

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 

1. Only one disk may 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 rod.
3. No disk may be placed on top of a disk that is smaller than it.

How to Solve Tower of Hanoi in C?

This is a classical recursion problem. We will approach this problem by dividing it into smaller subproblems solving which would result in the solution of the overall problem.

Let’s suppose that the towers are named as ‘A’, ‘B’, and ‘C’. And tower ‘A’ initially contains all the disks.

Steps to implement the solution

1. We shift the top N – 1 disks from tower A to the tower B
2. Then shift the bottom most disk to tower C
3. Notice that now we just need to shift the remaining N – 1 disks from tower B to tower C

Basically, we shift the disks from one tower to the second tower by taking the help of the third tower. And then we repeat the same procedure for the remaining disks.

For example, consider the case with 4 disks,

1. Shift top 3 disks from tower A to tower C(Iterations Needed: 3)
2. Shift the only disk remaining in tower A to tower B
3. Now shift the first 2 disks from tower C to tower A
4. And shift the last disk from tower C to tower B
5. Let’s now shift the topmost disk from tower A to tower C
6. Shift the only disk remaining in tower A to tower B
7. Now we are left with 3 disks in tower B that are perfectly arranged and single disk remaing in tower C
8. Shift the only remaining disk from tower C to tower B

To code the solution we will develop a function “move”. The function is going to have the following syntax:

void move(int n, char src, char helper, char dest)

Instead of using any vector or array to store each disk, and transfer the disks to different towers, we have named the towers Source, Destination, and Helper. We will just make a call on the move() function with N – 1 disk.

Code for Tower Of Hanoi In C

#include <cstdio>

int counter = 0;

void move(int n, char src, char helper, char dest)
{
        //base case
        if(n == 0)
                return;

        //incrementing the counter
        counter++;
        //recursive case
        //move N - 1 disks to the helper

        move(n - 1, src, dest, helper);
        printf("Shift disk %d from %c to %c\n", n,src, dest);
        move(n - 1, helper, src, dest);
}

int main()
{
        int n;
        printf("Enter the number of disks\n");
        scanf("%d", &n);

        move(n, 'A', 'C', 'B');
        printf("Total number of iterations required are: %d\n", counter);

        return 0;
}

Time Complexity

The time complexity of this recursive approach is exponential i.e. O(2^N). The total number of iterations required will be 2^N – 1

Space Complexity

Since we do not use any additional space for storing the data, the overall space complexity is constant i.e. O(1).

Output

Conclusion

In this article, we learned the recursive approach towards the problem of Tower Of Hanoi In C. We also discussed the time and space complexities of the C code.