Tower of Hanoi
The Tower of Hanoi is also called the Tower of Brahma or Lucas' Tower and sometimes pluralized as Towers . Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, 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 or on an empty rod.
- No larger disk may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves.
The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.
Steps :
- Move n-1 disks from start to auxillary
- Move nth disk from start to end
- Move n-1 disks from auxillary to end .
Algorithm :
|
TowerOfHanoi(n , start, end, aux)
TowerOfHanoi(n-1, start, aux, end)
TowerOfHanoi(n-1, aux, end, start)
|
Example :
Program :
|
def TowerOfHanoi(n , start, end, aux):
if n == 1:
print("Move disk 1 from rod",start,"to rod",end)
return
TowerOfHanoi(n-1, start, aux, end)
print("Move disk",n,"from rod",start,"to rod",end )
TowerOfHanoi(n-1, aux, end, start)
n = 4
TowerOfHanoi(n, "A", "C", "B")
|
Output :
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 3 from rod A to rod B
Move disk 1 from rod C to rod A
Move disk 2 from rod C to rod B
Move disk 1 from rod A to rod B
Move disk 4 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 2 from rod B to rod A
Move disk 1 from rod C to rod A
Move disk 3 from rod B to rod C
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
For more JECRC University CSE-III Sem Data Structure and Algorithm Lab Experiments CLICK HERE
| 
| 
