C Program for Tower of Hanoi

Tower of Hanoi Problem

The fun puzzle game tower of Hanoi consists of three towers or rods and an N number of discs. The game aims to move all the discs from tower X to tower Z using tower Y. following some rules.

The main three rules of the tower of Hanoi problem are as follows:

1. You can move only one disc at a time.

2. You can move only the uppermost disc of the stack.

3. You can’t place a larger disc on top of a smaller disc.

We can solve this problem by using iterative and recursive methods. 

We will cover both the recursive and iterative approaches in this article. You can visit our curated section on the Recursion topic to learn more about Recursion.

Example

Let’s start with a basic example of 3 discs to understand the problem better. 

So we have N = 3 and three pillars: X, Y, and Z.

 

Step 1: Move the disc from X to Z

Step 2: Move the disc from X to Y

Step 3: Move the disc from Z to Y

Step 4: Move the disc from X to Z

Step 5: Move the disc from Y to X

Step 6: Move the disc from Y to Z

Step 7: Move the disc from X to Z

Must Read Recursion in Data Structure

Algorithm for Recursive Approach

We need a base condition to solve this problem using the recursive approach.

We will consider the base case when we have only one disc, i.e., N=1.

When N = 1, move the disc from the start tower to the end tower. We can write the TOH function as follows:

TOH(1, X, Y, Z)
{ 
	Move the topmost disc from X to Z using Y;
}

 

When N != 1, we can split the disc stack into two parts. All other (n-1) disks are in the second part, while the largest disc (nth) is in the first. We will call our TOH function two times for the (n-1).

Step 1: TOH(N-1, start, end, intermediate).

Step 2: Move the topmost disc from the start to the end tower.

Step 3: TOH(N-1, intermediate, start, end).

 

For ‘n’ discs, we can generalise the algorithm as follows:

TOH(n, X, Y, Z)
{
  if(n>1)
    {
		TOH(n-1, X, Z, Y)
		Move the topmost disc from X to Z using Y;
		TOH(n-1, Y, X, Z)
		
	}
}

 

Therefore when we have n=2, we can write the function as follows:

TOH(2, X, Y, Z)
{
	TOH(1, X, Z, Y)
	Move the topmost disc from X to Z using Y;
	TOH(1, Y, X, Z)
}

 

When we have N = 3, we can write the algorithm as follows:

TOH(3, X, Y, Z)
{
	TOH(2, X, Z, Y)
	Move the topmost disc from X to Z using Y;
	TOH(2, Y, X, Z)
}

 

The number of moves for the given function is as follows:

for n number of discs = (2n - 1)

So we can say that,

For 2 discs, the number of moves = 3

For 3 discs, the number of moves = 7

Tree Structure Diagram

To understand the algorithm better, let’s see the tree structure diagram of the TOH problem when the disc number is three.

Code in C

Here is the complete recursive code of the Tower of Hanoi in C.

 

Input 1

3

 

Output 1

 Move the topmost disc from X to Z
 Move the topmost disc from X to Y
 Move the topmost disc from Z to Y
 Move the topmost disc from X to Z
 Move the topmost disc from Y to X
 Move the topmost disc from Y to Z
 Move the topmost disc from X to Z

 

Input 2

4

 

Output 2

 Move the topmost disc from X to Y
 Move the topmost disc from X to Z
 Move the topmost disc from Y to Z
 Move the topmost disc from X to Y
 Move the topmost disc from Z to X
 Move the topmost disc from Z to Y
 Move the topmost disc from X to Y
 Move the topmost disc from X to Z
 Move the topmost disc from Y to Z
 Move the topmost disc from Y to X
 Move the topmost disc from Z to X
 Move the topmost disc from Y to Z
 Move the topmost disc from X to Y
 Move the topmost disc from X to Z
 Move the topmost disc from Y to Z

 

Complexity Analysis

Time Complexity: The time complexity of the recursive approach of the tower of Hanoi in C is O(2ⁿ).

Explanation: Consider for n discs the time complexity required is T(n). We are calling the recursive function two times for (n-1) discs. Moving one disc from the start tower to the end tower is a constant time operation(suppose k1).

So we can write the equation as follows:

T(n) = 2 T(n-1) +k1 [equation 1]

 

Therefore,

