Applications (Abstract Data Type)
Part 5 Continue
Towers of Hanoi
Towers of Hanoi
One of the most interesting
applications of stacks can be found in solving a puzzle called Tower of Hanoi.
According to an old Brahmin story, the existence of the universe is calculated
in terms of the time taken by a number of monks, who are working all the time,
to move 64 disks from one pole to another. But there are some rules about how
this should be done, which are:
1. move only one disk at a time.
2. for temporary storage, a third pole may
be used.
3. a disk of larger diameter may not be
placed on a disk of smaller diameter.
For algorithm of this puzzle see Tower of Hanoi.
Assume that A is first tower, B is
second tower & C is third tower.
Towers of Hanoi step 1
Towers of Hanoi
step 2
Towers of Hanoi step 3
Towers of Hanoi
step 4
Tower of Hanoi
Output: (when there are 3 disks)
Let 1 be the smallest disk, 2 be the disk of medium size and 3 be the largest disk.
Move disk
|
From peg
|
To peg
|
1
|
A
|
C
|
2
|
A
|
B
|
1
|
C
|
B
|
3
|
A
|
C
|
1
|
B
|
A
|
2
|
B
|
C
|
1
|
A
|
C
|
The C++ code for this solution can be
implemented in two ways:
First implementation (without using stacks)
void TowersofHanoi(int n, int a, int b, int c)
{
if(n > 0)
{
TowersofHanoi(n-1, a,
c, b);
//recursion
cout << " Move top disk from tower " <<
a << " to tower " << b << endl ;
TowersofHanoi(n-1, c,
b, a);
//recursion
}
}
Second implementation (using stacks)
// Global variable , tower [1:3] are
three towers
arrayStack<int> tower[4];
void TowerofHanoi(int n)
{
// Preprocessor
for moveAndShow.
for (int d = n;
d > 0; d--)
//initialize
tower[1].push(d); //add disk d to
tower 1
moveAndShow(n, 1, 2, 3); /*move n disks
from tower 1 to tower 3 using
tower 2 as intermediate tower*/
}
void moveAndShow(int n, int a, int b, int c)
{
// Move the top
n disks from tower a to tower b showing states.
// Use tower c
for intermediate storage.
if(n > 0)
{
moveAndShow(n-1, a,
c, b);
//recursion
int d = tower[x].top(); //move a disc
from top of tower x to top of
tower[x].pop(); //tower y
tower[y].push(d);
showState(); //show state of
3 towers
moveAndShow(n-1, c,
b, a);
//recursion
}
}
However complexity for above written implementations is O(
). So it's obvious that problem can
only be solved for small values of n (generally n <= 30).
In case of the monks, the number of
turns taken to transfer 64 disks, by following the above rules, will be
18,446,744,073,709,551,615; which will surely take a lot of time.
Notes
continue into the next blog:
Applications part 5 Continue (Abstract Data Type (ADT))
J.W. PRODUCTION