Skip to main content

Tower Of Hanoi

 

Tower Of Hanoi


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

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:

  1. X – Z.
  2. X – Y.
  3. Z – Y.
  4. X – Z.
  5. Y – X.
  6. Y – Z.
  7. X – Z.

Comments

Post a Comment

Popular posts from this blog

HackerRank Tuples Solution in Python

  HackerRank Tuples Solution in Python Task Given an integer,n, and n  space-separated integers as input, create a tuple, t, of those n integers. Then compute and print the result of hash(t). Note:   hash()  is one of the functions in the  __builtins__  module, so it need not be imported. Input Format The first line contains an integer,n, denoting the number of elements in the tuple. The second line contains n space-separated integers describing the elements in tuple t . Output Format Print the result of  hash(t) . Sample Input 0 2 1 2 Sample OUTPUT- 3713081631934410656 n = int(input()) int_list = [int(i) for i in input().split()] int_tuple = tuple(int_list) print(hash(int_tuple))
Post a Comment
Read more

How to check if the given number is Even or odd-

1. How to check if the given number is Even or odd- We can determine whether a number is even or odd. This can be tested using different methods. The test can be done using simple methods such as testing the number’s divisibility by 2. If the remainder is zero, the number is even. If the remainder is not zero, then the number is odd. The following algorithm describes how a C program can test if a number is even or odd. CODE:- #include <stdio.h> int   main () { int num;//variable declaration printf("Enter any num: ");// take input from user  scanf("%d",&num);// declare input if(num%2==0) { printf("The num %d is even",num); } else { printf("The num %d is odd",num); } return 0; }     ALGORITHM:- Step 1.   Start Step 2 .   Enter a number. Step 3.   If...
3 comments
Read more

Binary to Decimal conversion program

  3. Binary to Decimal conversion program using C language:- The C program converts binary number to decimal number that is equivalent. A decimal number can be attained by multiplying every digit of binary digit with a power of 2 and totaling each multiplication outcome. The power of the integer starts from 0 and counts to n-1 where n is assumed as the overall number of integers in a binary number. Ex:-   ( 101100001 ) 2 =( 353 )10                                                  ALGORITHMS:- Step 1:  Start Step 3:  The user is asked to enter a binary number as an input Step 4:  Store the quotient and remainder of the binary number in the variable rem Step 5:  Multiply every digit of the entered binary number beginning from the last with the powers of 2 correspondingly Step 6:  Repeat the above step...
Post a Comment
Read more