CSCE 625 - Homework #2
due: Wed, Sep 21 (hand-in hard-copy in class)

Implement a search algorithm (in any language you like) to solve the
8-puzzle (as described in the textbook).

goal state:
  1 2 3
  4   5
  6 7 8

Start by choosing a representation for states, such as a linear array
of length 9, or a 3x3 array.  Next implement a successor() function,
which generates the set of all legal moves, by sliding an adjacent
tile into the current empty space.  Note that there are 2-4 successors
of every state.

The successor function can be used to generate random problems by
starting with the goal state and "scrambling" it by applying a
sequence of random moves.  In fact, the number of random moves can be
used to control problem difficulty (puzzles generated by 5 random
moves require at most 5 moves to solve them, though sometimes less;
puzzles generated by 50 random scambling moves can take up to 25-30
moves to solve).

Start by writing a simple BFS search algorithm using a queue data
structure.  Test the algorithm on randomly generated puzzles and
calculate statistics on the average length of solution, the maximum
queue size, and the number of goal-tests performed.

Next, a simple modification of the BFS procedure will produce a DFS
search.  Use DFS to try to solve a sample of random problems and
compare the statistics listed above to those for BFS.  How does the
optimal solution length scale up with the number of scambling steps?

You will probably find that the maximum queue size is smaller for DFS
than BFS, but the solutions are much longer.  In fact, there may be some
problems that cannot be solved in a reasonable amount of time (or memory)
by either method.  Next, implement iterative-deepening search.  Do this
by writing a simple depth-limited search, and writing a wrapper around
it to progressively increase the depth limit.  See if you can solve 
even more complex problems (with deeper solutions) than by BFS or DFS.

In this problem, checking for visited states will be crucial, since
many alternative sequences of moves can produce the same state (in
addition, operators are reversible).  You will probably want to use a
hash table of some type to keep track of visited states efficiently.
Also, remember that you have to keep track of path information in
order to print out the final solution (sequence of moves) that solves
the puzzle and measure its length.  The checking for visited states
must be done at the right time; see the GraphSearch alg in the book.

Even with this, there may be some problems that cannot be solved in a
reasonable amount of time or space.  You will probably need to
implement some limits, such as when the queue or number of goal tests
gets too large, at which point the program will be force to fail.  Be
careful not to let a runaway process eat up all the memory on your
computer.

What to turn in:

1) sample output (solutions to a couple random problems; see below)

2) a table showing some statistics on mean #goal-tests and queue-size
and success rate for each of the algorithms, as a function of number
of scrambling steps

3) print-out of source code

### Example output ### (for an implementation in Python)

args to tiles.py are: <search_type> <num_scramble_steps>
where search_type is BFS, DFS, or ID

4 sun> python tiles.py BFS 20
goal:
1 2 3
4 0 5
6 7 8

random initial state:
1 2 3
7 0 6
4 8 5

solution path:
1 2 3
7 0 6
4 8 5

1 2 3
7 6 0
4 8 5

1 2 3
7 6 5
4 8 0

1 2 3
7 6 5
4 0 8

1 2 3
7 0 5
4 6 8

1 2 3
0 7 5
4 6 8

1 2 3
4 7 5
0 6 8

1 2 3
4 7 5
6 0 8

1 2 3
4 0 5
6 7 8

solution depth: 8
num goal tests: 326
max queue size: 203