Introduction:
The Tower of Hanoi (also
called the Tower of Brahma or Lucas' Tower and sometimes
pluralized) is a mathematical game or puzzle. It consists of
three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts with the disks in a neat stack in ascending order of size on
one rod, the smallest at the top, thus making a conical shape.
The objective of the
puzzle is to move the entire stack to another rod, obeying the following simple
rules:
1.
Only one
disk can be moved at a time.
2.
Each
move consists of taking the upper disk from one of the stacks and placing it on
top of another stack.
3.
No disk
may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves.
The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n −
1, where n is the number of disks.
We have n disks &
three tower named as tower1, tower2, tower3. We have to move the entire disk
from tower1 to tower3 according tower of Hanoi rule. The simple solution is to
move first (n-1) disks from tower1 to tower2 using help of tower3. Now move
last disk (the biggest one) from tower1 to tower3. Then move the (n-1) disks
from tower2 to tower3 using help of tower1.
In short
TOH(n,t1,t2,t3) = TOH(n-1,t1,t3,t2)
-> TOH(1,t1,t2,t3) {move biggest disk from
t1 to t3} -> TOH(n-1,t2,t1,t3)
We can put the solution in base system 6 as follows:
(Encoding possible values in base 6)
char1 char2 value
move notation
1 2 0 move disk from tower1 to tower2
1 3 1 move disk from tower1 to tower3
2 1 2 move disk from tower2 to tower1
2 3 3 move disk from tower2 to tower3
3 1 4 move disk from tower3 to tower1
3 2 5 move disk from tower3 to tower2
It means the solution contains digits on 0-5 & every
digit will notify one move.
Now one digit among 0 to 5 can be stored into maximum of 3
bits so 8 moves will require the memory of 3 bytes.
3 bytes = 24 bits = 8 * 3 bits = memory for 8 moves;
Because the solution has (2^n)-1 moves, so the minimum
memory required for the solution of n disks is equal to Ceiling((3*((2^n)-1)/8))
bytes.
If n=64 the memory size will be 6 Exabyte.
1 Exabyte = 1,07,37,41,824
GB
Allegedly,
"all words ever spoken by human beings" could be stored in
approximately 5 Exabytes of data.
Source code:
#include <stdio.h>
#include <conio.h>
#include <time.h>
short BaseSixCoded(char c1, char c2)
{
switch(c1)
{
case 1:
return((c2 == 2) ? 0 : 1);
case 2:
return((c2 == 1) ? 2 : 3);
case 3:
return((c2 == 1) ? 4 : 5);
}
return 0;
}
// a function for the solution of tower
of hanoi
void TowerOfHanoi(unsigned int NumberOfDisks, char B, char A, char E)
{
if (NumberOfDisks)
{
TowerOfHanoi(NumberOfDisks - 1, B, E, A);
printf("%d", BaseSixCoded(B, E));
TowerOfHanoi(NumberOfDisks - 1, A, B, E);
}
return;
}
int main()
{
TowerOfHanoi(64,
1, 2, 3);
_getch();
return 0;
}
