How to Solve Tower of Hanoi in C?

A French mathematician Édouard Lucas invented a game puzzle called Tower of Hanoi in 1883. This puzzle game is related to a religious temple of Hanoi, Vietnam, the name of the temple was the Tower of Hanoi.

This temple has three towers which are surrounded by sixty-four golden disks in the temple. The temple priests used to pass these disks from one tower to another with traditional rules. According to the monks, the world would end when the first disk came back. That's why it is also called the Tower of Brahma puzzle. This was a little history behind the name "Tower of Hanoi," but now a question arises: What is the use of the Tower of Hanoi in C?

So in this guide, we will consider every single aspect around the Tower of Hanoi and its requirements in C.

What is Tower of Hanoi?

Tower of Hanoi is a type of Mathematical puzzle in which there are disks of different sizes, which can slide on top of each other. This puzzle also includes three towers, so these disks are stacked in ascending order on these towers.

There are specific procedures and rules that you have to follow without violating any rules.The aim is to move disks to another tower without breaking the sequence of arrangements. So a person needs to follow a few rules for the Tower of Hanoi are:

1. A person only has to move one disk amid towers at a specific period.
2. Remember that only the "top" disk requires to be removed.
3. Any larger disk can't be placed on the smaller disk.

Approach of Recursive Method

Recursion is the process in which any function calls itself while its execution occurs in the system. The recursion method is useful in solving small problems, and many things should be kept in mind to solve these problems. So let's take a simple example of a recursive method in C to understand this procedure easily.

In this example, we have three towers named J, K, and L, so we need to solve it, and the input of this Tower of Hanoi puzzle is 3. The syntax of this puzzle will be:

#include<stdio.h>
void TOH(int n,char x,char y,char z) {
   if(n>0) {
      TOH(n-1,x,z,y);
      printf("\n%c to %c",x,y);
      TOH(n-1,z,y,x);
   }
}
int main() {
   int n=3;
   TOH(n,'J','K','L');
}

When you execute this syntax then you will get an output like this:

J to K
J to L
K to L
J to K
L to J
L to K
J to K

Here is a little explanation about the approach we can perform in the recursive method of the Tower of Hanoi in C.

Let's take an example for two disks: 

Tower 1 = 'J', Tower 2 = 'K', Tower 3 = 'L'.

Step 1: Move the first disk from 'J' to 'K.'
Step 2: Move the second disk from 'J' to 'L.'
Step 3: Move the first disk from 'K' to 'L.'

The pattern is:
Move 'n-1' disks from 'J' to 'K'.
Move the last disk from 'J' to 'L'.
Move 'n-1' disks from 'K' to 'L'.

Let's take an example for two disks:

Tower 1 = 'J', Tower 2 = 'K', Tower 3 = 'L'.

Step 1: Move the first disk from 'J' to 'K'
Step 2: Move the second disk from 'J' to 'L'
Step 3: Move the first disk from 'K' to 'L'

The pattern is:

Move 'n-1' disks from 'J' to 'K'.
Move the last disk from 'J' to 'L'.
Move 'n-1' disks from 'K' to 'L'.

Code for Tower of Hanoi in C Using Recursive Method

Here is the syntax of the recursive method we can put in place for solving the tower of Hanoi in C:

/* C program for Tower of Hanoi*/
/*Application of Recursive function*/
#include <stdio.h>
void hanoifun(int n, char J, char L, char K)
{
    if (n == 1)
    {
        printf("\n Move disk 1 from tower %c to tower %c", J, L);
        return;
    }
    hanoifun(n-1, J, K, L);
    printf("\n Move disk %d from tower %c to tower %c", n, J, L);
    hanoifun(n-1, K, L, J);
}
 
int main()
{
    int n = 4; // n implies the number of disks
    hanoifun(n, 'J', 'L', 'K');  // J, K and L are the name of rod
    return 0;
}

Output

Move disk 1 from tower J to tower K
Move disk 2 from tower J to tower L
Move disk 1 from tower K to tower L
Move disk 3 from tower J to tower K
Move disk 1 from tower L to tower J
Move disk 2 from tower L to tower K
Move disk 1 from tower J to tower K
Move disk 4 from tower J to tower L
Move disk 1 from tower K to tower L
Move disk 2 from tower K to tower J
Move disk 1 from tower L to tower J
Move disk 3 from tower K to tower L
Move disk 1 from tower J to tower K
Move disk 2 from tower J to tower L
Move disk 1 from tower K to tower L

