The objectives of this assignment are:

1. Depth-First Search (Iterated) and Breadth First Search Algorithms
2. State space representation design
3. Scheme! (writing the operators, modifying search to keep track of the operators at each step, etc).

You are to write two Scheme procedures (you will probably write many procedures that help these two out) that solve water jug problems based on 3 jugs. One procedure will be an Iterated Depth First Search, the other will be a Breadth First Search. Both procedures will have arguments that describe the capacity of each of the jugs, the goal state (how much water in each jug), and a depth limit. Your procedures should return an english description of a sequence of operations from the start state to the goal state (instead of describing the states along the way, you describe the operators used).

Fell free to start with the DFS and BFS code discussed in class (available via the course home page) or any other scheme search code you can find. If you do happen to find scheme code that solves 3-jug water jug problems, please don't use it (and tell Dave it exists!).

One procedure should be named dfswj and will be given three parameters:

• The first parameter is a list of three integers indicating the capacity of the jugs
• The second parameter is a list of three integers indicating the goal state
• The third parameter is a depth limit (an integer indicating the maximum depth you should search, with the start state being depth 0).

Sample: with the jugs can hold 3,4 and 10 gallons. The goal state has 2 gallons in the jug 1 (4 gallon jug), and nothing in the other jugs. Depth limit is 10.

(dfswj '(3 4 10) '(0 2 0) 10)
=> ( "1. Fill jug 0."
     "2. Pour jug 0 into jug 1."
     "3. Fill jug 0."
     "4. Pour jug 0 into jug 1."
     "5. Empty jug 1."
     "6. Pour jug 0 into jug 1." )

It is possible that there is no way to solve the problem, that is, not path from the start state to the goal state. For example, if you had three jugs that each hold 2 gallons, you could not get to the state with 1 gallon in each jug:

(dfswj '(2 2 2) '(1 1 1) 10)
=> ( "No solution found" )

Your DFS search should be an interated DFS (start with a depth limit of 1, if no solution is found start over with a depth limit of 2, etc. Note that this should always find a solution involving the minimum number of steps (if there is a solution within the total depth limit).

You also need to write bfswj. The arguments and result are the same as for dfswj, the only difference is that your procedure should use a breadth-first search and stop when it hits the depth limit.

Generating successor states

Rather than hard-code a successor procedure, think about writing some general procedures that can be applied to each jug independently, to each pair of jugs, etc.

Consider encoding the rules/operators as data that are operated on. The Scheme eval function can be your friend here. You can also write procedures that return procedures!

DFS vs. BFS

As the text suggests, the difference between a depth-first search and a breadth-first search is using a stack vs. a queue for keeping track of a list of states to be explored. You could get/write some procedures to add an item to a list (enqueue vs. push) and remove an item from a list (dequeue, pop) and pass these procedures to a general search procedure. If you pass it the enqueue/dequeue procedures the search is BFS, the stack procedures will make it DFS. You only write one main search function!

Generating the textual return value

In general you need to record (along with each state that is generated), what operator generated the state. Converting these records to text is the easy part, recording them is more work than the actual conversion to text.

You may want to leave this part for last, and start out by getting the searches working with a list of states as the result. The text description of the operations is worth 10 points.

Each procedure (search algorithm) is worth 45% of the project grade, 10% is for code quality (how well can we make sense of the code, how well is it organized, etc.)

If you generate a list of states as the return value of the search procedures, rather than the text desription, you will lose 10 points.

You can get partial credit for any part as long as your provide a description of what the code does do and what is missing/broken.