Search & Problem Solving
Finding solutions by exploring a space of possibilities.
A Rubik's cube can be scrambled into about configurations, far too many to try one by one, yet a computer solves any scramble in seconds. The trick is not trying faster. It is choosing cleverly what to try next.
What you’ll learn
- Formulate a problem as a state space with actions, a goal test and step costs.
- Compare breadth-first, depth-first and uniform-cost search by what they find and what they cost.
- Explain how a heuristic guides A* and why an admissible one keeps it optimal.
- Compute a minimax value and explain why alpha–beta pruning is safe.
- Describe how constraints let a solver discard most of a search space unseen.
Problems as spaces
To a search algorithm, a problem is a state space: a set of states, the actions available in each, a goal test, and a cost for every step. Route planning, puzzles, scheduling and game playing all fit this mold.
Solving it means growing a search tree from the start state. The frontier holds the nodes generated but not yet expanded, and a search strategy is nothing more than the rule for which frontier node to expand next.
The tree grows fast. If every state offers actions, the branching factor, then there are different action sequences of length .
Every state offers 10 actions. How many different sequences of 5 actions are there?
Show the answer
100000 sequences
Each step multiplies the count by 10: , not . Ten actions deep it would be , ten billion. This exponential growth is the central enemy of search, and every idea in this lesson fights it.
Blind search: which node next?
Uninformed strategies know nothing about where the goal lies. They differ only in the order in which they take nodes off the frontier:
- Breadth-first search (BFS) expands the shallowest node first. It spreads out in rings and finds the path with the fewest steps.
- Depth-first search (DFS) expands the deepest node first. It dives down one corridor and backs up only at dead ends. It needs little memory, but its path can be long and winding.
- Uniform-cost search (UCS) expands the node with the cheapest path so far. When steps cost different amounts, it finds the cheapest path.
On a map where mud costs 5 per step and plain ground 1, which algorithm is guaranteed to return the cheapest path?
- BFS
- DFS
- UCS
- Any of them: they all reach the goal
Show the answer
C. UCS
UCS always expands the cheapest path on the frontier, so the first time it expands the goal, no cheaper route can exist.
The Hidden Layer lesson Uninformed Search adds iterative deepening, which combines BFS's guarantees with DFS's tiny memory, and counts exactly what each strategy costs in time and memory.
A sense of direction
Blind search spreads in every direction, even away from the goal. A heuristic is a cheap estimate of the cost still to go from node . On a grid, the Manhattan distance (rows apart plus columns apart) is a natural choice. It ignores walls, so it never overestimates.
Greedy best-first search always expands whatever looks closest to the goal. A* balances the cost already paid against the estimate of what remains:
Think first What happens if the heuristic overestimates, for example Manhattan distance?
A* turns greedier. It usually expands fewer nodes, but it may return a path that is not the cheapest. Trading optimality for speed on purpose is the idea behind weighted A*, which the Hidden Layer lesson Heuristic Search & A* develops along with ways to design good heuristics.
Search against an opponent
In a game, half the moves belong to an opponent who is trying to beat you. Minimax assumes the opponent plays perfectly. At MAX's turns you take the child with the highest value, at MIN's turns the opponent takes the lowest, and values back up from the leaves to the root. In this zero-sum setting, one player's gain is exactly the other's loss.
MAX moves first, then MIN. MAX's three moves lead to MIN nodes whose leaves are worth (to MAX) , then , then . What is the root's minimax value?
Show the answer
B.
The MIN nodes are worth , and . MAX takes the best of these, so the root is worth : the first move guarantees at least 3 whatever MIN does.
Constraints prune the space
Some problems care only about the final state, not the path to it. In a constraint satisfaction problem you give each variable a value so that every constraint holds. The classic example is coloring a map so that neighbors differ: Australia's seven regions, three colors, and one constraint per shared border.
Blind generate-and-test would check all complete colorings. A CSP solver uses backtracking instead. It colors one region at a time and backs up the moment a constraint breaks, so whole families of doomed colorings are never generated.
The big picture
Every method here attacks the same exponential tree with a different weapon: an expansion order, an estimate of the distance to go, a model of the opponent, or constraints. The same machinery reappears across AI: planners search over actions, game engines over moves, and systems like AlphaZero combine search with learning.
| Strategy | Expands next | Returns | Memory |
|---|---|---|---|
| BFS | Shallowest node | Fewest-step path | Large: the whole frontier |
| DFS | Deepest node | Some path, maybe long | Small: one branch at a time |
| UCS | Cheapest path so far | Cheapest path | Large |
| Greedy | Smallest | Some path, often fast | Large |
| A* | Smallest | Cheapest path if is admissible | Large, but explores less |
| Hidden Layer lesson | What you will do there |
|---|---|
| Uninformed Search | Analyze BFS, DFS, uniform-cost search and iterative deepening: completeness, optimality, time and memory. |
| Heuristic Search & A* | Prove when A* is optimal, derive heuristics from relaxed problems, and trade optimality for speed. |
| Games: Minimax, Alpha–Beta & MCTS | See why perfect move ordering lets alpha–beta search about twice as deep, and how Monte Carlo tree search plays Go. |
| Constraint Satisfaction Problems | Combine backtracking with MRV, forward checking and arc consistency, and meet the SAT solvers behind modern verification. |
Key takeaways
- Search turns a problem into a state space (states, actions, a goal test and costs) and grows a tree of possibilities, which explodes as .
- Uninformed strategies differ only in which frontier node they expand: BFS the shallowest (fewest steps), DFS the deepest (little memory), UCS the cheapest (least cost).
- A* expands by . With an admissible heuristic it still returns a cheapest path while exploring far less.
- Games are searched with minimax. Alpha–beta prunes branches that cannot matter without changing the answer, and huge games rely on evaluation functions or Monte Carlo tree search.
- Constraint solvers reject partial assignments early and propagate constraints, eliminating most of the space without visiting it.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
You need the solution with the fewest steps in a huge tree, but memory is tight. Which strategy fits best?
- Breadth-first search
- Depth-first search
- Iterative deepening
- Greedy best-first search
Show the answer
C. Iterative deepening
Iterative deepening runs depth-limited DFS with limits . It keeps DFS's small memory and, like BFS, finds the shallowest solution. Redoing the shallow levels costs little, because most nodes of a tree sit in its deepest level.
An A* heuristic sometimes overestimates the remaining cost. What can go wrong?
- A* may never find any path
- A* will always expand more nodes than UCS
- Nothing: any heuristic keeps A* optimal
- A* may return a path that is not the cheapest
Show the answer
D. A* may return a path that is not the cheapest
An overestimate can make a node on the cheapest path look worse than it is, so A* may reach the goal by a costlier route first. Admissibility, never overestimating, is exactly the condition that rules this out.
Searching the same game tree to the same depth, how does alpha–beta's result compare with plain minimax's?
- Identical value and move: it skips only branches that cannot change the result
- Slightly worse: pruning trades accuracy for speed
- Better: pruning removes the bad moves
- It depends on the order in which moves are examined
Show the answer
A. Identical value and move: it skips only branches that cannot change the result
A branch is pruned only once it provably cannot affect the decision, so alpha–beta returns exactly the minimax value. The saved time is what lets real engines search deeper.
Why can't a chess program search every line of play to the end of the game?
- The rules of chess do not say when a game ends
- The tree is astronomically large, so programs look a limited depth ahead and score positions with an evaluation function
- The opponent's moves are unpredictable, so looking far ahead is pointless
- Minimax only works on trees a few moves deep
Show the answer
B. The tree is astronomically large, so programs look a limited depth ahead and score positions with an evaluation function
With about 35 moves per position, the tree grows as roughly , far beyond any computer. Programs search as deep as time allows and estimate the value of the positions where they stop.
A backtracking solver colors Western Australia red, then tries red for its neighbor, the Northern Territory. What happens next?
- It keeps going and checks the constraints once every region is colored
- It restarts with a new random coloring
- It rejects the partial assignment at once and tries another color for the Northern Territory
- It recolors Western Australia, the first region it chose
Show the answer
C. It rejects the partial assignment at once and tries another color for the Northern Territory
A partial assignment that already breaks a constraint can never be completed into a solution, so backtracking rejects it immediately and revises the most recent choice.
Go deeper
- Uninformed Search · BFS, DFS, uniform-cost and iterative deepening, compared.
- Heuristic Search & A* · Admissible heuristics and the optimality of A*.
- Games: Minimax, Alpha–Beta & MCTS · Planning against an opponent.
- Constraint Satisfaction Problems · Backtracking, propagation and smart variable ordering.
Further reading
- S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapters 3, 5 and 6.
- P. E. Hart, N. J. Nilsson & B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics 4(2) (1968), 100–107.