CSW4701 Artificial Intelligence

8 puzzle operators/states

Ok,  now that you've struggled with the code I sent for BFS (and DFS)
let me point out a simple "trick" to make your implementation of the
15-puzzle (or 8-puzzle) OPERATORS a lot easier!

In class, for pedagogical reasons, we specified a node for the 
8-puzzle as a list containing the state, and other information
pertinent to the algorithm employed. For the 8-puzzle, we defined
a state as  a list of three lists, each sublist encoding the
configuration of one row of the puzzle. Thus,

( (1 2 3) (8 nil 4) (7 6 5) )  would encode the goal state for
example for the case where we tile the puzzle concentrically. 

Well, the operators that I suggested (along with a comment that it
was pretty "ugly") SEARCHED for the blank (nil) in one of those
lists, and then acted accordingly to swap the blank with a neigbhor.

This means that each time you apply an operator to some state, you
have to search a list linearly...NOW THAT'S PRETTY UGLY.
How might you speed this up?

Ok, here it is:  encode the location of the blank as part of the
representation of the state.  Thus, in the example above for the
goal node of the 8-puzzle, include a FOURTH sublist which has 
TWO VALUES, the sublist in which the blank appears and the column
position in which it appears.  Eg,
( (1 2 3) (8 nil 4) (7 6 5) (2 2) ) states the specific board
configuration, as well as the fact that the blank (nil) appears
in the second sublist in position 2!

Why does this help?  Well, now you can easily test whether an
operator applies by testing the values of the last sublist. 
(For example, move EAST is not applicable if the (second (fourth
state)) equals 3.)
AND, you can implement the operator's swap very easily using
the LISP built-in function NTH!  Check it out!

[WARNING:  ***************DON'T FORGET TO CODE THE OPERATOR SO IT
                          CORRECTLY UPDATES THE POSITION OF THE BLANK******]

This means you've sped up the successor generator function quite
nicely!  Good work!!

Oh yes, another point to make (to save some time in copying and
some memory space/management time), you may need ONLY TO COPY A
SUBLIST when you generate a new node, not needing to copy the
entire state descriptor! Think about that one. If you are swapping
the blank in the second sublist ONLY, then why bother copying the
first and third sublists? THE MAIN POINT: ONLY COPY WHAT YOU HAVE
TO COPY NOT TO PROVIDE UNWANTED NASTY AND UGLY SIDE EFFECTS.

Different LISP's have different "copy" functions. Check out CL's
copy-tree function, or if you prefer, here is your own copy
function if your lisp doesn't have a convenient one ( or you 
cannot find it!):

(defun copy (obj)
 (cond ( (null obj) nil)
       ( (listp obj)  (cons  (copy (first obj)) (copy (rest obj))))
       ( t obj) ) )

Yep it was really THAT easy....

sal