# C Program for Tower of Hanoi

The **Tower of Hanoi** (also called the **Tower of Brahma** or **Lucas’ Tower**) is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

- Only one disk can 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.
- No disk may be placed on top of a smaller disk.

**Origin of the Tower of Hanoi Problem**

The puzzle was invented by the French mathematician Edouard Lucas in **1883**. There is a story about an Indian temple in Kashi Vishwanath, which contains a large room with three time-worn posts in it surrounded by **64** golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the immutable rules of the Brahma, since that time. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle is completed, the world will end. It is not clear whether Lucas invented this legend or was inspired by it.

If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves, it would take them \(2^{64} -1 \) seconds, or roughly \(585\) billion years to finish, ^{}which is about \(42\) times the current age of the Universe.

**How to Solve Tower of Hanoi Problem**

Tower of Hanoi problem is the best example of recursive algorithm, where the larger problem is solved in terms of smaller problem.

We develop recursive algorithm for Tower of Hanoi problem as follow:

- Move top \(n-1\) disk from the source rod to auxiliary rod.
- Move the \(n^{th}\) disk from source rod to destination rod.
- Move the \(n-1\) disk from auxiliary rod to destination rod.
- transfer of \(n-1\) disk from one rod to another rod can again be thought as a fresh problem, and can be solved in the same manner.

Below figure is showing the above steps for three disk:

**C program for Tower of Hanoi Problem**

#include<stdio.h> void towerOfHanoi(int numberOfDisk, char* source, char* dest, char* aux){ if(numberOfDisk == 1){ printf("Move Disk 1 from %s to %s.\n", source, dest); return; } towerOfHanoi(numberOfDisk-1, source, aux, dest); printf("Move Disk %d from %s to %s.\n", numberOfDisk, source, dest); towerOfHanoi(numberOfDisk-1, aux, dest, source); } int main(){ int n; printf("Enter the number of disk: "); scanf("%d",&n); printf("\n=======Tower of Hanoi Solution=======\n"); towerOfHanoi(n, "source", "dest", "aux"); return 0; }

The result of above program with n=4 is:

Enter the number of disk: 3 =======Tower of Hanoi Solution======= Move Disk 1 from source to dest. Move Disk 2 from source to aux. Move Disk 1 from dest to aux. Move Disk 3 from source to dest. Move Disk 1 from aux to source. Move Disk 2 from aux to dest. Move Disk 1 from source to dest.

**Time complexity of Tower of Hanoi Problem**

Recurrence relation of Tower of Hanoi problem is given by:

$$T(n) = 2 T(n-1) + 1$$

Solving this recurrence relation we get \(T(n) = \mathcal O(2^n)\).

This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.