Water Jug Problem

The Water Jug Problem looks like a riddle, but it is really a graph search in disguise. The trick that unlocks a whole class of interview questions: when a puzzle has states and moves between them, the states are nodes, the moves are edges, and BFS finds the answer.

The slow way first

You could try to reason out a clever sequence of pours by hand. That works for one puzzle but does not generalize, and it is easy to miss the path or loop forever repeating the same pours. We want a method that is guaranteed to find an answer if one exists.

The question to ask: what does a "situation" in this puzzle look like, and how do situations connect? A situation is fully described by how much water each jug holds — the pair (a, b). Every legal move turns one pair into another. That is exactly a graph, so we can search it.

The idea: states are nodes, moves are edges

Treat each pair (a, b) as a node. From a node, the six possible moves (fill jug1, fill jug2, empty jug1, empty jug2, pour 1→2, pour 2→1) lead to neighbor nodes. Start at (0, 0) and BFS outward: expand the oldest state in the queue, generate its neighbors, and enqueue any you have not seen. Stop the moment you dequeue a state where some jug holds the target.

A seen set is what keeps this finite: without it we would pour back and forth forever. Because BFS explores by distance, the first time we reach a goal state we have also found it in the fewest moves.

Walk through it

Step through the animation. We start at (0, 0) and expand level by level. Each step dequeues one state, lights up the new neighbor it discovers, and bumps the step count. The queue label shows what is waiting. After a handful of expansions we dequeue (3, 4) — the 5-jug holds 4 — and return True.

Pseudocode

start = (0, 0)
seen = {start};  queue = [start]
while queue is not empty:
    (a, b) = pop the front of queue
    if a == target or b == target or a + b == target:
        return True
    for each next state reachable by a fill / empty / pour:
        if next state not in seen:
            add it to seen and push it onto queue
return False        # exhausted every reachable state, never hit target

The Python solution

from collections import deque
 
def can_measure(jug1, jug2, target):
    start = (0, 0)
    seen = {start}
    queue = deque([start])
    while queue:
        a, b = queue.popleft()
        if a == target or b == target or a + b == target:
            return True
        for nxt in moves(a, b, jug1, jug2):
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return False

• start = (0, 0) — both jugs empty is the BFS source.
• seen is a set of visited states; it stops us from re-exploring and looping forever.
• queue.popleft() takes the oldest state — that FIFO order is what makes this breadth-first.
• Line 9 is the goal test: success if either jug, or the two combined, equals the target.
• moves(...) yields every state reachable by one fill, empty, or pour. We enqueue only the unseen ones.
• If the queue drains without a hit, every reachable state has been tried, so we return False.

Complexity

There are at most (jug1 + 1) × (jug2 + 1) possible states, and the seen set visits each once, so the whole search is bounded by the product of the capacities — small and fast.

When this pattern shows up

Practice