Explanation of Above Code

First, we put all the basic details and command lines for starting the recursive method in C:

/* C program for Tower of Hanoi*/
/*Application of Recursive function*/
#include <stdio.h>

In the next line, we have used a void, which is used as the function return type, and hanoifun, which works as a Hanoi function in C and C++. We have to move disks from J to L using K, so we have written the function as "J, L, and K" in the below command.

void hanoifun(int n, char J, char L, char K)

In these functions, n==1 is a boolean expression that works to return true if n is 1 or false if n is anything apart from 1.After that, we have written functions to move a disk from J to L, then hanoifun(n-1, J, K, L); is used for moving disks from J to K using L.

At last, we used hanoifun(n-1, K, L, J); for moving disks from K to L using J. In these functions “n-1” represents that we are moving an n-1 number of disks from one tower to another.

if (n == 1)
    {
        printf("\n Move disk 1 from tower %c to tower %c", J, L);
        return;
    }
    hanoifun(n-1, J, K, L);
    printf("\n Move disk %d from tower %c to tower %c", n, J, L);
    hanoifun(n-1, K, L, J);
}

So it was the brief information on the recursive method for Tower of Hanoi in C, and we have given the complete explanation of interchanging the positions of tower names in codes for having a correct output.

Approach of Iterative method

Iteration is a procedure to create loops or rotation in any program. This method is used to repeat a specific group of statements until the program meets the termination condition. The iterative method in C is designed for do-while and while functions. Now, here is the example of the Iterative method for the Tower of Hanoi in C.

// C Program for Iterative Tower of Hanoi 
#include <stdio.h> 
#include <math.h> 
#include <stdlib.h> 
#include <limits.h> 
 
// A structure to represent a stack 
struct Stack 
{ 
unsigned capacity; 
int top; 
int *array; 
}; 
 
// function to create a stack of given capacity. 
struct Stack* createStack(unsigned capacity) 
{ 
    struct Stack* stack = 
        (struct Stack*) malloc(sizeof(struct Stack)); 
    stack -> capacity = capacity; 
    stack -> top = -1; 
    stack -> array = 
        (int*) malloc(stack -> capacity * sizeof(int)); 
    return stack; 
} 
 
// Stack is full when top is equal to the last index 
int isFull(struct Stack* stack) 
{ 
return (stack->top == stack->capacity - 1); 
} 
 
// Stack is empty when top is equal to -1 
int isEmpty(struct Stack* stack) 
{ 
return (stack->top == -1); 
} 
 
// Function to add an item to stack. It increases 
// top by 1 
void push(struct Stack *stack, int item) 
{ 
    if (isFull(stack)) 
        return; 
    stack -> array[++stack -> top] = item; 
} 
 
// Function to remove an item from stack. It 
// decreases top by 1 
int pop(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return INT_MIN; 
    return stack -> array[stack -> top--]; 
} 
 
//Function to show the movement of disks 
void moveDisk(char fromPeg, char toPeg, int disk) 
{ 
    printf("Move the disk %d from \'%c\' to \'%c\'\n", 
        disk, fromPeg, toPeg); 
}
 
// Function to implement legal movement between 
// two poles 
void moveDisksBetweenTwoPoles(struct Stack *src, 
            struct Stack *dest, char s, char d) 
{ 
    int pole1TopDisk = pop(src); 
    int pole2TopDisk = pop(dest); 
 
    // When pole 1 is empty 
    if (pole1TopDisk == INT_MIN) 
    { 
        push(src, pole2TopDisk); 
        moveDisk(d, s, pole2TopDisk); 
    } 
 
    // When pole2 pole is empty 
    else if (pole2TopDisk == INT_MIN) 
    { 
        push(dest, pole1TopDisk); 
        moveDisk(s, d, pole1TopDisk); 
    } 
 
    // When top disk of pole1 > top disk of pole2 
    else if (pole1TopDisk > pole2TopDisk) 
    { 
        push(src, pole1TopDisk); 
        push(src, pole2TopDisk); 
        moveDisk(d, s, pole2TopDisk); 
    } 
 
