CS63 Fall 2002
Lab 2: State Space Search
Due: Friday, September 20, by noon



State space search is a powerful technique for solving problems. However, in order to apply this technique we need to formulate the problem so that we have the following information:

For this homework, we will apply state space search to the infamous eight puzzle problem. The eight puzzle consists of a three by three board with eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into the space. The object is to figure out the steps needed to get from one configuration of the tiles to another.

For this problem, a state should specify the location of each the eight tiles as well as the blank space in the three by three grid. The operators are most efficiently represented as moving the blank left, right, up or down, rather than creating operators for each of the numbered tiles.

For example, suppose we wanted to get from the initial state to the goal state given below.

 1 2 3   1 2 3
 8   6   8   4
 7 5 4   7 6 5 
 initial goal
We could accomplish this with the following sequence of operators on the blank.
 1 2 3   1 2 3   1 2 3   1 2 3   1 2 3
 8   6   8 6     8 6 4   8 6 4   8   4
 7 5 4   7 5 4   7 5     7   5   7 6 5
 step1	 step2	 step3	 step4	 goal
 right   down    left    up


Copy the scheme files provided in the directory below to your home directory.

There are two files: search.ss and missionary.ss. The search.ss file contains an implementation of general search. The missionary.ss file contains a formulation of the missionary and cannibals problem to be used with general search. To test search on this problem, do the following:
  1. At the unix prompt type: drscheme missionary.ss
  2. At the bottom of this file you will see a load command and a call to the search function. In drscheme, press the execute button to start the search.
  3. The global variables maxM and maxC determine the number of missionaries and cannibals trying to cross the river. Try creating an illegal state of 2 missionaries and 1 cannibal and then re-execute the search. Try creating an easier state of 1 missionary and 2 cannibals and re-execute the search.
  4. Familiarize yourself with the Scheme implementation of general search and the missionary and cannibals problem.


Part A: Using the missionary.ss file as a model, create an 8puzzle.ss file that implements states, operators, an expander, and a displayer for the 8 puzzle problem that can be used with the search function provided. Make sure that your expander function does not generate states that return to the parent state.

Test your solution on the following starting states A-E (each is progressively harder) using the same goal each time.

 1 2 3   1 3     1 3 4     1 3   7 1 2   8 1 2
 8   4   8 2 4   8 6 2   4 2 5   8   3   7   4
 7 6 5   7 6 5     7 5   8 7 6   6 5 4   6 5 3
 goal      A       B       C       D       E
Use the add-to-back queuer, and record the number of nodes that are expanded for each test.

Part B: Create a new version of the repeated-state? helper function within the expander that uses a hash table to maintain a record of every state generated so far. Rename the original helper and keep it so that you can switch back to it later.

Re-run the test cases again using the same queuer and the new repeated state checker, and record the number of nodes expanded now.

Part C: Copy the original search.ss file to a new file called depth-limited.ss. Change the general search function into a depth limited search and then use this to implement iterative deepening.

Re-run the test cases one more time using the add-to-front queuer and reverting back to the old version of repeated-states? without the hash table. Be sure to sum up the number of nodes expanded over all of the calls to depth limited search.

Part D: Discuss the results within a comment in your file. What is the branching factor b for the 8 puzzle problem? What is the depth of the shortest path d for each test case? Part A is a breadth-first search, Part B is a breadth-first search without repeated states, and Part C is iterative deepening search. Do the recorded values fall within the theoretical limits discussed in the book?


Use cs63handin to submit both your 8puzzle.ss file and your depth-limited.ss file. Your table of test results and discussion of the results should be included in the 8puzzle.ss file as comments.