TOWER OF HANOI – SHOUT CODERS
The 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. (Wikipedia)
For n disks, total 2^n – 1 moves are required.
Introduced: 1883
Designer: Édouard Lucas
Genre: Puzzle (Wikipedia)
PROCEDURE:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
TowerOfHanoi(noofdisk, source, dest, aux) do IF disk == 1, THEN move disk from source to dest ELSE TowerOfHanoi (no-of-disk- 1, source, aufrom_rod, dest) // Step 1 move disk from source to dest // Step 2 TowerOfHanoi (no-of-disk- 1, aufrom_rod, dest, source) // Step 3 done |
INPUT-OUTPUT:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Input : 2 Output : How many plates? : 2 S -> A S -> D A -> D Input : 3 Output : How many plates? : 3 S -> D S -> A D -> A S -> D A -> S A -> D S -> D |
C PROGRAM:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include<stdio> void ToH(int, char, char, char); void main() { int n; print("How many plates? : ") scanf("%d",&n); ToH(n,'S','D','A'); } void ToH(int n, char from_rod, char to_rod, char aux_rod) { if(n>0) { ToH(n-1,from_rod,aux_rod,to_rod); /*... n-1 plates moved from source to auxiliary using destination tower ...*/ printf("\n%c -> %c",from_rod,to_rod); /*...last plate moved form source to destination...*/ ToH(n-1,aux_rod,to_rod,from_rod); /*... n-1 plates moved from auxiliary to destination using source tower ... */ } } |
PYTHON PROGRAM:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def TowerOfHanoi(n , from_rod, to_rod, aux_rod): '''if n == 1: print "Move disk 1 from rod",from_rod,"to rod",to_rod return''' if n>0: TowerOfHanoi(n-1, from_rod, aux_rod, to_rod) print (from_rod," -> ",to_rod) TowerOfHanoi(n-1, aux_rod, to_rod, from_rod) # Driver code n = int(input("How many plates? : ")) TowerOfHanoi(n, 'S', 'D', 'A') # S, D, A are the name of rods |
MOVE DISK FROM SOURCE ROD TO DESTINATION ROD :
Tower of Hanoi Solution for 4 disks :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
Initial disk S: [4, 3, 2, 1] A: [] D: [] Move disk from rod S to rod A S: [4, 3, 2] A: [1] D: [] Move disk from rod S to rod D S: [4, 3] A: [1] D: [2] Move disk from rod A to rod D S: [4, 3] A: [] D: [2, 1] Move disk from rod S to rod A S: [4] A: [3] D: [2, 1] Move disk from rod D to rod S S: [4, 1] A: [3] D: [2] Move disk from rod D to rod A S: [4, 1] A: [3, 2] D: [] Move disk from rod S to rod A S: [4] A: [3, 2, 1] D: [] Move disk from rod S to rod D S: [] A: [3, 2, 1] D: [4] Move disk from rod A to rod D S: [] A: [3, 2] D: [4, 1] Move disk from rod A to rod S S: [2] A: [3] D: [4, 1] Move disk from rod D to rod S S: [2, 1] A: [3] D: [4] Move disk from rod A to rod D S: [2, 1] A: [] D: [4, 3] Move disk from rod S to rod A S: [2] A: [1] D: [4, 3] Move disk from rod S to rod D S: [] A: [1] D: [4, 3, 2] Move disk from rod A to rod D S: [] A: [] D: [4, 3, 2, 1] |
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1) Only one disk can be moved at a time.
2) A disk can only be moved if it is the
uppermost disk on a stack. i.e. Each move
consists of taking the upper disk from
one of the stacks and placing it on top of another
stack.
3) No disk may be placed on top of a smaller disk.
There are many long running time when input more than 10. 2^n-1 is the total moves required for n inputs. O(2^n) is the complexity. 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.
The tower of Hanoi (also called the tower of Brahma or the Lucas tower) was invented by a French mathematician Édouard Lucas in the 19th century. It is associated with a legend of a Hindu temple where the puzzle was supposedly used to increase the mental discipline of young priests.
Quick sort is fastest sorting algorithm and Heapsort is slowest sorting algorithm. Where Tower of Hanoi takes O(2^n) which is exponential.
Make it easy to remember as call Toh with n,s,d,a within recursive function call Toh 1st time with n-1,s,a,d and call Toh 2nd time with n-1,a,d,s. Program executes and you get the result. No of stacks initialize in each iteration may cause to internal memory full occur. To overcome this situation, you must careful about input.
