The Water Jug Problem: Production Rules and the Smallest State Space

Two unmarked jugs, no measuring marks, and a target volume. The six production rules, the complete 20-state graph drawn out, the number-theory result that says when it's solvable, and BFS code.

You have a 4-gallon jug and a 3-gallon jug. Neither has any measuring marks. A tap gives unlimited water and you can pour water away freely.

Measure out exactly 2 gallons.

This is the smallest problem on these pages — 20 states in total — which makes it the best one for actually seeing how state-space search works. You can draw the entire graph, trace every path, and check the algorithm’s answer by hand.

It also hides a genuinely deep result: whether a water-jug problem is solvable at all is decided by a piece of number theory from Euclid.

The problem

That “you can only tell full or empty” constraint is the crux. Without it you’d just eyeball 2 gallons. All the intelligence in this problem comes from using one jug as a ruler for the other.

State representation

A state is simply how much water is in each jug:

$\text{state} = (x, y)$

$x$ — gallons in the 4-gallon jug, $0 \le x \le 4$
$y$ — gallons in the 3-gallon jug, $0 \le y \le 3$

start = (0, 0)                        # both jugs empty
goal  = lambda s: s[0] == 2           # 2 gallons in the big jug

State-space size: $5 \times 4 = 20$ . Every one of them is reachable — unlike missionaries and cannibals, there are no illegal states here. That makes this the cleanest possible demonstration of search.

Note the goal is a predicate, not a specific state. We don’t care what’s in the small jug when we’re done. (2, 0) and (2, 3) both count. Writing state == (2, 0) instead of a predicate is the most common bug here — it makes the search take longer and sometimes miss the shortest answer.

The six production rules

This problem is where the term production rule entered AI — an IF condition THEN action pair. Six of them cover everything you can do:

#	Rule	Condition	Result
R1	Fill the 4-gallon jug	$x < 4$	$(4, y)$
R2	Fill the 3-gallon jug	$y < 3$	$(x, 3)$
R3	Empty the 4-gallon jug	$x > 0$	$(0, y)$
R4	Empty the 3-gallon jug	$y > 0$	$(x, 0)$
R5	Pour 4 → 3 until 3 is full or 4 is empty	$x > 0, y < 3$	$(x - d,\; y + d)$ where $d = \min(x,\, 3 - y)$
R6	Pour 3 → 4 until 4 is full or 3 is empty	$y > 0, x < 4$	$(x + d,\; y - d)$ where $d = \min(y,\, 4 - x)$

R5 and R6 are the interesting ones. The pour amount is a min — you stop either when the source runs dry or when the destination fills, whichever comes first. Getting that expression wrong (using just the source amount, say) produces jugs holding negative or overflowing volumes, and the bug is easy to miss because the search still runs.

CAP = (4, 3)

def successors(state):
    x, y = state
    X, Y = CAP
    out = []
    if x < X: out.append(((X, y), 'fill 4-gal'))
    if y < Y: out.append(((x, Y), 'fill 3-gal'))
    if x > 0: out.append(((0, y), 'empty 4-gal'))
    if y > 0: out.append(((x, 0), 'empty 3-gal'))
    if x > 0 and y < Y:
        d = min(x, Y - y)
        out.append(((x - d, y + d), f'pour 4→3 ({d})'))
    if y > 0 and x < X:
        d = min(y, X - x)
        out.append(((x + d, y - d), f'pour 3→4 ({d})'))
    return out

The complete state graph

Twenty states. Here they all are, with every legal transition.

Two things pop out of the picture:

The goal isn’t one point. Both (2, 0) and (2, 3) — the whole column $x = 2$ — satisfy “2 gallons in the big jug”.
Fill and empty moves are the long straight edges; pours are the short diagonals. Every path to $x = 2$ has to use at least one diagonal, because fills and empties alone can only ever produce 0, 3 or 4.

Two solutions, traced

Solution A — 4 moves (the shortest)

#	Rule	State	What just happened
—	start	(0, 0)	Both empty
1	R2 — fill 3-gal	(0, 3)
2	R6 — pour 3 → 4	(3, 0)	Big jug now holds 3
3	R2 — fill 3-gal	(3, 3)
4	R6 — pour 3 → 4	(4, 2)	Only 1 gallon fits — 2 left behind ✅

The final move is the trick. The 4-gallon jug already had 3 in it, so it can accept only 1 more. Pouring from a full 3-gallon jug leaves exactly $3 - 1 = 2$ gallons in the small jug.

Wait — that puts 2 gallons in the 3-gallon jug, not the 4. If your goal is specifically “2 in the big jug”, add one more move (empty 4-gal, pour 3 → 4), or use solution B.

Solution B — 6 moves, 2 gallons in the big jug

#	Rule	State	What just happened
—	start	(0, 0)
1	R1 — fill 4-gal	(4, 0)
2	R5 — pour 4 → 3	(1, 3)	3 fits in the small jug; 1 stays behind
3	R4 — empty 3-gal	(1, 0)	The 1 gallon survives
4	R5 — pour 4 → 3	(0, 1)	Move the 1 across
5	R1 — fill 4-gal	(4, 1)
6	R5 — pour 4 → 3	(2, 3)	Small jug takes only 2 — 2 stays behind ✅

When is it solvable? The number theory

This is the part that lifts the water-jug problem above puzzle status.

Theorem. With jugs of capacity $a$ and $b$ , you can measure exactly $d$ gallons if and only if:

$d \le \max(a, b) \quad\text{and}\quad \gcd(a, b) \mid d$

Every operation you can perform adds or removes a whole $a$ or a whole $b$ , so every reachable amount has the form

$d = m \cdot a + n \cdot b$

for integers $m, n$ (possibly negative — that’s an empty). By Bézout’s identity, the set of integers expressible that way is exactly the multiples of $\gcd(a, b)$ .

