# Tower of Hanoi Algorithm

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:

1. Only one disk can be moved at a time.
2. 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.
3. 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 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
```
##### 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(2N), There are two possibilities for every disk. Therefore, 2 * 2 * 2 * . . . * 2(N times) is 2N
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.