Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Backtracking Search
Backtracking is depth-first search for CSPs that does not waste time below a state that already breaks a constraint:
- before generating successors, check for constraint violations
- if a constraint is violated, go back to the last decision point and try another value
Plain backtracking is still uninformed. It builds on DFS.
Smarter Search
Three questions make the search more intelligent:
- which variable to assign next
- in what order to try its values
- what the current assignment implies for the unassigned variables (forward checking and constraint propagation)
Forward Checking and Constraint Propagation
Constraint propagation pushes the effect of a constraint on one variable onto other variables, shrinking their domains. Forward checking is the simple version: after assigning , remove from each neighbour's domain the values that conflict with . If some domain becomes empty, backtrack at once.
In 4-queens, placing a queen crosses out its row and diagonals in later columns, so dead ends show up much earlier than with plain backtracking.
Map Colouring Example (Australia)
Regions WA, NT, SA, Q, NSW, V, T with colours {R, G, B}. Assign WA = R: forward checking removes R from NT and SA. Assign Q = G: removes G from NT, SA, NSW. Now NT and SA both have only {B} left. Forward checking alone does not notice, but full constraint propagation does: NT and SA are neighbours and cannot both be B, so this branch fails before either is assigned.
Variable and Value Ordering
| Heuristic | Rule | Why it helps |
|---|---|---|
| Most constrained variable (minimum remaining values, MRV) | pick the variable with the fewest legal values left, breaking ties by the one in the most constraints on unassigned variables | fails early, lowers branching factor later |
| Least constraining value | for that variable, try the value that rules out the fewest options for neighbours | keeps maximum flexibility for later assignments |
In map colouring SA touches the most regions, so it is a good first variable. When choosing a colour for Q, prefer the one that still leaves 1 value for SA over one that leaves 0.
Min-Conflicts Heuristic
A local search method:
- Start from a complete (possibly bad) assignment, e.g. random
- Pick a variable involved in a violated constraint
- Give it the value that minimises the number of violated constraints
- Repeat
For 8-queens, move one attacked queen within its column to the square with the fewest attacks. It is often very fast on large problems, but it is not guaranteed to find an answer.