Discuss Tower of Hanoi problem in Data structure and algorithm.

Question

In this article you will get to know,about 

1. Tower of Hanoi problem 
2. Using recursion

• When number of disks is 4
• When number of disks is 3

3. Tower of Hanoi problem with  Python Code

Answer 1

Tower of Hanoi

1. Rules 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.

---

2. 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

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

---

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

2. 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ⁿ-1

---

3. 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.

---

4. 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.