Three classical search problems from CE 213, the AI course I took on exchange at
the University of Essex, rebuilt from scratch as things you can play with. The
arc is the course's own: first a state space small enough to draw whole and
flood with breadth-first search; then a space too big to draw, where a heuristic
decides how much of it you visit; then an opponent, where search stops finding
paths and starts finding moves. What each rebuild changes, and what the labs
actually asked, is in the
Search at Play case study.
Left bank
river
Right bank
Everyone starts on the left bank. Ferry all three across without a meal being made.
c corn · g goose · f fox · m the man with the boat · left|right of the river · struck
states: something gets eaten
The whole puzzle, drawn: 6 of the 16 states are fatal, and the
10 safe ones leave only two corridors from start to goal, each
7 crossings long, meeting where the goose rides back. With JavaScript
enabled this plate adds the board itself: row the cargo across, watch your path trace
through this graph, or let breadth-first search flood it layer by layer.
Plate I
The corn, goose and fox crossing beside its complete state space: 16 states, six of them fatal (struck and dashed). Row the cargo across and your path traces live through the graph; Solve by BFS floods the safe states layer by layer and stops the moment it touches the goal, seven crossings out.
Uniform-cost search and A* on the default grid world: nodes expanded and path cost.
search
expanded
path cost
uniform cost
92
14
A* · Manhattan
38
14
Both searches, run at build time on this plate's default map: the same cheapest path
(cost 14), but uniform cost settles 92 cells to A*'s
38, because the Manhattan heuristic keeps the frontier leaning
toward the goal. With JavaScript enabled the map is paintable and both expansions
replay side by side.
Plate II
The same grid world solved twice: uniform cost on the left, A* with Manhattan distance on the right. Paint walls and swamp (step cost 5), drag the start and goal, and compare expanded counts; Replay animates both frontiers in lockstep. Set the heuristic to h = 0 and A* collapses into uniform cost, expansion for expansion.
Minimax value of each kind of opening move in tic-tac-toe.
opening
value under best play
center
draw
corner
draw
edge
draw
Solved at build time: minimax reaches
5,478 distinct positions from the empty board and
values the game at 0, a draw. Every opening holds that draw. With
JavaScript enabled this plate lets you play the table anyway, and open the search to
see the value of every move you were offered.
Your move: you are X, the bot holds the table.
Your options · minimax values
Plate III
Tic-tac-toe against exact minimax. Show the search opens the game tree from the current position: every option with its value, and the replies to whichever one you point at; hover an empty square for the value of moving there. The bot cannot be beaten, and the tree is the reason why.
Puzzle
Technique
Next cell
Run
Speed
123456789
123456789
123456789
123456789
3123456789
123456789
123456789
123456789
123456789
123456789
5123456789
123456789
4123456789
123456789
6123456789
123456789
123456789
7123456789
1123456789
123456789
4123456789
123456789
123456789
123456789
5123456789
2123456789
123456789
123456789
123456789
123456789
123456789
123456789
123456789
7123456789
123456789
123456789
123456789
123456789
123456789
7123456789
8123456789
123456789
123456789
123456789
123456789
8123456789
3123456789
123456789
123456789
123456789
123456789
123456789
4123456789
123456789
6123456789
123456789
5123456789
8123456789
123456789
9123456789
123456789
123456789
123456789
123456789
2123456789
123456789
123456789
123456789
123456789
1123456789
123456789
9123456789
7123456789
123456789
123456789
2123456789
123456789
123456789
123456789
123456789
123456789
24 clues placed. Striking them from their peers leaves
217 candidates across 57 empty cells, which is
about 10^31.8 ways to fill the grid if the constraints stopped mattering. Press Step.
Assignments
0
Backtracks
0
Constraint checks
0
Arc revisions
0
Steps
0
Candidates left
217
Ways left to fill
10^31.8
ochre outline: the cell in hand · dashed outline: the cell that vetoed it · green tint:
candidate sets that shrank this step · ochre tint and ×: a cell with no candidates left ·
small digits: the candidates still standing
The three techniques, run to the end
Assignments, backtracks and constraint checks for each technique on the same puzzle.
technique
assignments
backtracks
constraint checks
outcome
Backtracking
572,844
63,618
4,275,870
solved
Forward checking
15,356
11,111
109,434
solved
AC-3
208
113
12,912
solved
Stiff · 24 clues, in reading order, computed when this page was built. Backtracking pays
2,754 times
as many assignments as AC-3 for the same grid. Race them again for any other puzzle and
ordering.
Stiff · 24 clues: generated the same way as the others, dug a good deal further. Propagation no longer settles it, so all three techniques have to search, and the gap between them opens. Checked at build time, by an exhaustive count that
stops at two, to have exactly one solution.
Plate IV
Sudoku as a constraint satisfaction problem: 81 variables, nine values each, 810 binary not-equal constraints. Empty cells show the candidates they still have, and the counters keep score. Run one puzzle with each technique in turn, then change what the search branches on: minimum remaining values costs nothing and buys more than either kind of lookahead.
The first three had originals in Java and Python coursework: breadth-first search on
this same four-bit river, uniform cost against A* on the 8-puzzle, and a minimax
player with alpha-beta pruning. The fourth had no lab behind it; constraint
satisfaction is the pillar the course never reached, and it is here because the
other three kept pointing at it. These pages rebuild the ideas for the browser
rather than republish the labs; the write-up at
/projects/search-at-play/ keeps the honest
numbers, including where the rebuilds take the easy road.