The Water-Jug Problem

1Two jugs and a volume you cannot mark

You hold a 4-litre jug and a 3-litre jug. Both start empty. You need exactly 2 litres — enough for one flask on the lab bench — and neither jug has a 2-litre mark. The tap gives only a full jug; the sink takes a whole jug. The only way to get a new volume is to pour from one jug into the other until something stops you: the source runs dry, or the destination hits its capacity.

That is a search problem, not a measuring trick. The Search Problems and Breadth-First Search lesson already named the three parts: a state, the legal moves, and a goal test. Here the state is how much water sits in each jug, a move is fill or empty or pour, and the goal test is 'some jug holds 2 litres' — unless the exam names one jug, which is a different test and a later concept.

2A state is the pair of volumes

Write a state as (a, b): a litres in the 4-litre jug, b litres in the 3-litre jug. a is an integer from 0 to 4; b is an integer from 0 to 3. That is twenty possible pairs. The start is (0, 0). Designing the State Space called this the interchangeability test: two histories that leave the same pair are one state, because every remaining fill, empty or pour does the same thing from that pair.

The path that produced the pair — fill the 4-litre first, or fill the 3-litre first — is node bookkeeping. Hash the pair, not the pour sequence. Encode the sequence and the twenty-pair space becomes a tree of repeated situations, which is the warehouse-aisle mistake from that lesson, only smaller.

Figure. Two histories, one pair. Once both runs hold 1 L and 0 L, no remaining fill, empty or pour can tell them apart, so the explored set stores (1, 0) once. Topology of the merge, not a drawing of the jugs.

3Six moves, and pour stops for a reason

From any pair the successor function returns at most six neighbours: fill the 4-litre, fill the 3-litre, empty the 4-litre, empty the 3-litre, pour the 4-litre into the 3-litre, pour the 3-litre into the 4-litre. Fill always produces a full jug. Empty always produces a zero. Pour is the only move that mixes the two numbers, and it stops at the first of two events: the source is empty, or the destination has no room left.

Write the transferred volume as the minimum of what the source holds and what the destination can still take. From (4, 0) a pour into the 3-litre transfers \min(4, 3-0) = 3, and the result is (1, 3). From (1, 3) the same pour transfers \min(1, 3-3) = 0 — a no-op you should still generate, then let the explored set drop it as a duplicate of the current pair.

Figure. Six neighbours: fill or empty either jug, or pour either way. Pour stops at the first of two events — source empty or destination full. From (4, 0) the pour into the 3-litre transfers min(4, 3−0) = 3 and writes (1, 3).

One pour

1. Room leftDestination capacity minus what it already holds — 3 minus b, or 4 minus a.
2. TransferMove the minimum of the source volume and that room. One of those two hits zero.
3. Write the pairSource loses the transfer; destination gains it. No other jug changes.

4Which jug has to hold the 2 L?

A goal test is a predicate on a state, not a vibe. 'Measure 2 litres' with no jug named is true of any pair where a = 2 or b = 2. 'Put 2 litres in the 4-litre jug' is true only of pairs where a = 2. Those are different problems. Breadth-first search will return a shortest path for whichever predicate you hand it; it will not guess which one you meant.

On these capacities the two tests disagree about length. The either-jug test is first true at (4, 2) after four moves. The 4-litre-only test is first true at (2, 3) after six moves. A classmate who implements the stricter test and then compares step-counts with the either-jug write-up has not found a bug in BFS — they have solved a harder goal.

5BFS to (4, 2) in four moves

Hand the either-jug test to breadth-first search, the algorithm from Search Problems and Breadth-First Search. The frontier is a queue of pairs. The first time a dequeued pair has a 2, that path is a shortest one — every edge is one move, so fewest hops is fewest pours.

The walk that BFS returns is: fill the 3-litre, pour it into the 4-litre, fill the 3-litre again, pour into the 4-litre until the 4-litre is full. The leftover in the 3-litre jug is 2 L. The 9-looking pair (4, 2) is not bait here — there is no opponent. It is the goal.

6BFS you can run

The listing is the successor function plus the queue from Search Problems and Breadth-First Search. States are tuples so they can sit in a set. Each frontier entry carries the path of pairs behind it, which is how the returned answer is a sequence of pours and not only the final pair. The goal test in the listing is the either-jug predicate; change one line to require a = 2 and you will watch the path grow from four moves to six.

This is the paper's water-jug experiment — the 'war-jug' typo on the question paper. It is not a new algorithm. It is the uninformed-search loop pointed at a twenty-state space you can print.

Figure. successors returns fill, empty and pour pairs as a set. Each frontier entry is a pair plus the list of pairs behind it — that list is the answer. The goal test is a == 2 or b == 2; change it to a == 2 and the path grows from four moves to six.

What the listing does

1. Six neighbourssuccessors returns the fill, empty and pour pairs as a set, so a no-op pour is one pair, not six.
2. Queue of pathsEach frontier entry is a pair plus the list of pairs behind it — that list is the answer.
3. Either-jug stopa == 2 or b == 2. Change that line to a == 2 and the path grows from four moves to six.

Water-jug BFS, either-jug goal

from collections import deque

def successors(a, b, A=4, B=3):
    t = min(a, B - b)
    u = min(b, A - a)
    return {
        (A, b), (a, B), (0, b), (a, 0),
        (a - t, b + t), (a + u, b - u),
    }

def water_jug(A=4, B=3):
    start = (0, 0)
    frontier = deque([(start, [start])])
    seen = {start}
    while frontier:
        (a, b), path = frontier.popleft()
        if a == 2 or b == 2:
            return path
        for nxt in successors(a, b, A, B):
            if nxt not in seen:
                seen.add(nxt)
                frontier.append((nxt, path + [nxt]))
    return None

Coding lab. BFS to 2 L runs in the app, with checks on your output.