x Programming Assignment 2 Computer Science 102

Programming Assignment 2

Computer Science 102

Spring 2005

First draft due TUE, MAR 1, 11:59 pm (midnight). Each successive draft is due as indicated at the bottom of this writeup. .

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.

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 one. Replace scramble() with init() in the main method, and run the program.

Step 2. Write a method called randomize() that switches the blue tile with an adjacent one until 30 valid and non-trivial switches (see Step 3)have been performed. To do this generate a random digit direction between 0 and 3. Use the indices i and j initialized to zero, as thay are used in the fifteen program, and either increment or decrement one of them depending on direction's value. Use a switch statement for this. Write a method called valid that checks if an index falls within the 0 to 3 range. If it does, execute moveSquare(i,j) as given in the fifteen program. If not, reset the index. This should be reminiscent of a random walk. Insert a pause between moves by executing Thread.sleep(250) nested in a try-catch block. Beware, once you implement a button listener in the later steps, the sleep will not function properly. Finally, place the call to randomize() in the main method after init.

Step 3. Lets say that in step 3 a 0 indicates a move to the left and 1 a move to the right. Then the sequence of moves 01 or 10 would indicate that the blue tile reverts to its original position constituting a trivial move. Similarly 23 or 32 would indicate the same thing. Correct for this by not executing the moveSquare() etc. in these cases.

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 index 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.

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

Step 5. Make i and j used in randomize() instance variables. This will enable you to write method retrace() which retraces the steps after the randomize method is finished. In retrace() use a switch statment nested in a while that changes either i or j 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 in randomize() originally indicated that i-- be executed, now in retrace() it indicates that i++ be executed. This allows you to retrace the steps generated by randomize. Place a pause that is twice the time of that used in randomize to enable you to tell when the program is retracing the steps executed in scrambling the tiles. Place retrace() after randomize in the main method.

Draft #2

Rewrite draft #1 using the ListIterator and LinkedList class of the Java API.

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. If you print the contents of the list you won't need this statement.

Draft #3

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 scramble and retrace button and place these buttons on the NORTH part of the layout. Activate these buttons so that:

  1. No pause is used in scrambling the buttons.
  2. When the scrambling is done, each time the blue button is clicked, the program executes one swap in retracing the scrambling.
  3. The "solve" button only serves a purpose if you want to change the blue button's color to red directly before the retracing. Include the "solve" button" anyway.

Draft #2 is due SAT night, MAR 5. Draft #3 is due THURS night, MAR 10.