This may be done instead of the last part of Assignment 1:

The water jug problem is defined as follows:

Assume that you have two jugs, Jug-A and Jug-B each of which holds a certain number of gallons. Initially, both gallons are full, but we have an infinite supply of water. Our task is to measure exactly X gallons.

As an example: Jug-A holds 4 gallons, and Jug-B holds 3 gallons. We wish to obtain exactly 1 gallon.

We can look at a state as a pair of numbers, where the first represents the number of gallons of water currently in Jug-A and the second represents the number of gallons in Jug-B.

Possible legal operators are: filling Jug-A, filling Jug-B, emptying Jug-A onto the ground, emptying Jug-B onto the ground, pouring Jug-A into Jug-B (until either Jug-A is empty or Jug-B is full), or pouring Jug-B into Jug-A (until either Jug-B is empty or Jug-A is full).

Formulate this in writing as a search problem. Specify what the initial state looks like, what the goal state looks like, and how the operators change the states.

Implement this search problem using depth first search and breadth first search.

Your program should accept three integer values as parameters (the size of each jug and the gallons we need for the goal). It should also accept a parameter telling it which type of search to perform.

Your program should output the path to the goal as a sequence of states. It should also output the number of states that it visited, (i.e. placed on the stack or queue), the number of states that it expanded, and the average branching factor of all states that it expanded (average number of children that a node had). (Think about checking for repeated states or placing a maximum depth on paths for dfs.)

I prefer your code to be in C/C++ so that (if I wish) I can run the executable on a UNIX or Linux machine (or Windows, for those of you who are used to VC++). However, any other language/platform is acceptable as long as you check with me in advance. Hand in a copy of your source code as well as both dfs and bfs output runs on a few problems, including the one above as well as a 9 gallon jug and 4 gallon jug where you wish to have 6 gallons. For this second problem, if you find that one (or both) of these two uninformed search methods takes too long because it explores too many search nodes, you may stop the program and output how many nodes were explored. This could occur if you do not check for repeated states.)

There is source code publicly available on the web for the different searching algorithms. If you wish, you can use some of it, and change it to be appropriate for this problem. Your book website contains links for Python, Java, and Lisp. For C++ you can follow this link: http://www-users.cs.umn.edu/~gini/aiprog/c++search/ which has a c++ search library created by Peter Bouthoorn.