 # Water Jug Problem

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:

1. (x, y) -> (a, y) if x < a i.e., Fill the first jug if it is not already full
2. (x, y) -> (x, b) if y < b i.e., Fill the second jug if it is not already full
3. (x, y) -> (0, y) if x > 0 i.e., Empty the first jug
4. (x, y) -> (x, 0) if y > 0 i.e, Empty the second jug
5. (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
6. (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:

## 14 thoughts on “Water Jug Problem”

1. Psysho says:

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 ??

• kartik kukreja says:

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.

2. Anonymous says:

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

• kartik kukreja says:

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

3. diya says:

• kartik kukreja says:

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

• fill water into a jug (rules 1 and 2)
• empty any jug (rules 3 and 4)
• pour water from one jug into another (rules 5 and 6)
4. rajath musth says:

5. Yash Bansal says:

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

• kartik kukreja says:

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).

6. Tan says:

Hey there, I’m having problem adapting BFS to A* search on water jug.
Could you give some pointers?

7. Waseem Khalid says:

how to solve this problem by using A* search

• Kartik Kukreja says:

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.

• Waseem Khalid says:

i need code for this please