CS 2360
Fall 1995
Homework Assignment 5
Due no later than 8:00am, Monday, November 6, 1995

The eight-tile puzzle is a square tray in which are placed 8 square 
tiles.  The remaining ninth square is uncovered.  Each tile has a number 
on it.  A tile that is adjacent to the blank space can be slid into that 
space.  A game consists of a starting position and a specified goal 
position.  The goal is to transform the starting position into the goal 
position by sliding the tiles around.

Your assignment is to write a program called EIGHT-PUZZLE which employs 
a depth-first state space search to solve an eight-tile puzzle with any 
initial state.  EIGHT-PUZZLE takes three arguments.  The first is the 
initial state of the puzzle, represented as a list of three lists.  For 
example, the list '((2 8 3)(1 6 4)(7 _ 5)) represents the eight-tile 
puzzle when it looks like this:

                              2 8 3
                              1 6 4
                              7   5

The second argument is any goal state for the puzzle, also represented 
as a list of three lists.  Thus, the list '((1 2 3)(8 _ 4)(7 6 5)) would 
represent the goal state that looks like this:

                              1 2 3
                              8   4
                              7 6 5

The third argument is either nil or non-nil.  If the value is non-nil, 
your program should print to the terminal a trace of the sequence of 
states or moves being tried as the search progresses.  The trace should 
also point out where the program runs into a dead end and has to 
backtrack, as well as pointing out when the goal has been reached.  If 
the third argument is nil, no trace should be printed.  (You'll want to 
look up some of the print I/O stuff in the book by Steele to make this 
pretty.)

When the goal has been reached, EIGHT-PUZZLE should terminate and return 
a list of successive states that constitutes the path from the initial 
state to the goal state.  So, if Lyman or Alex invokes EIGHT-PUZZLE in 
this way:

? (eight-puzzle '((2 8 3)(1 6 4)(7 _ 5)) '((1 2 3)(8 _ 4)(7 6 5)) nil)

your program should return something like:

(((2 8 3)(1 6 4)(7 _ 5))((2 8 3)(1 _ 4)(7 6 5))((2 _ 3)(1 8 4)(7 6 5))
 ((_ 2 3)(1 8 4)(7 6 5))((1 2 3)(_ 8 4)(7 6 5))((1 2 3)(8 _ 4)(7 6 5)))

Your program may find a different path because your program may apply 
its operators in a different order than my hypothetical program does.

If the goal state can't be reached from the initial state, EIGHT-PUZZLE 
should just return nil. 

If you wish, you can convert my representation for the eight-tile puzzle 
into any other representation of your choice if you think that would 
make your life easier.  However, you still have to deal with my 
representation as input to your function as specified above.  
Furthermore, you'll need to convert your representation to my 
representation in order to return the path from the initial state to the 
goal state in the correct (i.e., my) format, and you'll have to do the 
same conversion in order to get the trace information to be displayed in 
the format that we expect.  If you want my advice, you'll just deal with 
the representation as it is given, but ultimately that's up to you.

Same guidelines as in the past:  lots of well-abstracted, well-named, 
cohesive, and readable functions, but no global variables, no 
assignment, and no iteration.  Good luck.
-- 


Kurt Eiselt
Assistant Dean, Student Services
College of Computing
Georgia Institute of Technology
Atlanta, GA 30332-0280

http://www.cc.gatech.edu/aimosaic/faculty/eiselt.html