Water Jug Puzzle Solver

How to use the water jug solver

Choose whether there is a tap to fill from and a drain to empty into, or only the water already in the jugs. Set how much each jug holds, and for the second kind how much each starts with. Then say what you want: one jug holding an exact amount, or each jug holding an exact amount (leave a jug blank if it does not matter). Solve gives the fewest moves, and Step walks through them with the jugs filling and emptying. A move is filling a jug, emptying it, or pouring one jug into another until the first is empty or the second is full, because without markings that is all you can measure.

The Die Hard water jug puzzle

A 5 gallon jug, a 3 gallon jug, a fountain, and you need exactly 4 gallons. Fill the 5, pour it into the 3, leaving 2. Empty the 3, pour the 2 across. Fill the 5 again and top up the 3, which takes just 1, and 4 are left in the 5. Six moves, and no shorter way exists; the solver above proves it by checking every state it could reach in fewer.

The older puzzle with 8, 5 and 3 pint jugs, the 8 full, asks you to share the wine into two lots of 4. There is no tap, only pouring, and it takes seven pours. It goes back at least to the sixteenth century, and the version with 12, 8 and 5 is named after the mathematician Siméon Denis Poisson, who is said to have been drawn to mathematics by it.

Why some amounts cannot be measured

With a tap and two jugs, every amount you can ever hold is a multiple of the jugs' greatest common divisor. A 6 and a 4 litre jug can measure 2, 4 and 6 but never 3, because everything you do adds or takes away 6s and 4s, and those always leave an even number. When the jugs share no common divisor, like 5 and 3, every whole amount up to the bigger jug can be measured. The solver says which case you are in, and when the water is fixed it simply checks every state that can be reached.

The water jug problem in AI: states and breadth-first search

The puzzle is a standard first example of search. A state is how much each jug holds, written like (2, 3). The start state is (0, 0), the goal is any state with a 4 in it, and the operators are fill, empty and pour. The diagram beside the solution draws that state space: every dot is a state you can reach, and the line is the solution. Breadth-first search explores states in order of how many moves away they are, so the first time it meets the goal it has found a shortest path. This is the whole thing in Python:

from collections import deque

def solve(caps, target):
    """Fewest moves to get `target` into any jug, or None."""
    start = (0,) * len(caps)
    prev = {start: None}
    queue = deque([start])
    while queue:
        state = queue.popleft()
        if target in state:
            path = []
            while state is not None:
                path.append(state)
                state = prev[state]
            return path[::-1]
        for i in range(len(caps)):
            nexts = [state[:i] + (caps[i],) + state[i+1:],      # fill jug i
                     state[:i] + (0,) + state[i+1:]]            # empty jug i
            for j in range(len(caps)):                          # pour i into j
                if i != j:
                    amount = min(state[i], caps[j] - state[j])
                    s = list(state); s[i] -= amount; s[j] += amount
                    nexts.append(tuple(s))
            for n in nexts:
                if n not in prev:
                    prev[n] = state
                    queue.append(n)
    return None

print(solve((5, 3), 4))

Run it and it prints the states on the way: (0, 0), (5, 0), (2, 3), (2, 0), (0, 2), (5, 2), (4, 3).

More puzzles you can solve by searching

The Tower of Hanoi solver and the 15 puzzle solver are the same idea on bigger state spaces, and the eight queens puzzle shows backtracking search step by step. For a puzzle you solve with your hands rather than a search tree, our brain teasers are made of wood and metal. There are more solvers on the puzzle tools page.