CPSC 170 Spring 2005
Program 2: Towers of Hanoi
Due Friday, March 4, 2005
Description
As we discussed in class, Towers of Hanoi is a game with 3 "needles" (pegs)
and N graduated disks. Initially the disks are all on the first needle,
with the largest on the bottom and the smallest on the top. The object
of the game is to move all of the disks to the second needle while abiding
by the following rules:
- Only one disk may be moved at a time.
- A larger disk may never be placed on top of a smaller disk.
We discussed an elegant recursive solution to this problem, and that
it takes 2N-1 moves to transfer N disks from the first needle
to the second following these rules.
Your assignment is to write an interactive program that
graphically demonstrates the
Towers of Hanoi game for a variable number of disks. Your program should have the following behavior:
- The program should take an integer from the command line indicating the
number of disks (N). If no number is provided, it should use 8 disks.
- When the program starts, it should show N disks on the first needle.
- When the user clicks anywhere (or strikes a key, if you prefer),
the program should
move the next disk as appropriate in the sequence of moves that make
up the solution. Thus if there are two disks,
on the first click it should move the top (smallest)
disk to the third needle; on the second click it should move the next disk
to the second needle, and on the third click it should move the disk on the
third needle to the second needle, forming a stack of two disks.
- The program should display a counter indicating how many moves have
been made.
- If the user tries to keep moving disks after the solution has been
reached, nothing should happen.
Note that the user does not get to choose what moves are made; the clicks
just prompt the next move toward the solution.
To see a demo program, cd to ~cpsc/public_html/CPSC170A/hanoi
and run the Towers program (java Towers).
Program Structure
You may organize your program in any way you like as long as it is clean,
correct and reasonably efficient. Here are some suggestions:
- First generate and store a list of all the moves to transfer the given number of
disks to the other needle. This part of the program will look much like
what we did in class (and what's in the book). Then when the user clicks,
just take the next move from the list and make it happen. You may wish to
write a Move class to represent a move.
- Write a Needle class to represent a single needle. This class should
include methods to add a disk to the needle, remove a disk from
the needle, and draw the needle (that is, draw the disks on the needle).
- Write a TowerPanel class in which you create and draw the
three needles (with their disks), put the requested number of disks
on the first needle, and respond to mouse clicks by moving disks
as appropriate.
This class will be a JPanel and will need to either
implement the MouseListener interface or contain an inner class that does.
It will also need a method to generate and store the moves so that
the next move can be accessed when the user clicks the mouse. Finally,
this class will need a paintComponent method to draw the three needles
(which is easy, since they know how to draw themselves!) along with the count.
- Write a Tower class that looks for a command line argument indicating
the number of disks and uses it to
create a TowerPanel object. If there is no command line argument, it should
use 8 disks.