Tower Of Hanoi Algorithm, Explanation, Example and Program

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

• 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.
• 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.
  • 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.

History

There is one history behind Tower Of Hanoi is, It is originated from an ancient legend from Vietnam, according to which a group of monks is moving around a tower of 64 disks of different sizes according to certain rules. The legend says that, when the monks will have finished moving around the disks, the end of the world will come.

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

Pictorial Representation of How Tower of Hanoi works

Let’s see the below example where we have three disks that have to move in the destination tower which is the middle one with the help of the auxiliary tower.

Move disk 1 from tower source to tower destination

Move disk 2 from tower source to tower auxiliary

Move disk 1 from tower destination to tower auxiliary

Move disk 3 from tower source to tower destination

Move disk 1 from tower auxiliary to tower source

Move disk 2 from tower auxiliary to tower destination

Move disk 1 from tower source to tower destination

Program in Java to solve TOH puzzle

public class TowerOfHanoi
{
static void towerOfHanoi(int n, char source,
                    char dest, char aux)
	{
    		if (n == 1)
    		{
        		System.out.println("Move disk 1 from tower "+
                           source+" to tower "+dest);
        		return;
    		}
    		towerOfHanoi(n - 1, source, aux, dest);
    		System.out.println("Move disk "+ n + " from tower " +
                       source +" to tower " + dest );
    		towerOfHanoi(n - 1, aux, dest, source);
	}
 
	// Driver code
	public static void  main(String args[])
	{
    		int n = 3; // Number of disks
    		towerOfHanoi(n, 'A', 'B', 'C'); // A, B and C are name of towers
	}
}

Output

---

[wpusb]