Water Jug Problem in AI: State-Space Search With Python Code

The water jug problem is a classic state-space search task: two jugs of known capacity, no measuring marks, and a goal amount to leave in one of them. With capacities a and b, the target is reachable exactly when it does not exceed the larger jug and is a multiple of the greatest common divisor of a and b. A breadth-first search in Python finds the shortest sequence of fills, empties, and pours, which for jugs of three and five units and a target of four units takes six moves.

Formulating the problem

Problem formulation means naming the state, the actions, the goal test, and the cost. Here the state is (x, y), where x is the volume in the first jug and y in the second, with 0 ≤ x ≤ a and 0 ≤ y ≤ b. The start state is (0, 0). The goal test is that x or y equals the target. Each action costs one move.

The six actions are filling the first jug, filling the second, emptying the first, emptying the second, pouring the first into the second until the second is full or the first is empty, and the reverse pour. A pour moves min(x, b - y) units from the first jug to the second. Since every state has at most six successors and the grid has (a + 1)(b + 1) cells, the search space is small and finite.

A solvability test before searching

Every action changes the contents by amounts that are combinations of a and b, so every reachable amount is a multiple of gcd(a, b). Jugs of four and six units can only ever hold even amounts, so a target of five is impossible and a search would only confirm that after exhausting every reachable state. The check also needs the target to fit: no jug can hold more than max(a, b). The converse, that every such multiple can be reached in one of the jugs, follows from Bezout's identity and holds for this puzzle. Python's math.gcd provides the divisor.

Breadth-first search in Python

from collections import deque
from math import gcd

def solve(cap_a, cap_b, target):
    if target > max(cap_a, cap_b) or target % gcd(cap_a, cap_b) != 0:
        return None
    start = (0, 0)
    parent = {start: None}
    queue = deque([start])
    while queue:
        a, b = queue.popleft()
        if a == target or b == target:
            path, state = [], (a, b)
            while state is not None:
                path.append(state)
                state = parent[state]
            return path[::-1]
        pour_ab = min(a, cap_b - b)
        pour_ba = min(b, cap_a - a)
        for nxt in [(cap_a, b), (a, cap_b), (0, b), (a, 0),
                    (a - pour_ab, b + pour_ab), (a + pour_ba, b - pour_ba)]:
            if nxt not in parent:
                parent[nxt] = (a, b)
                queue.append(nxt)
    return None

The dictionary parent doubles as the visited set and as the record used to rebuild the path. A collections.deque is used for the queue because removing from the left end takes about constant time, whereas popping from the front of a list moves every remaining element.

Results from running the code

The function was run on several inputs, and the table shows what it returned.

Because breadth-first search expands states in order of move count, the first goal it finds uses the fewest moves. Depth-first search would also find an answer but could return a longer one.

What the puzzle teaches and where it stops

The same structure appears in larger problems: define states and actions, avoid revisiting states, and pick a search that matches the cost model. Textbook problems like this are called toy problems because they are small enough to analyze fully. Real planning tasks have far larger state spaces, uncertain outcomes, and costs that differ by action, which is why heuristics or learned models enter. Nothing in this puzzle models physical water: jugs have exact capacities, pours are exact, and nothing evaporates or spills.

FAQ

Is the water jug problem solvable for any two capacities?

Only for targets that are multiples of gcd(a, b) and no larger than the bigger jug. Capacities that share no factor other than one can reach every whole amount up to the larger capacity.

Why use breadth-first search instead of depth-first search?

All actions cost one move, so breadth-first search guarantees the fewest moves. Depth-first search uses less memory but may return a longer sequence.

How many states can be reached with jugs of three and five units?

Running the code gives 16 reachable states out of the 24 cells in the grid.

Does this puzzle have practical uses?

It is mainly a teaching example for search and problem formulation. Its pour operation resembles transferring a quantity between capacity-limited containers, but real systems add costs and uncertainty that the puzzle leaves out.

Related reading

• How a robot searches for a path
• Worked examples of problem formulation
• AI and the traveling salesman problem
• Algorithms used on the route-planning problem

More in AI and Society.

Last verified: October 2026

Sources

• collections, Container datatypes (deque), Python Software Foundation documentation, Python 3
• math, Mathematical functions (math.gcd), Python Software Foundation documentation, Python 3
• Output of the code shown, run under Python 3 on October 24, 2026