When Will the World End?
There is an old legend about a group of eastern monks.
They are the keepers of a puzzle that consists of three
poles and 64 golden rings.
These rings are all of different sizes and all started out
on the same pole with the largest on the bottom decreasing
in size to the smallest on the top.
Their task is to move the 64 rings from the first pole to the
last pole subject to two conditions:
- They may only move one ring at a time.
- They may never move a larger ring on top of a smaller ring.
When they finish the puzzle the world will come to an end.
This puzzle is usually called the Towers of Hanoi.
We can define a recursive solution to the puzzle as follows.
To move n rings from the source pole to the destination pole with a
spare pole:
- Move n-1 rings from the source pole to the spare pole using the
destination as the spare.
- Move the single ring from the source pole to the destination
pole.
- Move n-1 rings from the spare pole to the destination pole
using the source pole as the spare.
You should make sure you understand this recursive solution by
stepping through it with four rings.
It should take you 15 moves.
This solution algorithm is naturally amenable to implementation
in C.
Assuming we only want to print out the moves of the individual
rings, our function might look like:
void towers( int n, int src, int dest, int spare )
{
if( n > 0) {
towers( n - 1, src, spare, dest ) ;
printf( "Move a ring from tower %d to tower %d\n",
src, dest ) ;
towers( n - 1, spare, dest, src ) ;
}
As with all the other recursive functions and algorithms we need
a stopping condition for this.
As we start with n, we continually decrease it toward 0.
When we hit 0, there are no rings to move and we need do nothing.
As with the algorithm, trace through this function for moving
4 rings from tower 1 to tower 3 with tower 2 as a spare.
By the way, moving 64 rings at the rate of one ring a second
will take 350 million years.
Maybe the legend isn't too far off after all.
Move on to the next part.