Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Tower of Hanoi in C?
3.
Tower of Hanoi Problem
3.1.
Example
4.
Algorithm for Recursive Approach
4.1.
Tree Structure Diagram
4.2.
Code in C
4.3.
C
4.3.1.
Complexity Analysis
5.
Algorithm for Iterative Approach
5.1.
Code in C
5.2.
C
5.2.1.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
What is the logic of the Tower of Hanoi?
6.2.
Is it possible to solve the Tower of Hanoi in C without recursion?
6.3.
What is the time and space complexity of the recursive approach of Tower of Hanoi in C?
6.4.
What is the time and space complexity of the iterative approach of Tower of Hanoi in C?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

C Program for Tower of Hanoi

Author Nidhi Kumari
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Have you ever heard about the “Tower of Brahma”? According to a report by Édouard Lucas, there is a set of 64 gold disks on three diamond needles called the “Tower of Brahma” in the temple of Kashi Vishwanath in Varanasi, Uttar Pradesh, India.
 

Since the earliest days, priests have been working to find ways to transfer all the golden discs from the start needle to the end needle. The Universe may end when they succeed in moving the 64 discs without violating any of the rules framed by lord Brahma.

tower of hanoi in c

The popular version of this problem is the “Tower of Hanoi” puzzle. This article will help you to uncover the solution to this puzzling problem. 

What is Tower of Hanoi in C?

The Tower of Hanoi is a mathematical problem. In this problem, we move a stack of disks from one peg to another. We use a temporary peg to move the disks. In this problem, we have to follow some specific rules. The puzzle consists of three pegs and a number of disks of different sizes that can be stacked onto any peg. The rules for the Tower of Hanoi puzzle are as follows:

  1. Only 1 disk can be moved at a time.
     
  2. Each move consists of taking the topmost disk from one of the stacks and placing it on top of another stack or an empty peg.
     
  3. A larger disk must never be placed on top of a smaller disk. 
     

The objective of the problem is to move the entire stack of disks from one peg (the source) to another peg (the destination), using the third peg (the auxiliary) as temporary storage.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

 You can move only one disc at a time.

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

You can move only the uppermost disc of the stack.

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

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.

Three pillars

 

Step 1: Move the disc from X to Z

Move the disc from X to Z

Step 2: Move the disc from X to Y

Move the disc from X to Y

Step 3: Move the disc from Z to Y

Move the disc from Z to Y

Step 4: Move the disc from X to Z

Move the disc from X to Z

Step 5: Move the disc from Y to X

 Move the disc from Y to X

Step 6: Move the disc from Y to Z

 Move the disc from Y to Z

Step 7: Move the disc from X to Z

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.

Tree Structure Diagram

Code in C

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

  • C

C

#include <stdio.h>

void TOH(int, char, char, char);
int main()
{
int no_of_discs;
//User input
scanf("%d", & no_of_discs);
TOH(no_of_discs, 'X', 'Y', 'Z');
return 0;
}

// Tower of Hanoi recursive program in C
void TOH(int n, char towerX, char towerY, char towerZ)
{
if (n == 1)
{
printf("\n Move the topmost disc from %c to %c", towerX, towerZ);
return;
}

else
{
TOH(n - 1, towerX, towerZ, towerY);
printf("\n Move the topmost disc from %c to %c", towerX, towerZ);
TOH(n - 1, towerY, towerX, towerZ);
}
}

 

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(2n).

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(2n). 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 2n -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.

  • C

C

#include <stdio.h>

void TOH(int, char, char, char);
int main()
{
int no_of_discs;
//User input
scanf("%d", & no_of_discs);
TOH(no_of_discs, 'X', 'Y', 'Z');
return 0;
}

// Tower of Hanoi recursive program in C
void TOH(int n, char towerX, char towerY, char towerZ)
{
if (n == 1)
{
printf("\n Move the topmost disc from %c to %c", towerX, towerZ);
return;
}

else
{
TOH(n - 1, towerX, towerZ, towerY);
printf("\n Move the topmost disc from %c to %c", towerX, towerZ);
TOH(n - 1, towerY, towerX, towerZ);
}
}

 

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(2n). 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(2n) 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(2n) 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

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 AlgorithmsCompetitive ProgrammingSystem 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!!

Previous article
Sorting a Stack Using a Temporary Stack
Next article
Find the Roots of a Quadratic Equation in Program C
Live masterclass