Tower of Hanoi Program in C

Problem Description

Write a C program to solve the Tower of Hanoi Problem.

What is the Tower of Hanoi?

The Tower of Hanoi is a mathematical game or puzzle consisting of 3 rods or pegs and ‘n’ disks of varying diameters. It starts with all disks stacked on one rod in decreasing order. The objective is to move all these disks onto another rod.

Problem Solution

This C program uses a recursive function to solve the Tower of Hanoi puzzle. The Tower of Hanoi is a mathematical puzzle that consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle begins with all disks stacked on one rod in decreasing order of size, and the task is to move the entire stack to another rod, obeying the following rules:

Rules of Tower of Hanoi Puzzle:

Only one disk can be moved at a time.
Each move consists of taking the topmost disk from one of the stacks and placing it on top of another stack or on an empty rod.
No disk may be placed on top of a disk that is smaller than it.

Example:

Let’s consider a scenario where the number of disks is 4, and the starting rod is ‘A’, the auxiliary rod is ‘B’ and the ending rod is ‘C’.

Step-by-Step Process:

Initially, all disks are stacked on peg ‘A‘ in descending order of their size: Disk3 < Disk2 < Disk1

       Peg A                    Peg B                    Peg C
    
       Disc 3
       Disc 2
       Disc 1

Moving Disc 3 To Peg C:

       Peg A                    Peg B                    Peg C

       Disc 2
       Disc 1                                                  Disc 3

Moving Disc 2 To Peg B:

       Peg A                    Peg B                    Peg C
 
       Disc 1                    Disc 2                    Disc 3

Moving Disc 3 To Peg B:

Free 30-Day Java Certification Bootcamp is Live. Join Now!

       Peg A                    Peg B                    Peg C
  
                                     Disc 3
        Disc 1                   Disc 2

Moving Disc 1 To Peg C:

       Peg A                    Peg B                    Peg C
     
                                     Disc 3
                                     Disc 2                     Disc 1

Moving Disc 3 To Peg B:

       Peg A                    Peg B                    Peg C
 
       Disc 3                    Disc 2                    Disc 1

Moving Disc 2 To Peg C:

       Peg A                    Peg B                    Peg C
         
       Disc 3                                                  Disc 2
                                                                    Disc 1

Moving Disc 3 To Peg C:

       Peg A                    Peg B                    Peg C
      
                                                                    Disc 3
                                                                    Disc 2
                                                                    Disc 1

This final arrangement signifies the desired solution, where all disks are stacked on peg ‘C‘.

The Tower of Hanoi problem is typically approached using recursion, calling a function twice to position disks on the desired pegs.

Tower of Hanoi Algorithm:

1. Start the program.
2. Input number of disks.
3. Define a function that takes the count of disks, initial disk, auxiliary disk, and target disk as arguments and recursively invokes itself twice.
4. Call the function.
5. End the Program.

Program/Source Code

Here is the source code of the C program for tower of hanoi. The C Program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```
```
 * Tower of Hanoi Program in C
```
```
 */
```
```
 
```
```
#include <stdio.h>
```
```
 
```
```
void towers(int, char, char, char);
```
```
 
```
```
int main()
```
```
{
```
```
    int num;
```
```
 
```

    printf("Enter the number of disks : ");

```
    scanf("%d", &num);
```

    printf("The sequence of moves involved in the Tower of Hanoi are :\n");

```
    towers(num, 'A', 'C', 'B');
```
```
    return 0;
```
```
}
```

void towers(int num, char frompeg, char topeg, char auxpeg)

```
{
```

    // Base Condition if no of disks are

```
    if (num == 1)
```
```
    {
```

        printf("\n Move disk 1 from peg %c to peg %c", frompeg, topeg);

```
        return;
```
```
    }
```
```
 
```

    // Recursively calling function twice

    towers(num - 1, frompeg, auxpeg, topeg);

    printf("\n Move disk %d from peg %c to peg %c", num, frompeg, topeg);

    towers(num - 1, auxpeg, topeg, frompeg);

```
}
```

Program Explanation

1. First input the number of disks placed on three rods.
2. Declare a function which takes 4 parameters which are: no of disks and name of initial disk, auxiliary disk and final disk.
3. The function recursively calls itself twice to solve the problem with a base case to stop when n is 1.
4. Call this function from main function.

Time Complexity: O(2ⁿ)
In each function call, we are calling the function twice so time complexity of tower of hanoi program is O(2ⁿ).

Space Complexity: O(n)
Space of the recursive stack is of order n, so space complexity of tower of hanoi program is O(n).

Program Output

In this case, the user enters “3” as the number of discs as input to solve the Tower of Hanoi puzzle.

 
Enter the number of disks : 3
The sequence of moves involved in the Tower of Hanoi are :
 
Move disk 1 from peg A to peg C
Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
Move disk 3 from peg A to peg C
Move disk 1 from peg B to peg A
Move disk 2 from peg B to peg C
Move disk 1 from peg A to peg C

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

« Prev - C Program to Find Nth Node of Inorder Traversal

» Next - C Program to Print Alternate Nodes of a Linked List using Recursion

Related Posts:

Recommended Articles: