The Tower of Hanoi is a mathematical Puzzle that consists of three towers(pegs) and multiple disks. Initially, all the disks are placed on one rod. And this disks are arranged on one over the other in ascending order of size.
Our Objective is to move all disks from initial tower to another tower without violating the rule.
The Rule For disk movement in TOH
The rules according to which the disks have to be moved in Tower of Hanoi are the following
1.Initially, the disks are placed in Increasing Order in size on Tower 1 from top to bottom.
the objective is to move them to tower 2, making also use of an auxiliary tower 3.
2.the conditions for moving the disks are:
all disks (except the one to be moved) have to be on one of the three towers.
Only one disk is possible to move at a time.
3.The only top disk can be moved i.e. taking from the top of one tower and placing on the top of another tower.
A larger disk can never be placed on a smaller disk.
Tower of Hanoi mathematical puzzle that has n disks with 3 towers can be solved in minimum 2^n−1 steps.
For an example
A puzzle with 3 disks has taken
2^3 – 1 = 7 steps.
Algorithm For Tower of Hanoi Puzzle
In Tower Of Hanoi puzzle we have three towers and some disks. We have to move this disk from intial tower to destination tower using aux tower.
For an example lets take we have two disks and we want to move it from source to destination tower.
So the approach we will follow
First, we will move the top disk to aux tower.
Then we will move the next disk (which is the bottom one in this case) to the destination tower.
And at last, we will move the disk from aux tower to the destination tower.
Similarly if we will have n number of disk then our aim is to move bottom which is disk n from source to destination. And then put all other (n-1) disks onto it.
Steps we will follow is
Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest
Means to move n > 1 disks from tower 1 to tower 2, using auxiliary tower 3
Step 1- Move n – 1 disks from Tower 1 to tower 3
Step 2 – Move the n-th disk from Tower 1 to Tower 2
Step 3 – Move n – 1 disk from Tower 3 to Tower 2
Algorithm
START
Procedure TOH(disk, source, dest, aux)
IF disk == 1, THEN
move disk from source to dest
ELSE
TOH(disk - 1, source, aux, dest) // Step 1
moveDisk(source to dest) // Step 2
TOH(disk - 1, aux, dest, source) // Step 3
END IF
END Procedure
STOP