    // When top disk of pole1 < top disk of pole2 
    else
    { 
        push(dest, pole2TopDisk); 
        push(dest, pole1TopDisk); 
        moveDisk(s, d, pole1TopDisk); 
    } 
} 
 
//Function to implement TOH puzzle 
void tohIterative(int num_of_disks, struct Stack 
            *src, struct Stack *aux, 
            struct Stack *dest) 
{ 
    int i, total_num_of_moves; 
    char s = 'J', d = 'K', a = 'L'; 
 
    //If number of disks is even, then interchange 
    //destination pole and auxiliary pole 
    if (num_of_disks % 2 == 0) 
    { 
        char temp = d; 
        d = a; 
        a = temp; 
    } 
    total_num_of_moves = pow(2, num_of_disks) - 1; 
 
    //Larger disks will be pushed first 
    for (i = num_of_disks; i >= 1; i--) 
        push(src, i); 
 
    for (i = 1; i <= total_num_of_moves; i++) 
    { 
        if (i % 3 == 1) 
        moveDisksBetweenTwoPoles(src, dest, s, d); 
 
        else if (i % 3 == 2) 
        moveDisksBetweenTwoPoles(src, aux, s, a); 
 
        else if (i % 3 == 0) 
        moveDisksBetweenTwoPoles(aux, dest, a, d); 
    } 
} 
 
// Driver Program 
int main() 
{ 
    // Input: number of disks 
    unsigned num_of_disks = 3; 
 
    struct Stack *src, *dest, *aux; 
 
    // Create three stacks of size 'num_of_disks' 
    // to hold the disks 
    src = createStack(num_of_disks); 
    aux = createStack(num_of_disks); 
    dest = createStack(num_of_disks); 
 
    tohIterative(num_of_disks, src, aux, dest); 
    return 0; 
}  

Explanation of Above Code

There is a specific algorithm of an iterative method for Tower of Hanoi in C, and here is the explanation on it:

• First, we have to create the "n" integer that stands for the number of disks.
• Now, create three stacks for auxiliary, destination, and source and create three variables "s" as A, B, and C.
• After that, check if the number of disk mod 2 is zero and storing "d" in the temporary variable. Now update "d" as "a" then "a" as a temporary variable.
• After updating the variable, create the variable for the number of moves, then update it as the "(n*n) -1."
• Now,we have to transerve from "n" to one then provide the current value in a source stack.
• After that, we have to transverse from 1 to a total number of moves then check that the current index mod 3 is one. Now, pop the top through the destination and source stack.
• In case the popped top of a source stack is the same as "INT_MIN", then we have to push the popped top of the destination to the source stack.
• In case the popped top of a destination stack is the same as "INT_MIN",then we have to push the popped top of the source to the destination stack.
• In case the popped top of a source stack is more than the popped top of the destination stack, then we have to push the tops in the source stack, or else we can push both in the destination stack. After performing it, we have to print the traversal.
• Now, check that the current index mod 3 is two, and we have to pop the top from the source, then the auxiliary stack.
• In case the popped top of the source stack is the same as "INT_MIN", then we have to push the popped top of the auxiliary to the source stack.
• In case the auxiliary stack's popped top is the same as "INT_MIN" then we have to push a popped top of the source to the auxiliary stack.
• In case the popped top of a source stack is more than the popped top of the auxiliary stack, then we have to push the tops in the source stack, or else we can push both auxiliary stacks. After performing it, we have to print the traversal.
• Now, check that the current index mod 3 is zero, and we have to pop the top from auxiliary, then the destination stack.
• In case the popped top of the source stack is the same as "INT_MIN", then we have to push the popped top of the destination to the auxiliary stack.
• In case the destination stack's popped top is the same as "INT_MIN", then we have to push a popped top of the auxiliary to the destination stack.
• In case the popped top of the auxiliary stack is more than the popped top of the destination stack, then we have to push the tops in the auxiliary stack, or we can push both the destination stack. After performing it, we have to print the traversal.

Conclusion

So it was the complete information on what is Tower of Hanoi in C and different methods to perform it easily. We have mentioned the history of the Tower of Hanoi and the reason behind its popularity in the programming World. Now, you can perform Tower of Hanoi in different programming languages like C#, Java, C++Python C, etc. We hope that our guide helped you to understand this particular topic, and if you want to learn more programming information, then please do visit our official website.