# ICS 171: Homework #4

1. IMPORTANT Implement lisp functions to define the search space of the Towers of Hanoi problem of Homework #2

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.

Back to http://www.ics.uci.edu/~pazzani/171-p.html (text only) or http://www.ics.uci.edu/~pazzani/171.html .

Michael Pazzani
Department of Information and Computer Science,
University of California, Irvine
Irvine, CA 92717-3425
pazzani@ics.uci.edu