2.2 CSP, Constraint Propagation and Backtracking: Eliminate the Impossible First, Then Try Assignments

A shift schedule needs coverage, prevents one person from working in two places at once, and imposes night-shift qualifications and rest periods. Exhaustive search over finite domains can find a solution or establish that none exists, but many combinations already fail after the first few assignments. Getting the solver to say “no” sooner can save everyone some overtime.

A Constraint Satisfaction Problem (CSP) breaks the problem into variables, domains (value sets), and constraints. The key insight of a solver isn't in generating complete solutions faster, but in propagating the consequences of early local choices as early as possible.

Learning Objectives

• Model problems using variables, domains, and constraints;
• Implement backtracking and forward checking that are independent of variable order;
• Understand MRV, degree, LCV, and arc consistency;
• Distinguish between local consistency, satisfiability, a single solution, and all solutions.

1. The Form of CSP

A finite CSP consists of:

$$X=\{X_1,\dots ,X_n\},D_i,C=\{C_1,\dots ,C_m\}.$$

• Variables $X_i$;
• A domain $D_i$ for each variable;
• Constraints that specify which combinations of variables are allowed.

A complete and constraint-satisfying assignment is a solution. If the goal is to minimize cost, it becomes a constraint optimization problem, the first feasible solution is not guaranteed to be optimal.

2. Constraints Have Different Scopes

• unary: shift != night;
• binary: adjacent regions have different colors;
• global: AllDifferent(X1, ..., X9);
• arithmetic/cumulative: total resource capacity and time interval bounds.

Splitting a global constraint into multiple binary constraints may preserve the set of feasible solutions but loses stronger propagation capabilities. For example, AllDifferent can leverage a global matching structure to detect infeasibility earlier than sequentially checking each pair !=.

3. A Minimally Correct Solver That Is Order-Independent

If a constraint is stored only under the directed key (a,b), a lookup in the reverse assignment order may miss it. Give each constraint an explicit scope and check it once all variables in that scope have values.

This Python 3.9+ function fragment (partial) needs a list of distinct variables, finite domains, and a list of constraints. Every scope must reference declared variables. Validate supplied partial assignments against domains and completed constraints, then copy them before searching so the caller's dictionary is preserved.

from dataclasses import dataclass

@dataclass(frozen=True)
class Constraint:
    scope: tuple[str, ...]
    predicate: object

def consistent(assignment, constraints):
    for constraint in constraints:
        if all(v in assignment for v in constraint.scope):
            values = [assignment[v] for v in constraint.scope]
            if not constraint.predicate(*values):
                return False
    return True

def backtrack(variables, domains, constraints, assignment=None):
    assignment = {} if assignment is None else assignment.copy()
    if any(v not in variables or value not in domains[v]
           for v, value in assignment.items()):
        return None
    if not consistent(assignment, constraints):
        return None
    if len(assignment) == len(variables):
        return assignment.copy()

    var = next(v for v in variables if v not in assignment)
    for value in domains[var]:
        assignment[var] = value
        if consistent(assignment, constraints):
            result = backtrack(variables, domains, constraints, assignment)
            if result is not None:
                return result
        del assignment[var]
    return None

This implementation is clearer in its correctness, but it only validates after all values within the constraint scope have been assigned, resulting in weak propagation.

4. Forward checking

After assigning a value to a variable, immediately remove incompatible values from the domains of its unassigned neighbors. If any neighbor's domain becomes empty as a result, trigger backtracking immediately.

When implementing, avoid directly and permanently modifying shared domains; instead, use a reversible trail or a domain copy. Copying is simple but expensive, while a trail is more efficient, but can introduce subtle errors if the backtracking recovery is incomplete.

Forward checking only considers the current assignment and its immediate neighbors, and thus cannot detect when two unassigned variables have no feasible pair of values that can satisfy both.

5. Arc Consistency and AC-3

Under a binary constraint $C(X,Y)$, the arc $X\to Y$ is arc-consistent if every value in $D_X$ has at least one supporting value in $D_Y$.

AC-3 repeatedly revises inconsistent arcs. This is pseudocode; revise removes values with no support:

queue ← all directed arcs
while queue not empty:
    (X, Y) ← pop(queue)
    if revise(X, Y):
        if domain[X] is empty: fail
        add (Z, X) for every neighbor Z ≠ Y

Arc consistency does not guarantee a global solution. Give each vertex of a triangle the domain {red, blue} and require different colors on adjacent vertices. Every color has support across each arc, yet the triangle cannot be colored with two colors. See Berkeley CS 188 on constraint filtering for the limits of local propagation.

6. Variable and Value Ordering

MRV

Select the variable with the fewest remaining legal values, prioritizing early failure detection.

Degree Heuristic

When MRV is tied, prefer the variable that is constrained by the most unassigned neighbors.

LCV

Try assigning the value that removes the fewest values from its neighbors, preserving flexibility for future assignments.

These heuristics influence search efficiency without altering the solution set. LCV scoring incurs computational overhead; it may not provide a speed advantage on small problems.

7. Modeling is typically more important than heuristic tuning

• Use a tight domain, don’t start with all possible values and then eliminate them via constraints;
• Choose variables that reflect true independence in the real-world scenario;
• Use global constraints to preserve structural integrity;
• Break symmetry: when three colors are interchangeable, fix the color of the first region;
• Move precomputable fixed relationships out of the search space;
• Never disguise soft preferences as hard constraints.

An inappropriate time granularity might classify a feasible shift schedule as infeasible, while overly coarse variables could miss essential rest intervals.

8. Unsat Also Needs Explanation

In reality, "unsat" is often more informative than a solution. Solvers should strive to return conflict constraints (or unsat cores) to help business stakeholders determine whether the issue stems from actual capacity limits or from contradictory rules.

Soft constraints can be assigned penalties, enabling weighted CSP or optimization models. It's essential to clearly distinguish between rules that are absolutely non-negotiable and those that are merely preferred. Additionally, the overall score must not obscure the fact that one entity may be bearing an undue burden.

9. Testing

Empty variable set
Single-variable empty domain
Asymmetric input order
Multiple solutions versus unique solution
Locally consistent but globally unsatisfiable
Symmetric solutions
Domain fully restored after backtracking
Conflict between hard and soft constraints

Enumerate all possible assignments for small instances and compare against the results from an optimization solver.

Common Misconceptions

• Consistent nodes and arcs guarantee a solution: They are only local properties.
• Registering constraints in one direction is sufficient: The solving order might miss critical checks.
• Finding the first solution means optimal scheduling: Feasibility is not the same as optimality.
• MRV is always faster: Heuristics come with their own overhead and depend heavily on the problem structure.

Exercise

1. Fix the map coloring constraints so that the solution remains valid regardless of variable ordering.
2. Implement forward checking and count the number of domain wipeouts.
3. Construct a CSP that is arc-consistent but has no solution.
4. Distinguish between hard rules and soft preferences in scheduling, and explain the objective function.

Summary

CSP exposes the structure of a problem through variables and constraints. Backtracking handles variable selection, while constraint propagation enforces early elimination of impossible assignments. The overall correctness and efficiency of the solver are determined by modeling choices, global constraints, and recovery mechanisms.

The next lesson moves into probabilistic representations: when evidence is incomplete, instead of asking whether a conclusion is certain, we compute the probability distribution over possible outcomes given the available evidence.