Tower of Hanoi is a mathematical puzzle where we have three towers and n disks. The objective of the puzzle is to move the entire stack to another tower, 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 i.e. a disk can only be moved if it is the uppermost disk on a stack.
- No disk may be placed on top of a smaller disk.

##### Approach

Take an example for 2 disks : Let tower 1 = ‘A’, tower 2 = ‘B’, tower 3 = ‘C’.

Step 1 : Shift first disk from ‘A’ to ‘B’.

Step 2 : Shift second disk from ‘A’ to ‘C’.

Step 3 : Shift first disk from ‘B’ to ‘C’.

The pattern here is : Shift ‘n-1’ disks from ‘A’ to ‘B’. Shift last disk from ‘A’ to ‘C’. Shift ‘n-1’ disks from ‘B’ to ‘C’.

##### Sample

**Input ** − 3

**Output ** − A to B

A to C

B to C

A to B

C to A

C to B

A to B Explanation − uses recursive function & solves the tower of Hanoi

##### Implementation of Hanoi Tower 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)
{
if (num == 1)
{
printf("\n Move disk 1 from peg %c to peg %c", frompeg, topeg);
return;
}
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);
}
```

##### Output

Enter the number of disks : 3 The sequence of moves involvedinthe 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

##### Implementation of Hanoi Tower In Python

```
# Recursive Python function to solve tower of hanoi
def TowerOfHanoi(n, from_rod, to_rod, aux_rod):
if n == 0:
return
TowerOfHanoi(n-1, from_rod, aux_rod, to_rod)
print("Move disk", n, "from rod", from_rod, "to rod", to_rod)
TowerOfHanoi(n-1, aux_rod, to_rod, from_rod)
# Driver code
N = 3
# A, C, B are the name of rods
TowerOfHanoi(N, 'A', 'C', 'B')
# Contributed By Harshit Agrawal
```

**Time complexity**: O(2^{N}), There are two possibilities for every disk. Therefore, 2 * 2 * 2 * . . . * 2(N times) is 2^{N}**Auxiliary Space:** O(N), Function call stack space

#### Important Notice

If you’re a college student and have skills in programming languages, Want to earn through blogging? Mail us at geekycomail@gmail.com

For more Programming related blogs Visit Us Geekycodes . Follow us on Instagram.