T(0) = k2 [equation 2]

 

Using equation 1,

T(1) = 2T(1-1) + k1
     = 2T(0)+k1
     = 2k2 + k1       [equation 3] [Using eq 2]


T(2) = 2T(2-1) + k1
     = 2T(1) + k1
     = 4k2 + 2k1 + k1   [equation4] [Using eq 3]


T(3) = 2T(3-1) + k1
     = 2T(2) + k1
     = 8k2 + 4k1 + 2k1 + k1   [Using eq 4]

 

From these patterns, we can conclude that T(n) = O(2ⁿ). It has exponential time complexity. The time requirement doubles for every single increment in the problem size. 

Space Complexity: The space complexity of the recursive approach of the tower of Hanoi in C is O(n).

Explanation: Each function call's required space is independent of n, or we can say it is constant(k). The first recursive call ends when we make the second one. Therefore, we can use the first call's space for the second call.

T(n) = T(n-1) + k
T(0) = k
T(1) = 2k
T(2) = 3k
T(3) = 4k

 

Thus, the space complexity is O(n). The space complexity is linear for the recursive approach of the tower of Hanoi in C.

Algorithm for Iterative Approach

1. Calculate the total number of moves using the formula 2ⁿ -1, where n is the number of discs.
    
2. If n is even
   Moved from the intermediate to the end tower.
    
3. For i = 1 to n
   if(i%3 == 0),
   Move the disc from the intermediate to the end tower.
   
   else if (i%3 == 1) 
   Move the disc from the start to the end tower.
   
   else(i%3 == 2) 
   Move the disc from the start to the intermediate tower.

To know more about the iterative approach in various languages, you can check out the iterative tower of Hanoi.

Code in C

Here is the complete iterative code of the Tower of Hanoi in C.

 

Input

3

 

Output

Move the disc 1 from 'X' to 'Z'
Move the disc 2 from 'X' to 'Y'
Move the disc 1 from 'Z' to 'Y'
Move the disc 3 from 'X' to 'Z'
Move the disc 1 from 'Y' to 'X'
Move the disc 2 from 'Y' to 'Z'
Move the disc 1 from 'X' to 'Z'

 

Complexity Analysis

Time Complexity: The time complexity of the iterative approach of the tower of Hanoi in c is O(2ⁿ). The number of iterations increases exponentially with the number of discs since the iterative solution needs to produce and process every single combination of moves for n discs.
 

Space Complexity: The space complexity of the iterative approach of the tower of Hanoi in c is O(n) because we are using the stacks of size n. Where n is the number of discs.

Must Read what is storage class in c

Frequently Asked Questions

What is the logic of the Tower of Hanoi?

The Tower of Hanoi logic is solved using a recursive algorithm. To move a stack of disks from one rod to another, move the top (n-1) disks to an auxiliary rod, move the considerable disk to the target rod, and then move the (n-1) disks from the additional rod to the target rod, follow the rules of not placing a larger disk on a smaller one.

Is it possible to solve the Tower of Hanoi in C without recursion?

Yes, one can solve the tower of Hanoi in c without recursion using three basic steps. The first step is to find the number of moves. The second and third steps describe the condition when the number of discs is even and odd, respectively.

What is the time and space complexity of the recursive approach of Tower of Hanoi in C?

The time complexity of the recursive approach of the tower of Hanoi in C is O(2ⁿ).  The space complexity of the recursive approach of the tower of Hanoi in C is O(n).

What is the time and space complexity of the iterative approach of Tower of Hanoi in C?

The time complexity of the iterative approach of the tower of Hanoi in C is O(2ⁿ).  The space complexity of the iterative approach of the tower of Hanoi in C is O(n), as we use stack to solve the problem.

Conclusion

In this article, we extensively discussed the tower of Hanoi problem, algorithm, and code for the tower of Hanoi in C.

We hope this blog has helped you with your interview. We recommend you visit our articles on different topics of C, such as

• Introduction to C.
• Identifiers and Keywords.
• Const Qualifier in C.
• Ternary Operator in C
•  Tribonacci Series
• Bubble Sort Program in C
   

If you liked our article, do upvote our article and help other ninjas grow.  You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, System Design, and many more!

Head over to our practice platform Coding Ninjas Studio to practise top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!!

Happy Reading!!