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