Check our problem: $\gcd(4, 3) = 1$ , and $1$ divides everything. So with a 4-gallon and a 3-gallon jug you can measure any whole number of gallons from 0 to 4. No search required to know that.

Jugs	gcd	Measurable amounts
4, 3	1	0, 1, 2, 3, 4 — anything
5, 3	1	anything up to 5
4, 6	2	only 0, 2, 4, 6 — odd amounts are impossible
8, 6	2	only even amounts
9, 6	3	only 0, 3, 6, 9
7, 5	1	anything up to 7

Try measuring 3 gallons with a 4-gallon and a 6-gallon jug. Your BFS will explore every reachable state and return None. The number theory tells you that in one line: $\gcd(4, 6) = 2$ , and $2 \nmid 3$ .

from math import gcd

def is_solvable(a, b, d):
    return d <= max(a, b) and d % gcd(a, b) == 0

This is the ideal relationship between analysis and search. When you can characterise solvability mathematically, do that first — it’s instant, and it tells you whether the search is worth running. Search then finds you the actual sequence of moves, which the theorem doesn’t give you.

Full working code

from collections import deque
from math import gcd


def water_jug(cap_a, cap_b, target):
    """Shortest sequence of pours reaching `target` in either jug."""
    if target > max(cap_a, cap_b) or target % gcd(cap_a, cap_b) != 0:
        return None                                  # provably impossible

    start = (0, 0)
    frontier = deque([(start, [])])
    seen = {start}

    while frontier:
        (a, b), path = frontier.popleft()

        if a == target or b == target:
            return path

        moves = [
            ((cap_a, b), f'fill  {cap_a}-gal'),
            ((a, cap_b), f'fill  {cap_b}-gal'),
            ((0, b),     f'empty {cap_a}-gal'),
            ((a, 0),     f'empty {cap_b}-gal'),
        ]
        # pour A → B
        d = min(a, cap_b - b)
        if d: moves.append(((a - d, b + d), f'pour  {cap_a}→{cap_b} ({d})'))
        # pour B → A
        d = min(b, cap_a - a)
        if d: moves.append(((a + d, b - d), f'pour  {cap_b}→{cap_a} ({d})'))

        for nxt, action in moves:
            if nxt not in seen:
                seen.add(nxt)
                frontier.append((nxt, path + [(action, nxt)]))
    return None


if __name__ == '__main__':
    for a, b, t in [(4, 3, 2), (5, 3, 4), (4, 6, 3), (7, 5, 1)]:
        plan = water_jug(a, b, t)
        print(f'\n{a}-gal & {b}-gal jugs, measure {t}:')
        if plan is None:
            print(f'  impossible — gcd({a},{b}) = {gcd(a, b)} does not divide {t}')
        else:
            print(f'  ({0},{0})  start')
            for action, state in plan:
                print(f'  {str(state):<8} {action}')
            print(f'  solved in {len(plan)} moves')

Output:

4-gal & 3-gal jugs, measure 2:
  (0,0)  start
  (0, 3)   fill  3-gal
  (3, 0)   pour  3→4 (3)
  (3, 3)   fill  3-gal
  (4, 2)   pour  3→4 (1)
  solved in 4 moves

5-gal & 3-gal jugs, measure 4:
  (0,0)  start
  (5, 0)   fill  5-gal
  (2, 3)   pour  5→3 (3)
  (2, 0)   empty 3-gal
  (0, 2)   pour  5→3 (2)
  (5, 2)   fill  5-gal
  (4, 3)   pour  5→3 (1)
  solved in 6 moves

4-gal & 6-gal jugs, measure 3:
  impossible — gcd(4,6) = 2 does not divide 3

Variants worth knowing

Three jugs. The classic version: an 8-litre jug full of water, plus empty 5-litre and 3-litre jugs, split the water into two equal 4-litre portions. No tap and no drain — the total is conserved at 8. The state space is the set of $(a, b, c)$ with $a + b + c = 8$ , which is 24 states, and the answer takes 7 moves. The conservation constraint changes the character completely: there are no fill or empty rules, only pours.

Die Hard 3. The film’s puzzle is a 5-gallon and 3-gallon jug measuring exactly 4 gallons. $\gcd(5,3) = 1$ so it’s solvable; BFS finds it in 6 moves.

Minimising water used rather than moves. Now the edges have different costs (a fill costs its volume, a pour costs nothing) and you need uniform-cost search instead of BFS. Same graph, different frontier ordering — exactly the substitution described in the overview.

Why this problem matters

Water jug is the standard first example when teaching production systems — architectures where knowledge is a set of IF ... THEN ... rules and a control loop repeatedly picks a rule whose condition matches. That architecture ran the expert systems of the 1980s (MYCIN, XCON) and survives today in business rules engines, Drools, and every “if this then that” automation platform.

The transferable ideas:

Six rules describe a 20-state space. A small, complete rule set generates a much larger behaviour space. That ratio is what makes rule-based systems worth building.
The goal is a predicate over states, not a state. Real goals almost always are — “the account balance is zero”, not “the system is in exactly this configuration”.
Analysis first, search second. One gcd call answers a question that search takes thousands of nodes to answer, and answers it for all targets at once.

And the practical shape shows up in resource allocation everywhere: memory allocators combining fixed-size blocks, currency systems making change with fixed denominations, and dosage calculations combining fixed-volume containers are all “which integer combinations of $a$ and $b$ can I reach” — the same Bézout question in different clothes.

Where to go next

Problem Solving with AI: The State-Space Framework — the shared vocabulary
Missionaries and Cannibals — the other small-space classic, with constraints
Vacuum Cleaner World — the smallest state space of all
BFS Shortest Path — the algorithm used here