Constraint Satisfaction Problems: Backtracking, Propagation and Heuristics

Every semester the university must schedule hundreds of exams into rooms and time slots without clashes. This is not a path-finding problem — we do not care about the sequence of steps, only about the final assignment. Problems of this kind are Constraint Satisfaction Problems (CSPs), and they have a factored structure that makes them far more efficient to solve than generic search.

Definition#

A CSP consists of three components:

1. A set of variables $X = \{X_1, \dots, X_n\}$.
2. A domain $D_i$ of possible values for each variable.
3. A set of constraints $C$, each specifying allowed combinations of values for a subset of variables.

A complete, consistent assignment is a solution.

Other classic CSPs: Sudoku (81 variables, domain 1–9, all-different constraints on rows, columns and boxes), N-queens, job-shop scheduling and exam timetabling.

Types of constraints#

• Unary: restrict a single variable ($X_1 \ne \text{red}$).
• Binary: relate two variables ($X_1 \ne X_2$).
• Global / higher-order: involve many variables (AllDifferent).
• Soft constraints / preferences: "Prof. Rahman prefers morning slots" — these make it a constraint optimisation problem.

Backtracking search#

The basic algorithm is depth-first search that assigns one variable at a time and backtracks when a constraint is violated.

def backtrack(assignment, variables, domains, consistent):
    if len(assignment) == len(variables):
        return assignment
    var = select_unassigned(variables, assignment, domains)
    for value in order_values(var, domains):
        if consistent(var, value, assignment):
            assignment[var] = value
            result = backtrack(assignment, variables, domains, consistent)
            if result is not None:
                return result
            del assignment[var]
    return None

Because assignments are commutative (order does not matter), we only branch on one variable per level. That alone reduces the tree from $n!\,d^n$ to $d^n$ leaves. Still exponential — so we add intelligence.

Heuristics that make backtracking fast#

1. Minimum Remaining Values (MRV) — choose the variable with the fewest legal values left. This "fail-first" heuristic prunes dead ends early.
2. Degree heuristic — to break ties, choose the variable involved in the most constraints with unassigned variables.
3. Least Constraining Value (LCV) — for the chosen variable, try values that rule out the fewest choices for neighbours ("succeed-first").

Constraint propagation#

Instead of waiting to discover a conflict, we can infer reductions in domains.

Forward checking#

After assigning $X$, delete from each unassigned neighbour's domain any value inconsistent with $X$. If some domain becomes empty, backtrack immediately.

Arc consistency and AC-3#

A variable $X_i$ is arc-consistent with respect to $X_j$ if for every value in $D_i$ there exists some value in $D_j$ satisfying the constraint. The AC-3 algorithm enforces this across the whole network:

from collections import deque

def ac3(domains, neighbors, satisfies):
    queue = deque((xi, xj) for xi in domains for xj in neighbors[xi])
    while queue:
        xi, xj = queue.popleft()
        if revise(domains, xi, xj, satisfies):
            if not domains[xi]:
                return False                # inconsistency detected
            for xk in neighbors[xi]:
                if xk != xj:
                    queue.append((xk, xi))
    return True

def revise(domains, xi, xj, satisfies):
    removed = False
    for x in list(domains[xi]):
        if not any(satisfies(xi, x, xj, y) for y in domains[xj]):
            domains[xi].remove(x)
            removed = True
    return removed

AC-3 runs in $O(c\,d^3)$ time for $c$ binary constraints and domain size $d$. On easy Sudoku puzzles, arc consistency alone solves the whole grid without any search! Combining search with propagation at every node is called MAC (Maintaining Arc Consistency).

Local search for CSPs#

For very large problems, a different approach often wins: start with a complete (possibly inconsistent) assignment and repeatedly change the value of a conflicted variable to the value that minimises the number of conflicts — the min-conflicts heuristic. It solves the million-queens problem in a few dozen steps on average and is widely used in real scheduling systems.

Exploiting structure#

If the constraint graph is a tree, the CSP can be solved in $O(n d^2)$ time — linear in the number of variables — by ordering variables topologically and enforcing directional arc consistency. Many real problems can be made tree-like by removing a small cycle cutset or by tree decomposition. This is a recurring theme in AI: structure makes hard problems easy.