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:

Reference: Artificial Intelligence by Rich and Knight

14 thoughts on “Water Jug Problem

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s