Problem Description
In a monastery in Benares India there are three diamond towers holding 64 disks made of gold. The disks are each of a different size and have holes in the middle so that they slide over the towers and sit in a stack. When they started, 1500 years ago, all 64 disks were all on the first tower arranged with the largest on the bottom and the smallest on the top. The monks' job is to move all of the disks to the third tower following these three rules:
1. Each disk sits over a tower except when it is being moved.
2. No disk may ever rest on a smaller disk.
3. Only one disk at a time may be moved.
The monks are very good at this after all this
time and can move about 1 disk per second.
When they complete their task, THE WORLD WILL END! The question is, how much time
do we have left?
Techniques & Background
This is version 1 of the Towers problem. It knows what to do, but
doesn't really do it.
Coming are Version 2, makes the moves internally and displays a list of which
disks move to which pegs and Version 3 which adds graphics so you can drag the
disks around or watch the program move them.
But first to solve the basic problem. Here is a good example
of the method of mathematical proof known as "Mathematical
Induction". The Induction method applied to our problem says
that if you can solve it for one disk and if, assuming you can solve the problem for
M disks, you can tell how to solve it for M+1 disks, then you can solve the problem for any
number of disks!
So, we can surely solve the problem for one disk - just move
it. Given
a stack of M+1 disks, and knowing how to move M disks, can we figure out how to solve the problem? First
notice that the top M disks of this pile wouldn't know about the bottom disk at
all - since it's the largest disk, if it were alone on the tower, any other disk
could move on top of it just like it wasn't there. I'm going to use
the word "pegs" for "towers" from now on - shorter. Lets call the
pegs A, B, and C and assume that we have the M+1 disks on peg A.
We're assuming by induction that we can move the top M disks to another peg, say
to B. Presto, we did it! So we now we have peg A left with the largest disk, peg B with the
other M disks and peg C empty. Now move the largest disk from A to
C. Next, since we have a method that moves M pegs from peg A to peg
B, we can just re-label the pegs appropriately (so A has the M pegs, B
is the one with the large disk on it that we want to move the other M to, and C is the spare). Now apply our
method for moving M pegs from A to B once again and we're done!
If you look at the source code, you'll see that that is
exactly what the program does. There is a procedure called
MoveOne(A,B) that moves the top disk from peg A to peg B. In this version it
doesn't do much except add 1 to a counter and call Application.Processmessages
to give Windows a chance to do handle other messages (like the user hitting the
stop button). Later on, Moveone will list the move or do the graphics stuff.
The other major procedure is called MoveStack(n,A,B,C).
Its job is to move a stack of n disks from A to B using peg C as the spare.
It does this using another bit of magic called recursion. Recursion occurs
when a procedure calls itself. See this article
in Delphi Techniques for a more extensive
discussion. To move along here, MoveStack performs the 3 steps we
described above
Procedure MoveStack(n,A,C,B:Integer);
Begin
If n=1
then MoveOne(A,C); {If there's only one to move, move it}
else
Begin
{Move n-1 disks from peg
A to peg B using C as the spare}
MoveStack(n-1,A,B,C);
MoveOne(A,C); {Move 1 disk to Peg C}
{Then move n-1 disks from B
to C using A as the spare}
MoveStack(n-1,B,C,A);
end;
end;
That's it. Some code to display output and to let the
user stop if he puts in a big number and estimate time to complete and we're
done. For now.
Running/Exploring the Program
