x Programming Assignment 2 Computer Science 102

Programming Assignment 2

Computer Science 102

Spring 2009

First draft due TUES, MAR 10, 11:59 pm (midnight). Each successive draft is due as indicated at the bottom of this writeup. The midterm is WED MAR 4. PLease start this assignment immediately inorder to be able to adequately prepare for the exam! I will be reviewing JFrames on MON. To prepare for this, see my GUI class programs from this term. .

Draft #1 Introduction
The first draft of this project requires you to write a program that solves the fifteen puzzle by retracing the moves that were randomly made by switching the blue tile with an adjacent one. Implement the tiles with buttons. ( See the fifteen demonstration program on the course homepage. You will be using it as the basis for your solution.) Some of the logical flow of the required program will be new to you. If you click a button, the logic of your program will be event driven, that is, the logical flow will be dictated by an event --a button click-- recognized in the constructor, after the seqence of methods in the main method have been executed. When you execute your program, you will scramble the tiles by clicking the gray tiles vertically or horizontally adjacent to the blue tile. You will indicate that you have finished scrambling the tiles by clicking a button labelled End. When you do this, the path you took will be printed on the MS-DOS window (the one that is used for output). Do this by using a print() method that employs a iterator class (call it TheIterator) that you write. Then a readout on top of the screen will instruct you to click a button called Solve. The program will retrace the steps used in scrambling the tiles and when it's finished, the readout will indicate that the puzzle is solved.

You may choose to write your solution as a sequence of a few steps.

Step 1. Write a method called init() that places the blue button in the upper left hand corner as shown below.

1 2 3
4 5 6 7
8 91011
12 131415

Use scramble() from the fifteen program as a guide. Of course, you will not be using the random() method and the tiles will be labeled with consecutive integers starting with the number one. Replace scramble() with init() in the main method, and run the program.

Step 2. Place a panel at the top of the frame which has a button called End on the EAST side and one called Solve on the WEST side sandwiching a label in the CENTER. Here's how to do it: Place the sixteen buttons on a panel p1 and using container.add(p1, BorderLayout.CENTER); add the panel to the frame. Then create another panel p2 containing a End and Solve button and place these buttons on the NORTH part of the layout. Alter moveSquare(i,j) so that:

where direct indicates the direction the tile just clicked has moved. Here are the directions:
      ^ 0 
   3<- -> 2 

In the actionPerformed method, alter the nested for loop so that after a tile is moved in moveSquare, the value of direct is added to a node of a doubly-linked list. Note that the loop indices are not defined after the nested loop so that the coordinates, i, j, of the tile clicked will have to be saved in the global variables r, c, respectively.

Step 3. Insert a pause between the retracing moves by executing Thread.sleep(250) nested in a try-catch block. Beware, the sleep will not function properly unless the actionListener part for the Solve button has a separate thread (See the "Using threads" writeup on the homepage).

Step 4. Write a DoublyLinked class that will enable you to generate a doubly linked list in which each node contains a move, either 0, 1, 2, or 3. This type of list besides having a next field has a previous field that points to the previous node. It will also have front and rear fields like a queue. Each time your program generates a valid move, the the value of direct should be stored in the next node of the list. When the tiles are scrambled, your program should print the moves on the MS-DOS output screen by traversing the linked list. Use the TheIterator class you write to do this

The DoublyLinked class should have the following instance variables and methods:
Link front, rear, current;

Step 5. Since r and c are instance variables, you will be able to write method retrace() which retraces the steps after the tile scrambling is finished. In retrace() use a switch statment nested in a while that changes either r or c in the opposite direction to that of the value obtained from the nodes of the linked list. So that if a 1 is on the node in the linked list and 1 originally indicated that j++ be executed, now in retrace() it indicates that j-- be executed. This allows you to retrace the steps generated by scrambling the tiles. Note the retrace() method will be activated when the Solve button is clicked. The "solve" button should change the blue button's color to red directly before the retracing.

Draft #2

Remember that ListIterator itr = list.listIterator() resets the pointer to the beginning of the list. If you print before you retrace, the pointer will be placed at the end of the list. If you omit the printing, the pointer will be at the beginning of the list and retacing will cause an error. Note: ListIterator itr = list.listIterator(list.size() ) places the pointer at the end of the list.

Both the global LinkedList and ListIterator references must be declared static if you instantiate them in the main method. In jdk 1.5, your must import these two types explicitly, i.e.

import java.util.LinkedList;
import java.util.ListIterator;

Draft #2 is due WED night, 11:59pm, MAR 11.