Computer Science 2311
Spring 2005
Programming Assignment 4

Date assigned: 2/2/05

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.

It is convenient to refer to the posts by names, such as A, B and C. Instructions to move three disks from A to C are as follows.

  Move a disk from A to C.
  Move a disk from A to B.
  Move a disk from C to B.
  Move a disk from A to C.
  Move a disk from B to A.
  Move a disk from B to C.
  Move a disk from A to C.

The assignment

Write a Java program that prints instructions for solving the Towers of Hanoi puzzle. It should allow the user to decide how many disks there are, and what to call the three posts. So your program 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. a character to use for the other post.

Additional requirements

The disks are numbered from the top to the bottom, with disk 1 on top. Each instruction should say which disk is to be moved. It will always be the topmost disk, but give the disk number anyway.

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 M. Then the following would be printed.

  1. Move disk 1 from L to R.
  2. Move disk 2 from L to M.
  3. Move disk 1 from R to M.
  4. Move disk 3 from L to R.
  5. Move disk 1 from M to L.
  6. Move disk 2 from M to R.
  7. Move disk 1 from L to R.

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. Here is the function that we wrote in class.

//========================================================
// hanoi(n,start,end,extra) prints instructions to move
// n disks from post start to post end, using post
// extra for storage.
//========================================================

public static void hanoi(int n, char start, char end, char extra)
{
  if(n > 0) 
  {
    hanoi(n-1, start, extra, end);
    System.out.println("Move a disk from " + start + 
                       " to " + end);
    hanoi(n-1, extra, end, start);
  }
}

Modify the hanoi function so that it takes one more parameter, the instruction number to use for the first line. Also modify it so that it returns the number of moves used. For example, hanoi(3, 'L', 'R', 'M', 12) would print instructions starting at line 12.

  12. Move disk 1 from L to R.
  13. Move disk 2 from L to M.
  14. Move disk 1 from R to M.
  15. Move disk 3 from L to R.
  16. Move disk 1 from M to L.
  17. Move disk 2 from M to R.
  18. Move disk 1 from L to R.

Think carefully about the parameters to use in the recursive calls to hanoi, and what to do with the value that hanoi returns. Be sure that your documentation correctly describes the updated method.

Turning in your program

Test your solution, and check whether the instructions that it prints work. Do not ask the user which line number to start with. Start with line 1. (Can you see why you generalized hanoi to start with any line number?)

When it is working, print your program 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.

A note on reading characters

To read a character, read a line as usual. That gives you a string. Now just get the first character of the string. The first character of string s is s.charAt(0).