The Water Jug problem can be stated as follows: “*Given two unmarked jugs having capacities ‘a’ and ‘b’ liters respectively and a target volume ‘t’ liters, find the moves that get exactly ‘t’ liters in any of the two jugs.”*

The problem is solvable only when t is a multiple of gcd(a, b) and can be modeled as search through a state space. The *state space* for this problem can be described as the set of ordered pair of integers (x, y) such that x ∈ {0, 1, 2, …, a} and y ∈ {0, 1, 2, …, b}. The *initial state* is (0, 0) and the *goal states* are (t, y) and (x, t) ∀ x, y.

All we need now for a search procedure to work is a way to generate new states (successors) from a given state. This is captured by *production rules* that specify how and when a new state can be generated from a given state. For the water jug problem, the following production rules are sufficient:

- (x, y) -> (a, y) if x < a i.e., Fill the first jug if it is not already full
- (x, y) -> (x, b) if y < b i.e., Fill the second jug if it is not already full
- (x, y) -> (0, y) if x > 0 i.e., Empty the first jug
- (x, y) -> (x, 0) if y > 0 i.e, Empty the second jug
- (x, y) -> (min(x + y, a), max(0, x + y – a)) if y > 0 i.e., Pour from second jug into first jug until the first jug is full or the second jug is empty
- (x, y) -> (max(0, x + y – b), min(x + y, b)) if x > 0 i.e., Pour from first jug into second jug until the second jug is full or the first jug is empty

Strictly speaking, the conditions in the production rules are not required e.g., we could fill an already full jug except that it won’t lead us anywhere and would be wasteful in a tree search procedure where the visited states are not saved to prevent revisiting.

Now, a search procedure like BFS or DFS can be applied to systematically search from the initial state to one of the goal states through the state space.

Take a look at C++ implementations with BFS and DFS:

**Reference:** Artificial Intelligence by Rich and Knight

28.635308
77.224960

### Like this:

Like Loading...

*Related*

Hey kartik , nice post , would you mind posting original source or link you referred ? , Most importantly how you can to this approach if its originated by you ??

This problem is mentioned in the book “Artificial Intelligence” by Rich & Knight, which I’ve put under the Reference section. They’ve described this problem under “Search Techniques”, discussed the production rules and stated that it can be implemented with both BFS and DFS. I optimized the rules a little to make for an efficient implementation and have written the implementations myself.

Hey kartik…..where are the included files? (i.e. cstdio, queue, etc….)

These are standard C++ headers. Compile (and save as .cpp) the code with a C++ compiler, not a C compiler.

can you tell me about how this rules were made?

The rules have been derived directly from the problem statement. The problem statement allows to:

exact answer…. thank you….

I think that time complexity is ab here. Does there exist a more efficient solution?

Yes, the worst case complexity is O(ab). That can’t be helped because we are using a general purpose uninformed search procedure, whose time complexity is the size of the search space.

There do exist more efficient solutions. This paper: http://www.iaeng.org/publication/WCE2013/WCE2013_pp145-147.pdf describes arithmetic solutions to this problem in O(a+b).

Hey there, I’m having problem adapting BFS to A* search on water jug.

Could you give some pointers?

Are you facing problem while implementing A* search or in coming up with a suitable heuristic for this problem? If it’s the former, then take a look at https://kartikkukreja.wordpress.com/2013/12/28/a-star-search/

and

https://kartikkukreja.wordpress.com/2015/06/07/informed-search-algorithms/

how to solve this problem by using A* search

To apply A* to a problem, we need a good heuristic. If we want an optimal solution, then our heuristic must at least be admissible. You can read more about heuristics here: https://kartikkukreja.wordpress.com/2015/06/14/heuristics-in-ai-search/.

For this problem, we haven’t specified that we need the shortest sequence of moves or otherwise, we wouldn’t have used DFS so even a non-admissible heuristic would work. I could think of this heuristic: sum of absolute differences between actual and desired values in the jugs. It won’t be admissible because it’s different from the path distance (number of moves) but it roughly aligns with our goal so it shouldn’t be too bad.

Please experiment with this to find out how A* performs relative to BFS and DFS.

i need code for this please