Computer Science 2611
Spring 2003
Programming Assignment 4

Date assigned: 2/11/03

A puzzle

The Towers of Hanoi puzzle has three posts and some number n of disks. Each disk has a hole in the middle, so that it can be put on a post, and the disks are of different sizes.

Initially, the disks are all stacked on the leftmost post, with larger disks closer to the bottom and smaller disks closer to the top. For example, if there are three disks, the puzzle starts out looking like this.

The object is move all of the disks from the leftmost post to the rightmost post. So when the puzzle is solved, it looks like this.

But there are some rules that must be followed.

  1. Only one disk can be held in your hand at a time. The other disks must be on posts.

  2. A disk can only be put down by placing it on one of the posts. For example, you can't put a disk on the table beside the puzzle.

  3. No disk can ever be put on top of a smaller disk.

The assignment

Write a program that prints instructions for solving the Towers of Hanoi puzzle. It should read four things from the user: (1) a number n of disks, (2) a source post character (3) a destination post character, and (4) an intermediate post character. Your program should print instructions for moving n disks from the source post to the destination post, using the intermediate post as a place to put disks during the move.

Number the moves, starting at move 1. For example, suppose the number of disks n is 3, the source post is called L, the destination post is called R and the intermediate post is called R. Then the following would be printed. 

  1. Move a disk from post L to post R.
  2. Move a disk from post L to post M.
  3. Move a disk from post R to post M.
  4. Move a disk from post L to post R.
  5. Move a disk from post M to post L.
  6. Move a disk from post M to post R.
  7. Move a disk from post L to post R.
The disk to be moved is always the top one on the post. The instructions do not need to say which disk that will be.

Hints and requirements

Use recursion. We wrote a function similar to what you need in class, but yours will need to do a little more. Write a function that takes five parameters:

  1. the number of disks to move;
  2. the name of the post that contains those disks (for example, if you are moving disks from post L to another post, then this parameter will be the character 'L');
  3. the name of the destination post to which they should be moved;
  4. the name of the other post (the one that is neither the source nor the destination);
  5. what number to assign the first instruction that this function prints.
Use type char for the names of the posts, since each name is just one character. Make your function print the moves and also return the number of moves that it made. For example, if your function is called with parameters
  1. numdisks = 3
  2. source = 'M'
  3. destination = 'R'
  4. other = 'L'
  5. startnum = 12
then it would print 
  12. Move a disk from post M to post R.
  13. Move a disk from post M to post L.
  14. Move a disk from post R to post L.
  15. Move a disk from post M to post R.
  16. Move a disk from post L to post M.
  17. Move a disk from post L to post R.
  18. Move a disk from post M to post R.
where the numbering has started from 12. It would return 7, since a total of 7 moves were made.

It is easy to move no disks. To move n disks from post A to post B, using post C as the other post, first ask a friend to move n-1 disks from post A to post C. Then move the largest disk from post A to post B. Finally, ask another friend to move n-1 disks from post C to post B.

Test your solution, and check whether the instructions that it prints work. When it is working, print it and turn it in. Be sure that your program is well written and well commented. Write the contract for your function into your file before you write the function body.

Do not use any global variables in your program. Rely on passing parameters.