A bomb, a fountain and two jugs
Die Hard with a Vengeance (1995). Simon's riddle: a 5-gallon jug, a 3-gallon jug, a fountain. Put exactly 4 gallons on the scale or the bomb goes off.
McClane and Zeus shout at each other for a full minute. A computer would not shout. It would try things systematically until something works. That is search, and it only works if the problem is written down precisely first.
Today's version: 4 L and 3 L jugs, and you need exactly 2 L. How many pours at minimum?
Same idea, different costume: Google Maps getting you from Mirpur 10 to Motijheel, a Rubik's cube solver, the fastest route through your Among Us tasks. Different problems, one recipe: states, actions, a goal, a cost.
The problem-solving agent
A goal-based agent that plans a whole sequence of actions before moving works in four phases:
Executing the plan without looking is open-loop control. It is safe only if the environment is fully observable, deterministic and known (last week's properties). A flooded road on the way breaks it.
function SIMPLE-PROBLEM-SOLVING-AGENT(percept) state ← UPDATE-STATE(state, percept) if plan is empty: goal ← FORMULATE-GOAL(state) problem ← FORMULATE-PROBLEM(state, goal) plan ← SEARCH(problem) if plan = failure: return NoOp action ← FIRST(plan); plan ← REST(plan) return action
Adapted from Russell & Norvig's simple problem-solving agent. Everything today lives in FORMULATE-PROBLEM; Weeks 2–4 live in SEARCH.
A problem, in five parts
| Part | Notation | Dhaka → Cox's Bazar |
|---|---|---|
| 1 · Initial state | s₀ | In(Dhaka) |
| 2 · Actions | ACTIONS(s) | {Go(Cumilla), Go(Chandpur), Go(Brahmanbaria)} |
| 3 · Transition model | RESULT(s, a) | RESULT(In(Dhaka), Go(Cumilla)) = In(Cumilla) |
| 4 · Goal test | IS-GOAL(s) | s = In(Cox's Bazar) |
| 5 · Path cost | Σ c(s, a, s′) | sum of road km (or minutes, or taka) |
Parts 1–3 together define the state space: every state reachable from s₀ by some sequence of actions.
Solution
A sequence of actions from the initial state to a goal state.
Optimal solution
A solution with the lowest path cost among all solutions.
A solution is a plan (actions), not a single final state. "Cox's Bazar" is not an answer; "Cumilla, Feni, Chattogram, Cox's Bazar" is.
Live lab: explore the water-jug state space
Click an action. Every new state you reach appears in the graph.
Click actions and watch the state graph grow: each new (x, y) you reach becomes a node.
Then press Solve with BFS: it explores level by level and returns the shortest plan.
Find all 14 states. Why are 6 grid points never reachable?
Worked example: formulating the water jug
Given
A 4 L jug and a 3 L jug, no markings, a tap with unlimited water, a drain. You can fill a jug, empty it, or pour one into the other until the source is empty or the target is full.
Find
All five parts of the formulation, and an optimal solution.
Method: Rich & Knight's production rules; Russell & Norvig's five-part template
Solution
Predict the answer first. Then reveal one step at a time.
Abstraction: what to leave out
The real trip to Cox's Bazar involves the bus company, the weather, the tea stop and 400 km of potholes. Our state is one word: In(city). Abstraction = removing detail. It is valid if every abstract solution expands into a real one, useful if each abstract action is easier than the original problem.
The state space is then a graph: nodes are states, edges are actions, weights are step costs. Search = finding a path in that graph without drawing all of it.
Why is the state for route finding just 'which city I am in', and not 'the whole map'?
Argue it in pairs for two minutes. There may be more than one defensible answer.
Live lab: the 8-puzzle
| Arrangements | 9! = 362,880 |
|---|---|
| Reachable from goal | 9!/2 = 181,440 |
| Branching factor | 2, 3 or 4 (avg ≈ 2.67) |
| Hardest instance | 31 moves (optimal) |
Click a tile next to the blank to slide it.
States: location of each of the 8 tiles and the blank.
Initial: any state (but see parity!).
Actions: move the blank Left, Right, Up, Down. ACTIONS(s) depends on where the blank is.
Goal test: matches 1–8 in order, blank last.
Path cost: 1 per move.
In the 1880s Sam Loyd offered $1,000 for solving the 15-puzzle with 14 and 15 swapped. Safe money: it is on the wrong side of the parity split.
Sundarbans crossing (Life of Pi edition)
Three bawalis (wood-cutters) and three tigers must cross a khal in a boat that holds at most two. Anyone can row (it is a puzzle). If on either bank the tigers ever outnumber the bawalis present there, lunch is served.
The classic "missionaries and cannibals", with better scenery.
State: (B, T, boat) = bawalis and tigers on the start bank, boat side (L/R). The other bank is implied.
Initial: (3, 3, L). Goal: (0, 0, R).
Actions: the boat carries {1B, 2B, 1T, 2T, 1B+1T}, only if the result is safe on both banks.
Cost: 1 per crossing.
Your turn · 1: eight queens, two ways
Place 8 queens on a chessboard so that no two attack each other (same row, column or diagonal).
(a) Give an incremental formulation and estimate how many action sequences a naive version must consider.
(b) Improve it so the state space is tiny.
(c) Give a complete-state formulation and its number of states. Which formulation suits which kind of search?
Work it out first.
Press Solve when the class has an answer.
Why state-space size matters: bd
If every state has b successors (branching factor) and the shallowest goal is at depth d, a level-by-level search generates up to
| d | Nodes (b = 10) | Time | Memory |
|---|---|---|---|
| 4 | 11,111 | 11 ms | 11 MB |
| 6 | ≈ 10⁶ | 1.1 s | 1.1 GB |
| 8 | ≈ 10⁸ | 2 min | 111 GB |
| 10 | ≈ 10¹⁰ | 3 hours | 11 TB |
| 12 | ≈ 10¹² | 13 days | 1 PB |
Assumes 10⁶ nodes per second and 1 KB per node.
| Problem | States |
|---|---|
| Water jug (4, 3) | 14 |
| Sundarbans crossing | 16 |
| 8-queens (smart) | 2,057 |
| 8-puzzle | 181,440 |
| 15-puzzle | ≈ 1.05 × 10¹³ |
| Rubik's cube | ≈ 4.3 × 10¹⁹ |
Memory runs out long before patience does. That single fact drives next week (IDS).
Worked example: route finding, BFS by hand
Given
The map below (km approximate). Start Dhaka, goal Cox's Bazar.
Find
BFS expansion order, and the route returned with its cost.
Method: graph-search BFS (Russell & Norvig)
Solution
Predict the answer first. Then reveal one step at a time.
Live lab: BFS vs DFS on the road to Cox's Bazar
Frontier
FIFO queue: pop the front (left)Explored set
never expand these againinitStart: frontier = [Dhaka]
Judging a search strategy: four questions
| Criterion | BFS (FIFO) | DFS (LIFO) |
|---|---|---|
| Complete? finds a solution if one exists | Yes, if b is finite | Graph search: yes in finite spaces. No in infinite ones (or with loops, as tree search) |
| Optimal? finds the cheapest | Yes, if all step costs are equal | No |
| Time | O(bd) | O(bm) |
| Space | O(bd): keeps a whole level | O(bm): one path plus siblings |
node = frontier.pop(0) # BFS: oldest first (queue) node = frontier.pop() # DFS: newest first (stack)
In Python, that one argument is the whole difference between the two algorithms.
b = branching factor (max successors)
d = depth of the shallowest goal
m = maximum depth of any path (may be ∞)
Next week's question: can we get DFS's O(bm) memory and BFS's completeness and optimality? Yes: iterative deepening.
Your turn · 2: trace DFS by hand
All edges cost 1. Run graph-search DFS from S to G. Break ties alphabetically; goal test when a node is popped.
Give the expansion order, the stack after each expansion, and the path returned. Then compare with BFS.
Work it out first.
Press Solve when the class has an answer.
Critical thinking · is BFS ever wrong?
A classmate says: "BFS always finds the shortest path, so Google Maps could just run BFS."
Using the Dhaka → Cox's Bazar map, is BFS's route optimal? Under what condition is BFS optimal, and what would you use instead?
Work it out first.
Press Solve when the class has an answer.
Planning with STRIPS: states as sets of facts
STRIPS (Fikes & Nilsson, SRI, 1971) writes each action as three lists: PRE facts that must hold, ADD facts made true, DEL facts made false. Anything not mentioned stays the same.
s′=(s∖Del)∪AddCurrent state
Goal (all must hold)
Your turn · 3: a hospital delivery robot
A robot carries medicine between rooms of a hospital (Store, Pharmacy, Ward3; Store–Pharmacy and Pharmacy–Ward3 are adjacent). It carries one package at a time.
Initial: At(R, Store), At(M, Pharmacy), HandEmpty, plus the Adj facts. Goal: At(M, Ward3).
Write STRIPS operators Move, PickUp, Drop and a plan.
Work it out first.
Press Solve when the class has an answer.
Real world: planning a spray drone's day
An agro-drone spraying a paddy field must cover every cell with enough battery and pesticide. Naive state: (cell, battery, tank, set of sprayed cells). A 20 × 20 field has 400 cells, so the "sprayed set" alone has 2400 ≈ 2.6 × 10120 values.
Real planners abstract: fix a lawn-mower (boustrophedon) sweep, so the state becomes (row, battery, tank) and the only decision is when to return to refill. Ambulances in Dhaka: state (junction, time of day), step costs from live traffic, not km.
Our formulation assumed a fully observable, deterministic, known world. Is the real world ever like that?
Argue it in pairs for two minutes. There may be more than one defensible answer.
Pop quiz
Question 1 / 5
Which of these is not one of the five parts of a problem formulation?
Three things to remember
A problem = initial state, ACTIONS, RESULT, goal test, path cost. A solution is an action sequence; optimal = lowest cost.
Formulation and abstraction decide the state-space size (8-queens: 10¹⁴ vs 2,057). Search cost grows like bd.
BFS = FIFO queue, complete, optimal for equal costs, O(bd) memory. DFS = LIFO stack, O(bm) memory, not optimal.
Formulate the Die Hard 3 riddle (5 and 3 gallon jugs, measure exactly 4 in the big jug) in five parts. Find an optimal solution and count the reachable states. Assignment 1 is published this week; Class Test 1 next week covers UCS, DLS, IDS and local search, and assumes today's BFS/DFS.
Work it out first.
Press Solve when the class has an answer.