INTRODUCTION

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:

• an initial state
• a goal state
• the set of possible operators on states

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

 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

GETTING STARTED

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

~meeden/Public/cs63/lab2-search/

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.

LAB INSTRUCTIONS

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

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?

HAND IN

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.