Backtracking (Overview) for CSP — Beginner-Friendly Notes

1. What Backtracking Is

Depth-first assignment for CSP: pick an unassigned variable → try a value → check constraints → if ok recurse, else try next value, if none → backtrack to previous variable and try alternative.

function Backtrack(assignment):
  if assignment complete: return assignment
  var = select-unassigned-variable()
  for value in ordered-domain(var):
    if value consistent with assignment:
      add var=value
      inferences = propagate(var, value)  # optional forward checking
      result = Backtrack(assignment)
      if result != failure: return result
      undo inferences and assignment
  return failure

It is DFS in the space of partial assignments — only one variable assigned per depth.

2. Why Better Than Naive Search

• Tests constraints incrementally — fails early, prunes large subtrees (e.g., after 3 assignments violating a constraint, you skip all extensions).
• Commutativity: order of assignments doesn't matter → no need to consider permutations, branching reduces.

3. Three Improvements You Must Mention in Exams

1. Variable ordering — MRV (Most Constrained Variable / Minimum Remaining Values): pick variable with fewest remaining legal values — fail fast.
2. Value ordering — LCV (Least Constraining Value): try value that rules out fewest options for neighbours — keep flexibility.
3. Constraint propagation — Forward Checking / Arc Consistency:
   • Forward checking: when you assign $Xi=v$, remove inconsistent values from neighbours' domains; if any domain empties → backtrack immediately.
   • AC-3 (arc consistency): stronger — propagate beyond immediate neighbours.

4. Tiny Trace — Map Colouring WA, NT, SA with {R,G,B}

• Assign WA=R → neighbours NT loses R → domain {G,B}. Pick SA (MRV) → etc. If SA has no value → backtrack to NT.

5. Complexity

• Worst $O(d^n)$ where $d$ = domain size, $n$ = variables — but with propagation + ordering, often dramatically smaller.

6. One-Line Summary

Backtracking searches CSP assignments depth-first with incremental consistency checks, improved by MRV variable ordering, LCV value ordering and forward checking/arc consistency to prune early.

7. Quick Self-Check

1. Why is backtracking better than generating all full assignments and testing?
2. What does MRV do and why does it help?