Programming Project 6: Towers of Hanoi

Ledgend has it that in an ancient and secret monastery somewhere in the mountains of Tibet, monks are, and have been for countless generations, moving 64 golden disks of varying sizes from one pile to another in accordance with the rules (given below) set out at the beginning of the world. When the final move is completed, the world will come to an end. So it is said. For this assignment, you will implement a Java program that solves the Towers of Hanoi problem and graphically displays each step of progress in the solution sequence. You will want to draw upon what you have learned about recursive algorithms and you will now learn about Frames and drawing graphics.

Rules of the puzzle

There are exactly three places, or piles, where disks may be placed. Disks are moved one at a time. The monks moving a disk may only place it on another disk that is larger than the one being placed. Thus, a disk may never be placed on a smaller disk. Obviously, you may not insert a disk into the midst of a pile; disks may only be placed on the top of a pile. The object is to move a pile of disks from one peg to another, one disk at a time, using only the three places and without violating the size rule.

Requirements

Write a Java program (class), TOHViewer, that solves the puzzle for a given number of disks and also animates the solution sequence. In order to support the display of the solution steps, your TOHViewer class should extend java.awt.Frame. Specifically, you must:

  1. Create a window showing a base and three pegs on which disks may be placed.
  2. You will use three Stack<Integer>s to model the piles of disks. The astute reader will notice that piles are, in fact, stacks of disks and thus your model should use the stack ADT methods provided. Note, the Stack<E> class extends the Vector<E> class; thus, you will still have access to all the vector methods which may be useful during drawing. Each individual disk will be represented by an integer, the value of which corresponds to its size. For the purposes of the puzzle, you are allowed only to remove a single disk from the top of one pile (stack) and add it to the top of another (providing, of course, the size of the disk being added is less than that of the disk currently at the top of the stack on which it is being placed).
  3. Determine the desired number of disks to simulate from the first command line argument. (I suggest you not try 64.) Your class must have a constructor that takes a single int corresponding to the number of disks.
  4. Towers of Hanoi at start of puzzle Initialize the Stack corresponding to the left-most pile, or peg, to contain the given number of disks. Paint the piles. Your window should look something like the picture at the right.
  5. Using recursion, implement a puzzle solver method, solveTOH. Your solver method should have the following signature: public void solveTOH(int nDiscs, Stack<Integer> pileA, Stack<Integer> pileB, Stack<Integer> pileC). As with any recursive problem, think about an appropriate base case. You should interpret the arguments given to solveTOH as follows: move nDiscs discs from pile pileA to pile pileB, using pile pileC as a temporary space.
  6. Paint each of the piles after each movement of a single disk from one pile to another. You should include a small delay to improve viewing; something on the order of 50-200ms should work well.

Submission instructions:

Do not forget to use the javadoc constructs for your documentation and include the html file produced by the javadoc tool in your final submission. Make sure that you create a folder named with your Westmont email name followed by “Ex6”. For example, someone with email address “cjones” would create a folder called “cjonesEx6”. Make sure that inside that folder you have: for both parts of the assignment, java source files and html documentation files resulting from javadoc. Finally, either tar or zip the folder so that when we extract it, the folder “<emailname>Ex6” will be created. Submit the packaged file for Exercise 6 on Eureka.