Solving the 8-puzzle

Due: Jan 13th 11:59AM

Objective:

The Game: The 8 puzzle is a simple game played on a 3x3 board with 8 tiles numbered from 1 to 8 and a blank space. The following is a depiction of how one instance of a board might look.

1 3 5

6 7 X

8 2 4

Here X represents the blank space on the board. The goal of the game is to rearrange the tiles such that the tiles appear in the following order.

1 2 3

4 5 6

7 8 X

Any numbered tile may slide into an adjacent position if the adjacent position is the blank. The following is one of 4 valid operations.

1 2 3           1 2 3

4 X 5   =>   4 5 X

6 8 7           6 8 7

In this example, the tile numbered 5 has moved left.

For uniformity, you are required accept the following representation of the board as input. Of course, you can immediately transform it to another representation if you wish. This example board also represents the goal state of the game.

((1 2 3)

(4 5 6)

(7 8 X))

Each sub-list is a row of the board and 'X represents the blank space.

Your task

Write a general function called search that accepts the following information.

1. A list of states (initially, you will pass it a list containing the initial state)
2. A search specific function that adds states onto the search queue (more on this later) -- these functions should be called bfs dfs and astar..
3. An evaluation function or #f if none is needed
4. A cutoff depth for the search or -1 if there is no cutoff

This function should return a list of moves in the form '((move tile direction)) necessary to go from the start state to the goal state.

For example:

(search '((1 2 3) (X 5 6) (4 7 8)) bfs #f -1)

would return

((move 4 up)

(move 7 left)

(move 8 left)

Note: Use "right" and "down" for the other two directions.

Your general search function should be similar to the one written in class. This requires that you implement certain functions that are independent of the type of search that you are performing.

1. goal? will test if you have reached the goal state
2. expandState will create all successor states to the current state

In addition to these two functions, you will also write the search specific function for each of the three types of searches that you will be testing. Each search specific function should accept a list of new states, a list of current states and an evaluation function (if none is needed you can pass #f or '(). This function will return the new queue of states to continue searching with.

For testing purposes (I will not use it), you may want to implement an additional wrapper function so that you will be able to track certain statistics that I will ask for in your final report. You may also want to add functionality to your search to not expand nodes that you have already expanded.

More details on the searches you need to implement

1. Implement breadth first search. Keep in mind you will not always be able to always find solutions in the time alloted. Your bfs input function should actually just be a function that accepts the current queue, a queue of new states, and the heuristic function and return the new queue organized appropriately.
2. Implement depth first search with iterative deepening. Start with a depth of 2 and grow in increments of 1. You can always determine the depth of a state by taking the length of the current set of moves. Your dfs input function should actually just be a function that accepts the current queue, a queue of new states, and the heuristic function and return the new queue organized appropriately. In order to do the iterative deepening correctly, you can have an extra wrapper function that will repeatedly call search with different cutoffs.
3. Implement A-star search. Your astar input function should actually just be a function that accepts the current queue, a queue of new states, and the heuristic function and return the new queue organized appropriately.

When each of these 3 searches completes a search, you should return a list of the moves required to solve the puzzle. In addition, a final report (written in html) should also include for each search performed:

1. The search performed
2. The search method used
3. The solution
4. The total amount of CPU time spent on the search
5. The number of states that you tested against the goal state

For your A* search, you should write the following two heuristic evaluation functions. Each function accepts a board as an argument and returns a number greater than or equal to zero. In both of these cases the better state is the one with the smallest value (the goal state has a value of 0).

1. OutOfPlace - a count of the number of tiles not in their proper locations.

For example: ((1 2 3) (4 5 6) (8 7 X)) would score 2 since both 7 and 8 are not in their proper locations.

2. ManhattanDistance - the "distance" each tile is away from its proper location based on its "city block" distance.

For example (with Manhattan Distance): ((1 2 3) (5 6 X) (8 4 7)) would score an 8. 4 is one horizontal unit and one vertical unit away from its proper location thus receiving a score of 2. Each tile is scored likewise and the total is summed.

Test each search method and heuristic with the following states and create a table of the performance of each strategy. Include this table as a part of the comments at the top of your program. Construct at least one additional medium problem with a solution of over 20 steps and include that with your results as well. Keep in mind, some of the searches may never solve the puzzle and thus if you don't have a solution in under an hour (probably a lot less time for most). Then you are not likely to find a solution with that search method. Also note, there are possible states for which there is no solution.

State1 '((1 2 3) (7 X 5) (8 4 6)) - Easy

• Example: (search '(((1 2 3) (7 X 5) (8 4 6))) astar manhattandistance -1)

State2 '((2 1 3) (5 4 X) (7 8 6)) - Harder

1. Extend 8 puzzle to work for any size board (i.e. 15, 24, 35 etc.). How do your search strategies work with the larger board size?
2. Design your own heuristic function. Does it perform better or worse than the two heuristics provided?