Assignment 2
Due Thu 2/16 on or before 11:59:59 pm
Write a LISP program for best-first search on the 8-puzzle problem using the textbook's best-first implementation unmodified. The textbook's sample problem is the farmer-wolf-goat-cabbage problem. You will have to define operators on a state that return a new legal state (or nil if not legal) similar to farmer-takes-self, farmer-takes-wolf, etc. The 8-puzzle's legal moves will be moving the blank up, down, right, or left. Represent the 8-puzzle state as a list. For example, the goal state is (with 0 representing the blank):
(1 2 3 8 0 4 7 6 5)
Also define a "better" heuristic that computes the Manhattan distance that each tile is out of place.
Include a test run of your program with start state (2 8 3 1 6 4 7 0 5) just as shown in your textbook that takes 6 moves and also with this longer 18 move problem from start state (3 5 2 0 1 6 7 8 4). For fun you can also test your program with this very long 23 move problem from start state (3 5 2 7 0 1 8 4 6). Don't turn in a test run of this one as the trace output is much too long.
Hints
You may find these built-in Lisp functions helpful:
position
returns the index of an element in a list (the first position is 0).
You can use position to find the index of 0 in a state to find out where the
blank is.
mod and floor
return the modulo and floor respectively. The position of the blank
modulo 3 will give you its column (leftmost column is 0 and rightmost
is 2). Likewise the floor of the position divided by 3 gives you the row.
If you compute the position and store it in a local variable with a
let and want to add local variables for the row and
column to the same let, you should use let* instead
because let binds all of the variables in parallel whereas let* binds
each variable in sequence, so you can use the position to calculate
the row and then the column. If the blank is on the top row (row 0),
then you cannot legally move it up and likewise you cannot move it
down if it is on the bottom row (row 2). Similar rules apply for the
column and moving right or left.
You can use the setf function with accessor
nth to modify a state. As setf modifies the
original list, be sure to make a copy using copy-list first
and then call setf on the copy, not the original.
My solution takes 40 lines of code, not counting blank lines, comment lines or the definitions of *start* or *goal*. If your solution is taking much longer, you are probably doing something wrong and should come see me or our TA for help.
Submitting
Submit by zipping together your source code file (e.g., a2.lisp) and your typescript file (e.g., typescript.txt) into a2.zip and then upload a2.zip to Assignment 2 on Laulima. You do not need to include the textbook's best-first search code.
David N. Chin / Chin@Hawaii.Edu