State-space search: the water jug problem
Formulate a puzzle as states, actions, and a goal, and find a shortest solution with breadth-first search.
from collections import deque
def solve(cap_a, cap_b, goal):
start = (0, 0)
parents = {start: None}
queue = deque([start])
while queue:
state = queue.popleft()
a, b = state
if goal in state:
path = []
while state is not None:
path.append(state)
state = parents[state]
return path[::-1]
pour_ab = min(a, cap_b - b)
pour_ba = min(b, cap_a - a)
moves = ((cap_a, b), (a, cap_b), (0, b), (a, 0), (a - pour_ab, b + pour_ab), (a + pour_ba, b - pour_ba))
for following in moves:
if following not in parents:
parents[following] = state
queue.append(following)
return None
path = solve(3, 5, 4)
print(len(path) - 1)
print(path)
print(solve(2, 4, 3))6 [(0, 0), (0, 5), (3, 2), (0, 2), (2, 0), (2, 5), (3, 4)] None
Explanation
Many AI problems can be framed as search. A problem is defined by an initial state, the actions available in each state, a transition model that says which state an action leads to, a goal test, and a path cost. Search explores the graph of reachable states to find a sequence of actions from the initial state to a goal.
Breadth-first search expands states in order of their distance from the start. When every action costs the same, the first time it reaches a goal it has found a shortest solution, and it is complete on finite graphs. Its drawback is memory: it stores every state at the current depth. A parent map lets the program rebuild the path once the goal is found and also serves as the set of visited states, so no state is expanded twice.
In the water jug puzzle you have a 3-litre and a 5-litre jug and must measure exactly 4 litres. A state is the pair of current amounts. The actions are fill a jug, empty a jug, or pour one into the other until the source is empty or the target is full. Breadth-first search finds a 6-step solution. The program also shows that the same search reports no solution for 2- and 4-litre jugs and a goal of 3: every reachable amount is even, so the goal is unreachable.
Explore the dry run
from collections import deque def solve(cap_a, cap_b, goal): start = (0, 0) parents = {start: None} queue = deque([start]) while queue: state = queue.popleft() a, b = state if goal in state: path = [] while state is not None: path.append(state) state = parents[state] return path[::-1] pour_ab = min(a, cap_b - b) pour_ba = min(b, cap_a - a) moves = ((cap_a, b), (a, cap_b), (0, b), (a, 0), (a - pour_ab, b + pour_ab), (a + pour_ba, b - pour_ba)) for following in moves: if following not in parents: parents[following] = state queue.append(following) return None path = solve(3, 5, 4)print(len(path) - 1)print(path)print(solve(2, 4, 3))Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Take the oldest state from the queue: breadth-first order expands by distance from the start. | start (0, 0) | — | |
| Goal test: has either jug reached the target amount? | start (0, 0) | — | |
| Record how each new state was reached; this also marks it as visited. | (0, 0) → (0, 5) | — | |
| The solution has 6 actions: 7 states including the start. | (0, 0) → (0, 5) | 6 | |
| For 2- and 4-litre jugs, 3 litres is unreachable: the search exhausts every state and returns None. | (0, 0) → (0, 5) | 6 [(0, 0), (0, 5), (3, 2), (0, 2), (2, 0), (2, 5), (3, 4)] None |
Cost and common mistakes
BFS is O(V + E) time and O(V) memory for V reachable states. Here V is at most (cap_a + 1) × (cap_b + 1) = 24.
- Without a visited set, search on a graph with cycles can loop forever or repeat work exponentially.
- Breadth-first search finds fewest actions, which is the cheapest path only when all actions cost the same.
- State spaces often grow exponentially. Breadth-first search can run out of memory long before it runs out of time.
Try it yourself
Why does the program return None for jugs of 2 and 4 litres with a goal of 3?
Reveal answer and reasoning
Every amount reachable with capacities 2 and 4 is a multiple of 2, so 3 can never be measured. The search visits all reachable states and finds no goal.