C Program for Tower of Hanoi

Overview

Tower of Hanoi is a purely mathematics-based puzzle game that consists of three rods with a number of disks of varying diameters arranged in ascending order of diameter from the top, thus forming a conical shape consisting of disks. The aim of the game is to move the stack of disks from the first rod to the last rod using an auxiliary rod by following certain rules. The rules of the game are as follows:

One disk can be moved only once at a time.
Upper disk can be moved from one of the stacks and placed on top of another empty rod.
Disk of the largest diameter can't be placed on a disk of the smaller diameter.

Introduction to Tower of Hanoi in C

To solve the Tower of Hanoi Program in C programming language, the most basic implementation is by writing a program using

Recursive Method
Iterative method

tower-of-hanoi-example

C Program to Solve Tower of Hanoi Using Recursive Method

To solve the problem of the Tower of Hanoi in C, using the recursive method, We will consider the following:

Three rods A, B and C: where A is the rod from which the disks will be shifted. A acts as a source. B is the auxiliary rod using which the disks are moved to C. C is the destination rod.

Explanation

Tower of Hanoi when only one disk and towers A, B, and C are given:

tower-of-hanoi-with-one-disk

Tower of Hanoi when 2 disks are given with towers A, B, and C:

tower-of-hanoi-with-two-disk

Tower of Hanoi when 3 disks are provided with rods A,B, and C:

tower-of-hanoi-with-three-disk

Similarly.

Tower of Hanoi when n disks are given with rods A, B, and C

Note: For 'n' disks number of moves= $(2^{n-1})$ .

Let's look into the implementation of the following program using the C programming language.

Example

Output:

C Program to Solve Tower of Hanoi Using Iterative Method

Here also we'll consider 3 rods A, B and C as the source rod, auxiliary rod and destination rod.

tower-of-hanoi-step-by-step

Explanation

When i=1, we will shift the disk from source to destination.

When i=2, the auxiliary rod is empty so we move the disk from the source rod to the auxiliary rod.

When i=3, we need to shift the remaining disk to the destination rod and for it, we will shift the disk from destination to auxiliary.

In a similar way, we observe a pattern here, ie., after 3 subsequent moves, the destination rod becomes acceptable to get a disk(That's the reason we use i%3).

Example

Output:

Complexity of Tower of Hanoi in C

Time complexity of Tower of Hanoi using the

iterative method: $O(n)$
Space complexity: $O(n)$

Time complexity of Tower of Hanoi using

Recursive method: $O(2^n)$
Space complexity: $O(n)$

Ready to conquer complex algorithms? Our Dynamic Programming Certification course is your ticket to success. Enroll today and elevate your coding proficiency!

Conclusion

We learned two approaches to solving the Tower of Hanoi program in C programming language: The iterative method and the Recursive method.
Three rods are considered as a source, destination, and auxiliary rods for transferring the disks.
The number of moves required for 'n' disks is $2^{n-1}$ .
Time complexity of the Tower of Hanoi program in C using the iterative method is O(n) and using the recursive method is $O(2^n)$ .
Space complexity for both auxiliary and iterative approaches for solving the Tower of Hanoi program in c is O(n).