If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves, it would take them 264−1 seconds or roughly 585 billion years; it would take 18,446,744,073,709,551,615 turns to finish.
There are many variations on this legend. For instance, in some tellings, the temple is a monastery and the priests are monks. The temple or monastery may be said to be in different parts of the world — including Hanoi, Vietnam, and may be associated with any religion. In some versions, other elements are introduced, such as the fact that the tower was created at the beginning of the world, or that the priests or monks may make only one move per day.
The Flag Tower of Hanoi may have served as the inspiration for the name.
Towers of Hanoi
The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It consists of three pegs, and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks in a neat stack in ascending order of size on one peg, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another peg, obeying the following rules:
1. Only one disk may be moved at a time.
2. Each move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg.
3. No disk may be placed on top of a smaller disk.
Recursive Solution:
A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. The following procedure demonstrates this approach.
-> label the pegs A, B, C—these labels may move at different steps
-> let n be the total number of discs
-> number the discs from 1 (smallest, topmost) to n (largest, bottommost)
To move n discs from peg A to peg C:
1. If n == 1, move the single disk from peg A to C and stop.
2. Move the top n-1 disks from A to B, using C as auxiliary.
3. Move the remaining disk from A to C.
4. Move the n-1 disks from B to C, using A as auxiliary.
The C Program to solve the Towers of Hanoi problem:
#include
void towers(int, char, char, char);
void main(){
int n;
printf(“Enter the number of Disks : “);
scanf(“%d”,&n);
towers(n, ‘A’, ‘C’, ‘B’);
} /* end main */
void towers(int n, char frompeg, char topeg, char auxpeg){
/* if only one disk, make the move and return */
if(n==1){
printf(“Move disk 1 from peg %c to peg %c”, frompeg, topeg);
return;
} /* end if */
/* Move top n-1 disk from A to B, using C as auxiliary */
towers(n-1, frompeg, auxpeg, topeg);
/*Move remaining disk from A to C */
printf(“Move disk %d from peg %c to peg %c”, n, frompeg, topeg);
/* Move n-1 disk from B to C using A as auxiliary */
towers(n-1, auxpeg, topeg, frompeg);
}
Terms
if n=1,3,5,7,…(i.e.odd),
(i) odd numbered disk should jump
i.e. if disk 1 is at peg A, jump to peg C
(or) if disk 1 is at peg B, jump to peg A
(ii) even numbered disk (Ex: disk 2) should move to
next consecutive peg(Ex: peg A to pegB)
———————————————————————————–
if n=2,4,6,8,10,…(i.e.even),
(i) even numbered disk should jump
i.e. if disk 2 is at peg A, jump to peg C
(or) if disk 2 is at peg B, jump to peg A
(ii) odd numbered disk (Ex:a disk 1) should move to
next consecutive peg(Ex: peg A to pegB)
———————————————————————————–
Example 1: n=1(i.e. odd)
1 A->C
Example 2: n=2(i.e. even)
Step 1:
Write the number 1 before and after number 2
and write ‘A’ corresponding to first 1 and 2 since peg A has 1 and 2 disks
1 A
2 A
1
Step 2:
-> disk 1 is odd so move to next consecutive peg
-> disk 2 is even so jump from A to C
1 A->B
2 A->C
1
Step 3:
->disk 1 is currently in peg B and it is odd so move from B to C
1 A->B
2 A->C
1 B->C
———————————————————————————–
Example 3: n=3(i.e. odd)
Step 1:
Write the number 1,2,1 before and after number 3(This series 1,2,1 was obtained from n=2)
and write ‘A’ corresponding to first 1,2 and 3 since peg A has 1,2 and 3 disks
1 A
2 A
1
3 A
1
2
1
Step 2:
-> disk 1 is odd so jump from A to C
-> disk 2 is even so move to next consecutive peg
1 A->C
2 A->B
1
3 A
1
2
1
Step 3:
->disk 1 is currently in peg C and it is odd so jump from C to B
1 A->C
2 A->B
1 C->B
3 A
1
2
1
Step 4:
->disk 3 is currently in peg A and it is odd so jump from A to C
1 A->C
2 A->B
1 C->B
3 A->C
1
2
1
Step 5:
->disk 1 is currently in peg B and it is odd so jump from B to A
1 A->C
2 A->B
1 C->B
3 A->C
1 B->A
2
1
Step 6:
->disk 2 is currently in peg B and it is even so move from B to C
1 A->C
2 A->B
1 C->B
3 A->C
1 B->A
2 B->C
1
Step 7:
->disk 1 is currently in peg A and it is odd so jump from A to C
1 A->C
2 A->B
1 C->B
3 A->C
1 B->A
2 B->C
1 A->C
Comment below if you find this blog useful.