Project Notes

Suggested Program Interface

I suggest that you separate the code for solving 8-puzzle problems
from the random problem generator. Thus you may want to have 
a program called "search" with the following usage:
 
        search method heuristic board

where the parameters can take on values as follows:

        method = 0 -> BFS
        method = 1 -> DLS
        method = 2 -> A Star 
        ...

        heuristic = 0 -> h(n) = misplaced tiles
        heuristic = 1 -> h(n) = sum of manhattan distances
        heuristic = 2 -> h(n) = 0
        heuristic = 3 -> h(n) = random number between 1 and 10 

The starting state of the board is entered by typing the tile numbers
from left to right, top to bottom. 0 represents the blank. For example

2 4 3
1   6
7 5 8

is entered:

2 4 3 1 0 6 7 5 8

Example:
  to solve the 8-puzzle problem with A* we would type:
                search 2 0 2 4 3 1 0 6 7 5 8

  The first number (2) represents the method A*
  The second number (0) represents the heuristic
  The last 9 numbers represents the board configuration

This interface is only a suggestion and you may use a different
interface if you desire.



Random Problem Generator

The project asks you to generate random problems for your program
to solve. You are supposed to analyze how well your program does
at solving these random problems using the different search
algorithms.

I suggest that you write a separate program for generating 
random problems. It would be for example

   generate

which would return something like
(0 represents the blank)

   1 5 8
   0 2 3
   4 6 7

or

   2 0 7
   8 5 4 
   3 6 1

or

   8 6 2
   1 0 3
   5 4 7

or in vector form they would be

   1,5,8,0,2,3,4,6,7 
   2,0,7,8,5,4,3,6,1   
   8,6,2,1,0,3,5,4,7

using our previous notation. Generate at least ten of 
these problems and then run your search algorithms and 
record the results.

An easy way of generating these problems is just create
a function that spits out the numbers from 0 to 8 in
random order. Please note that not all puzzles generated 
in this fashion will have a solution.

Note that all of the examples in these notes do have a 
solution, so you can use them as test cases. However, 
please be aware that some solutions are extremely long.

For example, one implementation of A* with the sum of the
manhattan distances metric expanded over 30000 nodes to
solve

   2 0 7
   8 5 4
   3 6 1

with a solution path of 27 moves. 


Stephen Bay