When the CSP is huge (millions of variables) and backtracking is too slow, switch tactics: start from a complete (probably bad) assignment and improve it by local moves.
Min-conflicts
``` function min_conflicts(csp, max_steps): current = random_assignment(csp) for step in 1..max_steps: if current is solution: return current var = random_choice(conflicted_variables(current)) value = arg min over values: conflicts(var=value, others=current) current[var] = value return failure ```
Pick a variable that's involved in some unsatisfied constraint. Set it to the value that minimizes conflicts with current other-variable values. Repeat.
Properties
- Complete: no — can get stuck in local minima.
- Surprisingly powerful: solves million-variable n-queens in seconds. Made global routing for hardware design feasible.
- No optimality: terminates on the first satisfying assignment; doesn't search for "better" solutions.
Simulated annealing
When min-conflicts gets stuck, add controlled randomness: occasionally accept a worse move with probability . decreases over time ("cooling"). At high you explore widely; at low you converge.
Tabu search
Keep a short-term memory of recently-flipped variables; refuse to flip them again. Forces the search to explore rather than oscillating between the same two states.
When to choose local search
- Large CSPs where backtracking is hopeless.
- You only need a satisfying assignment, not all solutions.
- Approximate satisfaction is acceptable (constraint *almost* met).
- Online problems where new constraints arrive and you don't want to restart from scratch.
When to choose backtracking
- Smaller, structured CSPs where complete search is feasible.
- You need to prove unsatisfiability.
- You need an optimal solution (with constraint optimization).
SAT solvers don't really pick one
Modern SAT solvers (CDCL, used by industrial verification tools) are backtracking-based. Modern WalkSAT-style solvers (for huge fuzzy SAT, MAX-SAT) are local search. Knowing both exists and which to pick is most of the wisdom.