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:
  1. They may only move one ring at a time.
  2. 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:

  1. Move n-1 rings from the source pole to the spare pole using the destination as the spare.
  2. Move the single ring from the source pole to the destination pole.
  3. 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.