Programming Project: Towers of Hanoi

Ledgend has it that in an ancient and secret monastery, 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 Frames, drawing graphics, and recursive algorithms.

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, 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 Vector<Integer> to model the piles of disks. The astute reader will notice that piles are, in fact, stacks of disks and thus your model should treat the representation as Stack ADTs. Each individual disk will be represented by an integer, the value of which corresponds to its size. To use the vector as a pile, remove and add disks from the end. (Not the beginning. Why?) For the purposes of the puzzle, you are allowed only to remove a single disk from the end of one pile and add it to the end of another pile (providing, of course, the size of the disk being added is less than that of the disk currently at the end -- i.e., 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 Vector 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, Vector<Integer> pileA, Vector<Integer> pileB, Vector<Integer> pileC). As with any recursive problem, think about an appropriate base case.
  6. Paint each of the piles after each movement of a single disk from one pile to another. You should include a delay of something on the order of 50ms.

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 “HW7”. For example, someone with email address “cjones” would create a folder called “cjonesHW7”. 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>HW7” will be created. Submit the packaged file for assignment 7 on Eureka.