Tower Of Hanoi

July 17, 2019

Introduction to Tower of Hanoi

The Tower of Hanoi is a mathematical puzzle also known as Lucas’ Tower .
It is a game which consists of 3 rods/pegs/stack and n number of disks. These disks are of different sizes.
These disks are arranged in an ascending order on a given peg.
The objective of the game is to move the entire lot of disks of size n to another peg, following certain simple contraints which are:
- Only a single disk can be moved from one rod to another rod at a given time.
- Each move involves selecting the top-most disk from the source peg and moving it to the top of another peg. In other words we can say, only the topmost disk of a peg can be moved to the other.
- No larger disk can be placed on a smaller disk.

Understanding the concept

Each move consists of a shift of one disk from one peg to another.

In the tower of hanoi problem we are given 3 pegs, namely :

The source peg: The rod from which the disk is moved to another peg is known as the source peg
The spare/auxiliary peg: The rod from through which a disk reaches from it’s source to destination peg is known as the spare peg.
The destination/target peg: The final rod to which a disk is moved is known as the destination peg.

Let us understand through an example. Assuming we have to move the topmost disk(green disk) from one peg to another via spare peg, the shifts of the disk from one peg to another is shown in the figure.

Example:

Let us understand how the tower of hanoi problem works.

Consider we are given three pegs and 3 disks of different size. The objective is to move the entire lot from one peg to another.

Keeping in mind the constraints of the problem we solve an example where n = 3

Step 1:

We are given 3 pegs and 3 disks.
The objective is to move the entire lot to an other peg, keeping in mind the stated constraints.

Step 2:

In the first iteration, we move the topmost disk- disk 3.
The disk-3 is moved from the peg X to peg Z as show in figure.

Step 3:

Since we can move one disk at a time, the next disk to be shifted is disk-2.
The disk-2 is moved from peg X to the peg Y as shown in the image below.

Step 4:

In this iteration, the disk 3 is moved from peg Z to the peg Y.
Since disk-2 was already there on the peg Y the disk-3 is placed on the top of disk-2.

Step 5:

In the next move, the disk-1 is moved from the peg X to peg Y.

Step 6:

Now, the disk-3 is moved from peg X to the peg Y.

Step 7:

In the next iteration, the disk-2 is moved from peg Y to peg Z.
We can see that the disk-1 already exists on the peg Z.
Thus the disk-2 is placed on the top of disk-1.

Step 8:

Now, if we see the image carefully we can see that the stack is sorted halfway, fulfilling all the constraints of the Tower of Hanoi problem. In the final step, the disk-3 is moved from the peg X to peg Z, on the top of disk-1 and disk-2.
The entire lot of disks has been moved from one peg to the other and the disks are arranged in an ascending order.

Theoretical Implementation of Tower of Hanoi

Earlier we have learnt about the shifts of disks from one stack to the other via hit and trial. But there is a standard function defined which shows how the moves are occurring logically.

The function for the implementation of TOH is given below.

void TH(int n,char a,char b,char c)
{

	if(n>=1)
	{
		TH(n-1,a,c,b);
		printf("\n%c -> %c",a,c);
		TH(n-1,b,a,c);
	}

}

Following the function stated above we can implement the tower of hanoi problem of n number of disks. The standard representation of the implementation of TOH is shown as follows. In here,

Each move of n disks is represented as :TH(n, R1, R2, R3).
This disk further decomposes into three parts:
- Part 1: TH( n-1 ,R1 , R3, R2).
- Part 2: (R1 , R3).
- Part 3: TH( n-1 , R2 , R1 , R3 )
Each of the new decomposed move is then treated as the master move and it continues to decompose further untill n = 0.
The process of decomposition and new shifts is shown as follows.

Let us take an example to understand the theoretical implementation of the tower of hanoi.

Let us consider we have n = 3.

Now the step by step implementation of the TOH is shown as follows.

Step 1:

Consider we have three rods or pegs X , Y and Z.
When we have n = 3, according to the predefined structure we write it as,

Step: TH(3 , X , Y , Z)

Step 2:

As we move forward, the value of n reduces by 1 , i.e, n = 2.
It further decomposes to next shifts as shown in the image.
With this we get the first shift , i.e , X => Z

Step 3:

In this step, Each of decomposed transition is treated as a master move.
The value of n again decreases by 1, i.e , n = 1.
Decomposing the second transitions further we get the next set of moves , i.e ,

X => Y.

Y => Z.

Step 4:

In the final step, the value of n reduces to zero, i.e , n = 0.
The shifts cannot be decomposed further since the function executes until n > 0.
We get the final set of moves in which the disks are moved from one peg to another.
Taking the image as reference, if we traverse the moves(only) in pre-order fashion, we get the correct sequence in which the disks are moved between the pegs.

The correct order of implementation of Tower of Hanoi is given as follows:

X – Z.
X – Y.
Z – Y.
X – Z.
Y – X.
Y – Z.
X – Z.

Implementation of Tower of Hanoi(C – Code)

#include<stdio.h>
 
void TH(int,char,char,char);
 
void main()
{
	int n;
	printf("Enter the number of plates: ");
	scanf("%d",&n);
	TH(n,'X','Y','Z');
}
 
void TH(int n,char a,char b,char c)
{
	if(n>=1)
	{
		TH(n-1,a,c,b);
		printf("\n%c -> %c",a,c);
		TH(n-1,b,a,c);
	}
}