Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

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.

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

HeuristicRuleWhy 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 variablesfails early, lowers branching factor later
Least constraining valuefor that variable, try the value that rules out the fewest options for neighbourskeeps 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:

  1. Start from a complete (possibly bad) assignment, e.g. random
  2. Pick a variable involved in a violated constraint
  3. Give it the value that minimises the number of violated constraints
  4. 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.