ICS 171: Homework #4

A (10). Create a global variable *start-state* whose value represents the initial state

B (20). Create a global variable *tower-ops* to store the name of each operator

C (20). Define Lisp functions for each operator. An operator takes a state as an argument and returns NIL or a new state. It doesn't modify its argument.

D (20). Define a function solution-state? that determines whether a state is the solution state. You want to use the definition of sorted? from Homework 1

E (5). By hand, find some way of combining the operators so that the state is transformed to a goal state. For example, in the jug problem, one solution is:

(fill-three-from-four 
   (fill-four 
    (empty-four-into-three 
     (dump-three 
      (fill-three-from-four 
       (fill-four *start-state*))))))
#S(JUG-CONTENTS :FOUR 2 :THREE 3)
(solution-state? (fill-three-from-four 
                    (fill-four 
                     (empty-four-into-three 
                      (dump-three 
                       (fill-three-from-four 
                        (fill-four *start-state*)
                        ))))))
T

2. (10 points) Solve your Towers of Hanoi problem (above) with breadth first search. You can load the code for breadth first search in the file blind-search.lisp. Make sure you compile blind-search.lisp if you are running on a sun. It might be easier to debug if you start with a simpler problem first, such as moving 1 disk from A to C. Once you can do that without errors, try 2 disks, and then finally 3.

Turn in a single file, which is a listing of your program, and a dribble file showing it working for 1.E (as above) and 2.