AI Search Puzzles

Two classic state-space search problems. Play them, then let the AI solve them.

State (0, 0)
Moves 0
Par –
★★★

Goal state reached

Rules & AI notation

X = litres currently in the big jug. Y = litres currently in the small jug. The jugs have no markings, so these six operators are the only legal moves.

Fill X
If X < capacity, fill the big jug from the tap.
Fill Y
If Y < capacity, fill the small jug from the tap.
Empty X
If X > 0, pour the big jug out on the ground.
Empty Y
If Y > 0, pour the small jug out on the ground.
Pour X→Y
Pour from X into Y until X is empty or Y is full — whichever comes first.
Pour Y→X
Pour from Y into X until Y is empty or X is full — whichever comes first.

A state is the ordered pair (x, y). The start state is (0, 0) and the goal test is x = target ∨ y = target. "Par" is the true shortest path, computed live by breadth-first search — beat it and you can't, match it and you've found an optimal solution.

Path through the state space

No moves yet.
State (3,3,L)
Crossings 0
Par 11
★★★

Tap a figure on the boat's bank to load it aboard. Tap one in the boat to send it back.

LEFT BANK
RIGHT BANK
Missionary Cannibal

Everyone crossed safely

Rules & AI notation

Three missionaries and three cannibals must cross a river. There is one boat.

Boat size
The boat carries 1 or 2 people — never zero, never three.
Rowing
Someone must be aboard to row. The boat cannot cross empty.
Safety
On either bank, cannibals must never outnumber missionaries — the missionaries there would be eaten. A bank with zero missionaries is always fine.
Goal
Move all six people to the right bank.

A state is the triple (m, c, b) — missionaries on the left, cannibals on the left, and which side the boat is on. Start is (3, 3, L), goal is (0, 0, R). The safety rule is what turns this into a constrained search: many states are reachable but illegal, and a good search algorithm prunes them. The shortest solution takes 11 crossings.

Path through the state space

No crossings yet.