State-Space Search for River, Jug, and Crossing Puzzles
State-space search replaces trial and error with a map of legal configurations, transitions, and visited states.
How state-space search solves a puzzle
Describe a state with only the facts needed to determine legal moves, define the starting state and goal test, and generate every legal next state. Mark visited states so loops are not explored again. Breadth-first search finds a shortest solution when every move has equal cost; weighted moves require a lowest-cost search instead.
State-space search maps each legal configuration and move. A visited-state record prevents loops and supports a shortest-path proof.
Key relationships
- A state records the information needed to determine legal next moves.
- A transition connects one legal state to another legal state.
- Breadth-first search finds a shortest path when every move has equal cost.
Build the first layers of a jug-state graph
Represent the 4-litre and 9-litre jugs as (amount in the small jug, amount in the large jug). From (0,0), only states created by filling a jug are new. Emptying an already empty jug and pouring between two empty jugs change nothing.
| Layer | New state | Move used | Why it matters |
|---|---|---|---|
| 0 | (0,0) | Start | Both jugs are empty |
| 1 | (4,0) | Fill the 4-litre jug | Creates a four-litre transfer source |
| 1 | (0,9) | Fill the 9-litre jug | Creates a nine-litre transfer source |
| 2 | (0,4) | Pour 4 into 9 | Moves the known quantity into the large jug |
| 2 | (4,5) | Pour 9 into 4 | Leaves a five-litre remainder |
Each state is stored once with its parent and move. Later, filling the large jug from (0,4), pouring into the small jug, emptying the small jug, and pouring again creates a six-litre amount in the large jug. The parent chain provides a replayable solution instead of a lucky list of moves.
State-graph checks
- Amounts never fall below zero or exceed jug capacity.
- Every pour stops when its source is empty or destination is full.
- Equivalent states are not expanded twice at the same or higher cost.
- The claimed shortest path follows the search layers in order.
Choose a complete state representation
A state must contain enough information to determine what can happen next. For a jug puzzle, the amounts in both jugs are enough. For a bridge puzzle, the people on each side and the torch side are required. The history is unnecessary unless a rule depends on it.
Make the representation compact but not incomplete. Omitting the torch location can make an illegal crossing appear possible. Including the entire move history creates many labels for configurations that are functionally identical.
Define legal transitions
Write move rules before searching. A jug can be filled, emptied, or poured until the source is empty or destination is full. A bridge move must carry the torch and obey capacity. Generate successors from these rules rather than inventing moves when stuck.
Reject a transition immediately if it violates a safety constraint or leaves the allowed state space. Keeping legality separate from strategy prevents a promising-looking route from quietly using an impossible move.
Search without cycling
Keep a frontier of states waiting to be explored and a visited set of states already reached. When a generated state is already visited at an equal or lower cost, discard that path. This stops fill, empty, refill loops from consuming the search.
Store a parent state and move beside each newly accepted state. When the goal is found, follow the parent links back to the start. The resulting path is an explanation that can be replayed and verified.
Match the search to the cost
Breadth-first search explores all states one move away, then two moves away, and so on. The first goal found is shortest in number of moves when every move costs the same. It does not minimize elapsed time when crossings have different durations.
For unequal nonnegative costs, expand the state with the lowest total cost reached so far. A move count and a time total answer different questions, so the goal must state which quantity is being minimized.
Prove that the answer is optimal
A working path proves that the goal is reachable. Optimality requires more. A breadth-first layer proves no shorter equal-cost path was skipped. A lowest-cost search proves no unfinished state has a cheaper route to the goal than the solution already found.
Small puzzles can be audited with a hand-drawn graph or table of states. Report the state definition, move rules, solution path, cost, and reason no cheaper path remains. That record is stronger than a sequence discovered by luck.
Apply the search model to two different costs
Track jug amounts as exact states in the six-litre water jug puzzle.
Then compare move count with elapsed time in the bridge and torch optimization problem.
For a broader view of variables and legal values, continue with constraint satisfaction.