Measure Four Litres With Two Jugs: From Every Sequence of Moves to a Graph of States

Trying every sequence of pours explodes with its length; treating each pair of jug levels as a vertex turns the puzzle into a short search.

A puzzle of moves becomes a graph search once each arrangement of the puzzle is a vertex and each move is an edge, and breadth-first search then finds the fewest moves while visiting each arrangement once. A camper has a 3-litre jug and a 5-litre jug, both empty, and a tap. A move fills a jug, empties a jug, or pours one jug into the other until the first is empty or the second is full. The question is the fewest moves that leave exactly 4 litres in either jug.

The brute force tries every sequence of moves, length 1, then 2, and so on, until one ends with 4 litres. Each step offers six moves, so there are 6 to the power of the length of sequences of each length: 46,656 of length 6, and only one of them ends on 4 litres. The repeated work is that very different sequences reach the same two levels, and each carries on from there as though it were new: filling the small jug and emptying it again lands back where it started.

The fix is to search the levels instead of the sequences. A state is everything the next move depends on, here the two levels written as (small, large), so (0, 5) means the small jug empty and the large one full. Each state is a vertex, each move an edge to the state it produces, and the graph is never built in advance: a state's neighbours are worked out when the search reaches it.

Every sequence of moves against a search over states

Every sequence6 to the power of the length

Try every sequence of moves of each length in turn. Sequences that reach the same levels are all carried on separately.

Search over statesAt most 24 states

Breadth-first search over the pairs of levels, marking each the first time it is reached. Each pair is explored once, by a shortest route.

The listing runs both. Of the 4 × 6 = 24 pairs of levels, only 16 can be reached from two empty jugs at all, and the search finds 4 litres at depth 6.

jugs.pypy

from collections import deque
from itertools import product

SMALL, LARGE, GOAL = 3, 5, 4
State = tuple[int, int]


def moves(state: State) -> list[tuple[str, State]]:
    a, b = state
    pour_into_large = min(a, LARGE - b)
    pour_into_small = min(b, SMALL - a)
    return [
        ("fill 3", (SMALL, b)),
        ("fill 5", (a, LARGE)),
        ("empty 3", (0, b)),
        ("empty 5", (a, 0)),
        ("pour 3 into 5", (a - pour_into_large, b + pour_into_large)),
        ("pour 5 into 3", (a + pour_into_small, b - pour_into_small)),
    ]


def every_sequence(length: int) -> tuple[int, int]:
    tried = found = 0
    for sequence in product(range(6), repeat=length):
        tried += 1
        state = (0, 0)
        for move in sequence:
            state = moves(state)[move][1]
        found += GOAL in state
    return tried, found


for length in range(1, 7):
    tried, found = every_sequence(length)
    print(f"sequences of {length} moves: {tried}, reaching 4 litres: {found}")

start: State = (0, 0)
parent: dict[State, tuple[str, State] | None] = {start: None}
depth = {start: 0}
queue = deque([start])
while queue:
    state = queue.popleft()
    for name, following in moves(state):
        if following not in parent:
            parent[following] = (name, state)
            depth[following] = depth[state] + 1
            queue.append(following)

for level in range(max(depth.values()) + 1):
    print(f"depth {level}:", " ".join(str(s) for s, d in depth.items() if d == level))
print("states reached:", len(depth))
goal = min((s for s in depth if GOAL in s), key=depth.get)
route = []
while parent[goal] is not None:
    name, previous = parent[goal]
    route.append(f"{name} -> {goal}")
    goal = previous
print(f"fewest moves: {len(route)}")
for step in reversed(route):
    print(" ", step)

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

sequences of 1 moves: 6, reaching 4 litres: 0
sequences of 2 moves: 36, reaching 4 litres: 0
sequences of 3 moves: 216, reaching 4 litres: 0
sequences of 4 moves: 1296, reaching 4 litres: 0
sequences of 5 moves: 7776, reaching 4 litres: 0
sequences of 6 moves: 46656, reaching 4 litres: 1
depth 0: (0, 0)
depth 1: (3, 0) (0, 5)
depth 2: (3, 5) (0, 3) (3, 2)
depth 3: (3, 3) (0, 2)
depth 4: (1, 5) (2, 0)
depth 5: (1, 0) (2, 5)
depth 6: (0, 1) (3, 4)
depth 7: (3, 1) (0, 4)
states reached: 16
fewest moves: 6
  fill 5 -> (0, 5)
  pour 5 into 3 -> (3, 2)
  empty 3 -> (0, 2)
  pour 5 into 3 -> (2, 0)
  fill 5 -> (2, 5)
  pour 5 into 3 -> (3, 4)

The search reaches the states in waves, one move apart.

Moves against the states first reached at that many moves, from the run
Moves	States first reached
0	(0, 0)
1	(3, 0) (0, 5)
2	(3, 5) (0, 3) (3, 2)
3	(3, 3) (0, 2)
4	(1, 5) (2, 0)
5	(1, 0) (2, 5)
6	(0, 1) (3, 4)
7	(3, 1) (0, 4)

Following the parents back from (3, 4) gives the route, one move per edge.

The shortest route through the states, each edge labelled with its move

The search visits each reachable state once and tries six moves from each, so it does at most 16 × 6 = 96 steps, against 55,986 sequences tried up to length 6. In general it is O(S · m) for S states and m moves per state, and the states, not the sequences, are what to count when judging whether a search will finish in time.

← → move through sections and cards