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

The Developer Workshop receives a shift schedule: each post must have a guard on duty, no individual can be assigned to two posts simultaneously, and night shift eligibility and rest intervals are subject to strict limits. While enumerating all possible schedules would eventually yield a valid solution, the vast majority of combinations fail before even filling the first few positions.

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,\ldots,X_n},\quad D_i,\quad C={C_1,\ldots,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, no first-feasible solution can be considered 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

The original version stored constraints as directed (var, assigned_var), only recording (a,b), which could lead to missed checks when the assignment order was reversed. A more robust approach is to have constraint objects declare their scope and perform unified validation against the currently assigned values.

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
    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:

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

Achieving arc consistency does not guarantee a global solution. Problems like map coloring and Sudoku may still have all locally consistent arcs, yet no complete assignment can be formed.

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.