Tower of Hanoi

Tower of Hanoi

Tower of Hanoi is mathematical puzzle which consists of three towers( roads) and more than one rings (disks) are in a tower. The objective of the puzzle is to move then entire stack to another road.

These rings (disks) are of different sizes and stacked upon in an ascending order it means smaller one sites over the larger one.

There are other variations of the puzzle where the number of disks increase, but the tower count remain the same.

Rules

There are some rules to solve this puzzle. The mission is to move all the disks to some another tower without violating the sequence of arrangements. A few rules to be followed for TOH are :-

1. Only one disk can be moved among the towers at once.

2. Only the top disk can be moved.

3. No large disk can sit over a small disk.

Note: The objective of the puzzle is to move all the disks from one pole (Towers) (say "source pole") to another pole (say "destination pole") with the help of the third pole (say"auxiliary pole").

Tower of Hanoi puzzle with n disks can be solved in minimum 2^n-1 steps.

Example: for 4 disks, 2^4-1=15 moves are required.

Algorithm

Step 1 : Calculate the total number of moves required. 

"pow(2,n)-1". here n is the number of disks.(2^n-1)

Step 2 : If number of disks (n) is even than interchange destination pole and auxiliary pole.

Step 3 : for i=1 to total number of moves : 

  

  if i%3==1 then legal movement of top disk between source pole and destination pole.

  if i%3==2 then legal movement top disk between source pole and auxiliary pole.

  if i%3==0 then legal movement top disk between auxiliary pole and destination pole.

Implementation program 

# recursive python function to solve tower of Hanoi

def TowerofHanoi(n, source, destination, auxiliary):

if n==1:

        print("move disk 1 from source", source, "to destination" ,destination)

        return TowerofHanoi(n-1,source,auxiliary,destination)

        print("Move Disk", n, "from source", source, "to destination", destination)

        TowerofHanoi(n-1, auxiliary, destination, source)

# Driver code

n=3

TowerofHanoi(n, 'A', 'B', 'C')

# A, B, C are the name of roads

print("sorted array is :")

for i in range(n)

        print(arr[i], end="")