**Tower of Hanoi**

**R**__ules of the game:__

- Move the tower of disks from one source to destination source or remaining source.
- We can move only one disk at a time i. e. only upper ones.
- No larger disk can be put at upper position or larger disk should be last.
- we can move two disks simultaneously.
- Given three towers,one with a set of n disks of size.
- Determine the minimum number of steps or moves to take all the disks from their initial positions to destination tower.

__Tower of Hanoi problem using recursion method:__

Hanoi(n)=1 ,if n=1

Hanoi(n)=2*Hanoi(n-1)+1 ,if n>1

Function Hanoi is:

**Input**:integers,n ,number of disks

- if n is 1,return 1;
- else return[2*Hanoi(n-1)+1];
- End Hanoi

**Evaluation of Tower of Hanoi to find the number of moves to take, change disks from initial tower to destination Tower.**

- When n =4

Hanoi(4)=2*Hanoi(4-1)+1

Hanoi(4)=2*Hanoi(3)+1

Hanoi(4)=2*[2*Hanoi(2)+1]+1

Hanoi(4)=2*[2*[2*Hanoi(1)+1]+1]+1

Hanoi(4)=2*[2*[2*1+1]+1]+1

Hanoi(4)=2*[2*[2+1]+1]+1

Hanoi(4)=2*[2*3+1]+1

Hanoi(4)=2*[6+1]+1

Hanoi(4)=2*7+1

Hanoi(4)=15

**If *** n represents number of disks ,then Hanoi(n)=2*^{n}-1

**When no of disks is 3**

Now,consider the number of disks is 3,then number of transformations needed for transferring all disks from source A tower to destination C tower.

*Fig:*

Source:https://images.app.goo.gl/3Gc35qLcmNJppUCu5

**The moves involved here are as follows:**

1)Move disk 1 from A tower to C tower

2)Move disk 2 from A tower to B tower.

3)Move disk from C tower to B tower.

4)Move disk 3 from A tower to C tower.

5)Move disk 1 from tower B to tower A.

6)Move disk 2 from B tower to C tower.

7)Move disk 1 from A tower to C tower.

Finally, we are moving all the disks from source tower to destination tower.

__Tower of Hanoi problem using Python__

**def Hanoi(disks, source, auxillary, target) :**

** if disks==1:**

** print('Move disk 1 from one source to another source. '. format(source, target)) **

** return**

** Hanoi(disks-1, source, target, auxillary) **

** print('Move disk from one source to another source. '. format(disks, source, target)) **

** Hanoi(disks-1, auxillary, source, target) **

**disks=int(input('Enter the number of disks:')) **

**Hanoi(disks, 'A', 'B', 'C') **

**Output:**

Enter the number of disks:3

Move disk 1 from one source to another source.

Move disk from one source to another source.

Move disk 1 from one source to another source.

Move disk from one source to another source.

Move disk 1 from one source to another source.

Move disk from one source to another source.

Move disk 1 from one source to another source.