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 2^{n} − 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