Solving the 8 puzzle

Due: Dec 16th 11:59

Objective: Implement the 8 puzzle game and use the game as the basis to examine and analyze some of the 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 on space to its left.

 

For conformity represent your board as follows in your program.

((1 2 3)

(4 5 6)

(7 8 9)) 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. You can assume certain functions will be written such as goal? and expandState which are true of all puzzles that need to be solved via search.

1) Implement a generic version of breadth first search. The primary function (call it bfs) should take the initial state as an argument and reutrn 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 reutrn the steps needed to solve the problem.

3) Implement a generic version of best first search. The primary function (call it best-first-search) should take the initial state and the evaluation function as arguments and reutrn the steps needed to solve the problem.

 

Heuristic Evaluation Function:

Code the the following heurstic 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.

 

  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 '((2 8 7) (6 5 4) (X 1 3)) - Hard

 

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.
  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