Data Structures Homework 2, Fall 1999

Due: Sept 21, 1999, 12:00 PM (Absolutely no late homeworks accepted)

In this homework, you will implement the entire puzzle. The solution to the puzzle uses two lists: CheckedList and UnCheckedList (also referred to as open and closed lists in the search community). The starting point is provided by the following java files: Board.java, BoardSuccessors.java, Test.java, CheckedListAbstract.java, and UnCheckedListAbstract.java. Following is the description of these files:

Board.java : This is the Board class written by you in the previous homework. I am supplying a copy written by your TA George Iakovou (Thanks George) so that all of you can start from the same point irrespective of your performance on homework 1. This class contains one additional method: IsTheSolution over and above what you have written. You can choose your own classes (with the added methods) if you want to. Ensuring compatibility will be your responsibility though.
BoardSuccessors.java : This is the BoardSuccessors class written by you in the previous homework. Note that it does not contain any additional methods.
Test.java : This is your tester program. This is different from the Test.java from the first homework. The tester works by generating an initial board position. It inserts this board into UnCheckedList. It then enters a while loop that repeatedly extracts nodes from the UnCheckedList, expands them and inserts successors into the UnCheckedList if they have not already been seen (i.e. they do not exist in CheckedList). This is done until the solution is found or UnCheckedList is empty.
CheckedListAbstract.java : Contains abstract methods and data structures for the CheckedList. Note that CheckedList requires addition of Boards and removal of least cost Board. You are allowed to use the vector class for implementing CheckedList if you choose to do so.
UnCheckedListAbstract.java : Contains abstract methods and data structures for UnCheckedList. Note that the major operations here are addition to list and to see if a Board exists in the closed list.
Puzzle.class : Finally, when you get everything done using Test.java, you can also use the applet (Puzzle.class) to run your program. The applet works as follows: each mouse click on the applet displays the current Board that is being explored. Note that as the search proceeds, your Boards get closer to the solution. Also note that the movement is not sequential (as in, there are jumps in board configurations). This is because of the nature of the search.

When you get everything done, this is what your solution applet will look like:

Download all files as before and enjoy your coding. Make sure to have your images subdirectory in the directory in which these files are stored (otherwise you will see a blank applet). Here is the link for downloading the files.