# Discuss Tower of Hanoi problem in Data structure and algorithm.

0 like 0 dislike
1.7k views

edited

1. Tower of Hanoi problem
2. Using recursion
• When number of disks is 4
• When number of disks is 3
1. Tower of Hanoi problem with  Python Code

0 like 0 dislike
by (562 points)
selected

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

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

1. 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)=2n-1

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

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

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.  