Solving the 8 puzzle

Due: Dec 15th 11:59

Objective: Implement the 8 puzzle and use the game as the basis to examine and analyze a set of fundamental search algorithms.

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
where 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. Thus the following a valid operation 
1 2 3    1 2 3
4 X 5 => 4 5 X
6 8 7    6 8 7
where the 5 has moved one space to its left.

For uniformity represent the board as follows in your program. 

((1 2 3)
 (4 5 6)
 (7 8 X))
where each sublist is a row of the board and 'X represents the blank space.

Write a function search that accepts an initial board configuration and a search function (see below) and returns a list of the moves (in the form '(move tile direction)) necessary to go from the initial state to the final state.

For example: 

search '((1 2 3) (X 5 6) (4 7 8)) bfs)
would return 
((move 4 up)
 (move 7 left)
 (move 8 left)
Note: Use "right" and "down" for other possible moves.

Searching:

Each of these search functions should be written independently of the puzzle. That is -- the only functions that should assume domain knowledge are functions such goal? and expandState which require new implementations for new domains.

1) Implement a generic version of breadth first search. The primary function (call it bfs) should take the initial state as an argument and return the steps needed to solve the problem.

2) Implement a generic version of depth first search with iterative deepening. Start with a depth of 2 and grow in increments of 1. The primary function (call it dfs) should take the initial state as an argument and return the steps needed to solve the problem.

3) Implement a generic version of A*. The primary function (call it a-star) should take the initial state and the evaluation function as arguments and return the steps needed to solve the problem. This setup will require that the second parameter to the generic search function be 

 (lambda (x) 
   (best-first-search x evalFunc))
 Heuristic Evaluation Function:

Code the following heuristic evaluation functions. Each function takes a state as an argument and returns a number greater than or equal to zero. In both of these cases the best state is the one with the smallest value (in fact the goal state has a value of 0), other heuristic functions might instead be based on the maximal cost. (note: name both evaluation functions as specified below)

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

    2. 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: ((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.
Statistics Gathering:

Write the search functions such that they will gather basic statistical data on their performances. Two measures that are useful to examine are the "total time of the search" and the number of states examined during the search.

Testing:

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.

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

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

 Problems that are not solved in reasonable amounts of time (< 10 minutes) should be noted but need not be run to completion.

Challenge Problems:

  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. Be sure to realize that difficult states will be impossible to solve for larger board sizes (i.e >9)
  2. Design your own heuristic function. Does it perform better or worse than the two heuristics provided?
You should turn in a file called 8puzzle.ss