Tower of Hanoi Program in C Language

Problem Description

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

What is Tower of Hanoi?

Tower of Hanoi is a mathematical game or a puzzle which consists of 3 rods or pegs and n disks of various diameters. Tower of Hanoi puzzle begins with all disks stacked on one rod in decreasing order and the task is to move all these disks on some other rod.

Problem Solution

This C program uses a recursive function to solve the Tower of Hanoi. The tower of hanoi is a mathematical puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. Puzzle begins with all disks stacked on one rod in decreasing order and the task is to move all these disks on some other rod obeying the following rules.

Rules of Tower of Hanoi Puzzle:

Only one disk may be moved at a time.
Each move consists of taking the upper 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:

Suppose no of disks are 4 and the starting rod is ‘A’, the auxiliary rod is ‘B’ and the ending rod is ‘C’.

In each step first we move the top most node of peg ‘A’ to auxiliary peg ‘B’ and then finally move to ‘C’ which is the desired peg.

Note: Join free Sanfoundry classes at Telegram or Youtube

Initially:
All disks are stack on peg ‘A’ with order of their size being 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:

Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

       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

Now this is the desired solution as all of the disks are stacked on peg ‘C’.

Following is the approach for solving the tower of hanoi problem. In this approach we recursively call a function twice to place the disk in desired places or on desired pegs.

Tower of Hanoi Algorithm:

Step 1: Start the program.
Step 2: Input number of disks.
Step 3: Declare a function which takes the number of disks, starting disk, auxiliary disk and final disk as argument and recursively calls itself twice.
Step 4: Call the function.
Step 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

Next Steps: