Project #1
CSCE 625 (AI)
due Mon, Sep 17, 2012 (in class)

The goal of this project is to implement and test DFS, BFS, and iterative
deepening on the 8-puzzle (or the 15- or 24- puzzle, if you prefer).

Here is an example of the goal state.  

 1   2   3 
 4   .   5 
 6   7   8 

The rules are that you can move any tile up, down, left, or right into
the whereever the empty tile is.  Here are successors of the goal state:

 1   .   3     1   2   3     1   2   3     1   2   3 
 4   2   5     4   5   .     4   7   5     .   4   5 
 6   7   8     6   7   8     6   .   8     6   7   8 

You should implement the following 5 algorithms:
 BFS (simple breadth-first search; without checking for visited states)
 BFSv (BFS with tracking visited states) 
 DFSv (depth-first search with checking for visited states) 
 DLS (depth-limited DFS search)
 ID (iterative deepening)

You may use any programming language you like.  However, you MUST 
implement the algorithms in the way described (i.e. as a while loop
that uses a frontier).

You will probably want to implement a class for "State" that will store
the positions of the tiles (e.g. in a 3x3 array).  You will probably 
also want to implement methods for: printing out the puzzle state,
generating successors, scrambling the puzzle by X random moves, and testing
it to see if it matches the goal.  

If you start with a scrambled puzzle and find the goal, you will want
to print out the "solution path", which is the sequence of states from
the initial state to the goal showing each of the moves.  To do this,
each state will have to keep a pointer to its parent, which is the
state is was created as the successor of.  Also, it will be useful to
keep track of the depth of each node (for DLS).

In solving this puzzle, it turns out to be important to keep track of
visited states.  It is very easy to generate the same state by multiple
paths (multiple sequences of moves).  If you are not careful, this
will dramatically increase the size of your queue and limit the depth
to which you can effectively search.  You should implement a "visited
list" for keeping track of states which have previously been goal
tested, so you can avoid putting them in the queue and searching them
redundantly.

BFS is the easiest to implement and test, so do it first. Then extend
BFS with a mechanism for tracking of visited states.  Note that there
are many wasy to do this (using a simple list which takes long to
search, or a hash table if you are clever).  For the purposes of this
assignment, it does not matter whether this is done in an efficient
way, and we won't count the size of the visited list.

Once you have done this, it is easy to write a similar function for 
DFS and then DLS.  Finally, the routine for iterative deepening is
just a wrapper around DLS.

Your code should keep track of at least 2 key metrics: total number of
nodes that are goal-tested, and maximum queue size.  You should make
up a short table of statistics for these 2 metrics, to compare each
of the algorithms.  Run the program 10 times for each, and report
the average.  For some problems, the program might not halt in
reasonable time, so you can just stop it (manually, or using a limit
on time or max number of goal tests) and report the number of
such "failures".

One final note: you should create the scrambled puzzles to solve
by randomly applying the operator (choosing a random child node)
some number of times.  This is a convenient way to generate puzzles
because a) you are gauranteed there is a solution, and b) the
complexity or difficulty of the puzzle can be controlled by the
number of scrambling steps.  (in fact, it might be interesting
to see the difference between mean number of goal tests and 
mean depth of solution (path length from root to goal) for 
5, 10, 20, and 50 scrambling steps.

Here is one thing to note: which of your algorithms finds the shortest
solution?  Can you show on a particular instance that BFS produces a
shorter solution path than DFS?  You do not need to put this in your
report; it is just somehting interesting to observe.

What to turn in:
----------------

1) Your source code.
2) A short printout of an example run.
3) A table of statistics (mean number of goal tests and max queue size
for each algorithm, averaged over 10 trials)
4) A hardcopy of your source code.
(no written report is necessary)
5) You will have to schedule time to visit the TA to demo your program,
as part of your grade.

Example transcript
------------------
(3x3 puzzle, scrambled 10 times, searched with BFS)
init
 1   2   3 
 6   4   5 
 7   8   . 
iter=0, queue=1, depth=0
iter=1, queue=2, depth=1
iter=2, queue=4, depth=1
iter=3, queue=6, depth=2
iter=4, queue=7, depth=2
iter=5, queue=8, depth=2
iter=6, queue=11, depth=2
iter=7, queue=14, depth=2
iter=8, queue=15, depth=2
iter=9, queue=16, depth=3
iter=10, queue=18, depth=3
iter=11, queue=20, depth=3
iter=12, queue=22, depth=3
iter=13, queue=24, depth=3
iter=14, queue=26, depth=3
iter=15, queue=28, depth=3
...
iter=51, queue=92, depth=4
iter=52, queue=93, depth=4
iter=53, queue=96, depth=4
iter=54, queue=97, depth=4
iter=55, queue=98, depth=4
iter=56, queue=99, depth=4
iter=57, queue=100, depth=4
iter=58, queue=103, depth=4
iter=59, queue=104, depth=4
iter=60, queue=105, depth=4
iter=61, queue=108, depth=4
iter=62, queue=109, depth=4
iter=63, queue=110, depth=4
success! depth=4, total_goal_tests=64, max_queue_size=110
 1   2   3 
 6   4   5 
 7   8   . 

 1   2   3 
 6   4   5 
 7   .   8 

 1   2   3 
 6   4   5 
 .   7   8 

 1   2   3 
 .   4   5 
 6   7   8 

 1   2   3 
 4   .   5 
 6   7   8