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 goalWe 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.
~meeden/Public/cs63/lab2-search/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:
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 EUse 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.