Chris Pollett>Old Classes>PIC 20, Winter 2000>Hw4
For this homework you will need to submit three files: FPuzzle.php, FPuzzle.java and Puzzle.java. Your job is to write an JApplet to allow you to play a Tile Puzzle game (sometimes known in the 3X3 case as an 8-puzzle). The purpose of this assignment is to get you familiar with the Java2D API, as well as working with the Graphics class, JPanels, LayoutManagers and the different kinds of widgets available in Java. On this assignment you will also have the opportunity to receive bonus points which will be added to your grade after the final curve has been set. The difficulty of this homework depends on how many of the bonus points you go for.
Here is my version of the applet:
The bare minimum you need to do for this assignment to get full credit is
the following: (0) The class FPuzzle which extends JApplet should use a
BorderLayout. (1)Your applet must have a title printed on
a JLabel in some
font other than the standard. (2) The actual image of the puzzle should
live on the class Puzzle which extends JPanel. You are required
to use the Java2D API in drawing the Puzzle overriding the JPanel's paint
method. (Draw an outer rectangle,
then draw the tiles inside using fills and gradient paints).
(4) Your applet needs to have a randomize button. (5) You need
a JPanel that uses GridLayout and has on it a JLabel with "SizeSelector"
printed on it, a JComboBox to select puzzle size, and another
JPanel. (6) This other JPanel has four buttons on it to control
the slide of the pieces on the puzzle. It should use a BorderLayout
(7) Listeners on the appropriate Components to detect button presses and items
selected. To keep things simple use anonymous inner classes to implement
these. Changing the item on the JComboBox should change the size of the
Puzzle, pushing the direction buttons should move the tiles appropriately.
(8) Your Puzzle class should keep track of the pieces in the puzzle using
an array. It should have a public void move(int i) which
on an integer 0,1,2,3 causes a piece the blank tile to move internally NORTH,
SOUTH, EAST, WEST respectively. By internally, I mean when a repaint()
of the Puzzle occurs you will see the change. Note you are allowed
to let your pieces in your solution move in discrete steps; it doesn't
have to animate like in my example. (9) Your Puzzle class should have
a method randomize() which produces a random but legal board. i.e., one
where you can get all the pieces in ascending order from least to greastest.
This can be done by doing say 100 random moves on the board. Clicking
the randomize button will call this method.
(10)Also make sure to document each function you write to a similar degree
of description as I do in the solutions. This is worth one point of the
assignment. (11) Remember your honesty statement or your assignment won't
be graded. (12) Make sure you have the files names correct.
Bonuses: You can get a maximum of 5 bonus points on this assignment. Here the possible ways to get bonus points:
(1) Have it so when the tiles are aligned in the correct order the tiles altogether draw a single picture, That wouldn't be intelligible it they weren't all in order. (1pt)
(2) Implement smoothly animated tile movements. This can be done using the Timer class. (2pts)
(3) Implement the solve button using depth first search with a cut-off at some fixed depth. This can be done using recursion. If a branch does not yield a solution you can use the sum of the distances each square is out of place as a weight function (Manhattan distance). Return the path with the least weight final node. Then have the applet move the pieces according to this path. Then do another search to the same depth until find a solution or get trapped in a local minima. (3pts)
(4) Implement the solve button using Iterated Deepening. i.e., Do a depth first search to depth 1, then depth 2, then depth 3, etc until find a solution. This has the advantage of breadth first search in that you don't got stuck on a long path that doesn't work. But it uses the same space as depth first search. Timewise it takes about the same as breadth first search (4pts).
(5) Implement the solve button using the A* algorithm. (Will describe in class). (5pts)