Towers of Hanoi Program & Algorithm In C

This article deals with the problem of towers of Hanoi in the C programming language. We all would have played towers of Hanoi puzzle in our childhood, right? Now let’s solve the mathematical puzzle computationally. Let’s start!

Introduction

Towers of Hanoi is a simple mathematical puzzle that has 3 rods and n disks. The puzzle’s task is quite easy. We need to shift all the n disks from one rod to another rod while following the rules.

The rules is what makes the puzzle tricky. The rules are:

• You can move only one disk at a time.
• The movement of the disk is taking the uppermost disk from a rod and placing it in the top position of a stack of another rod.
• While placing a disk, a bigger disk can’t be top on a smaller disk.

Example of Hanoi tower problem

Now let’s see example of towers of Hanoi problem with 3 rods and 2 disks.

Let’s name the rods as A, B, C. Consider that all the disks are in rod A. For our reference let the bigger disk be red color and the smaller one be blue.

Now the steps of solving the problem are,

1. Move the blue disk to rod C.
2. Now move the red disk i.e., the biggest one to rod B.
3. Move the smallest disk(blue) on top of the red disk in rod B.
4. We moved the disk without violating any rules. Viola!

Now let’ see the pictorial representation of the above steps just to be super clear.

Program

Difficulty level: Medium

Now let’s see the approach, algorithm and the code.

Approach

To know the approach for the problem, we need to analyze the steps involving a lesser amount of disks say 2. Let’s see the steps and find which number disk needs to be moved.

Let’s have 2 disks now and the steps are,

1. Shift the first disk from A to C.
2. Now, shift the second disk from A to B.
3. Again we shift the first disk from C to B.

So these steps can be written with a little bit of mathematical notations such as,

• Move n-1 disks from source to aux.
• Now Move n^th disk from source to destination.
• Move n-1 disks from aux to destination.

Here aux refers to the rod we use in-between the shifting process. This process is continued for n times for n disks.

Algorithm

As we know the approach to the problem let’s see the algorithm now. Now the algorithm will be based on recursion, as it reduces the code length. Recursion is used to reduce code complexity. The algorithm is written in code sort of type, but just the steps using common words.

Recursion: This is nothing but the repetition of the same steps in a self-similar way. The Recursion is written as a separate function

How does a recursion work?

A function calls itself until a certain condition is satisfied. The other name for the condition is ‘base case’.

//algorithm for recursion
START
Recursion(disk,src,dest,aux)
   IF disk ==1 , THEN
        move disk from source to destination
   ELSE
        recursion(disk-1, source,aux,dest)
        move disk from source to destination
        recursion(deisk-1,aux,source)
   END IF
END Recursion
STOP

As for the driver/main code just call the function alone.

Code

//pgm for towers of hanoi
#include<stdio.h>
//recursion code
void towers(int num, char fromrod, char torod, char auxrod)
{
    if (num == 1)
    {
        printf("\n Move disk 1 from rod %c to rod %c", fromrod, torod);
        return;
    }
    towers(num - 1, fromrod, auxrod, torod);
    printf("\n Move disk %d from rod %c to rod %c", num, fromrod, torod);
    towers(num - 1, auxrod, torod, fromrod);
}

//driver code
int main()
{
    int num=3;
    towers(num, 'A', 'C', 'B');
    return 0;
}

Run the code here

NOTE: You can assign any value to ‘num’.

Code Explanation

Driver code

1. Inside the main function initialize the number of disks in a variable num.
2. Now call the function towers with num, A, B, C(name of the rods) as arguments. Here the order of the arguments is important(source, destination, auxiliary).

Recursion code

1. When the function is called, the recursion function starts working.
2. The compiler checks the condition, it doesn’t satisfy the condition(num==1), so the next step is carried out. Here the function is called again. This is how we call a recursion.
3. Recursion function has num-1,from, aux,to as arguments. It again goes to the header part and the arguments are interchanged and the condition is checked.
4. The process goes on and on till the value of num becomes 1.
5. This recursion statement is for moving the first disk alone.
6. Now, the other recursion starts moving the other disks in a similar fashion.
7. This process continues till all the disks completely move from one rod to the other.

This recursion code can be very confusing and its best if you work out the code manually to get the steps clearly.

Output

Pictorial Representation

Complexity

The minimum number of moves for solving this problem for n disks is 2ⁿ-1 steps. Now let’s discuss the time and space complexity for the algorithm.

Time complexity

Time complexity is nothing but a function that computes the amount of time taken by the compiler to execute an algorithm.

Let us consider the time required is T(n). There are 2 recursive statements for n-1. So, T(n)=2(n-1), and also we need a constant variable. So, T(n)=2(n-)+k₁ .

• Now, T(0)=k₂ . This is constant.
• T(1)=2k₂ + k₁.
• Likewise, T(2)=8k₂ + 4k₁ +2k₁ +k₁.

1. Co-efficient of k₁=2ⁿ
2. Co-efficient of k₂=2ⁿ-1

Time complexity is T(2ⁿ) or T(aⁿ). Here ‘a’ has value greater than 1. This is an exponential time complexity. For a single increase, the exponential increase may be very high. This is computationally cost. This is the reason why it is hard to write a recursive function in a recursive fashion.

Space Complexity

Space complexity is a function that describes the amount of memory that an algorithm takes for input to the algorithm.

The space for every parameter is not related to n and hence it is a constant. Let us take the constant as k. We the second recursive call executes, the first one is over and so, the space of the first one goes to the second one. To keep it short, we reuse the first space for the second.

• T(n)=T(n-1)+k
• T(0)=k

• Now, T(1)=2k
• T(2)=3k
• T(3)=4k

The space complexity is O(n). Here the space complexity is linear unlike time complexity.

Conclusion

I hope this article helped you understand how the towers of Hanoi problem works and its solution. However, it is more important that you try the code and work out the steps manually all by yourself to get better. Always remember ‘Only practice makes a man perfect’. Keep trying and happy coding!