Constraint Satisfaction Problems (CSPs)

Background — In previous searches, the state was a black box accessed only by successor functions and goal tests. In CSPs, we open the box.

Constraint Satisfaction Problem: States and goal test conform to a standard, structured representation.¹1. Modeling a problem as a CSP means you can use generic, highly-optimized constraint solvers rather than writing custom search algorithms. A CSP consists of 3 components:

1. X: A set of variables \{X_1, ..., X_n\}.
2. D: A set of domains \{D_1, ..., D_n\}, one for each variable.
3. C: A set of constraints that specify allowable combinations of values.

CSP Problem Formulation

• State: An assignment of values to some or all variables.
• Consistent Assignment: Does not violate any constraints.
• Complete Assignment: Every variable is assigned.
• Goal: A complete, consistent assignment.

CSP Backtracking Search

A form of DFS specifically for CSPs.²2. Backtracking is the fundamental engine behind logic puzzles like Sudoku. We assign one variable at a time and backtrack immediately when a constraint is violated.

function BACKTRACKING-SEARCH(csp) returns a solution or failure
    return BACKTRACK({}, csp)

function BACKTRACK(assignment, csp) returns a solution or failure
    if assignment is complete then return assignment
    var \leftarrow SELECT-UNASSIGNED-VARIABLE(csp)
    for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
        if value is consistent with assignment then
            add {var = value} to assignment
            inferences \leftarrow INFERENCE(csp, var, value)
            if inferences \ne failure then
                add inferences to assignment
                result \leftarrow BACKTRACK(assignment, csp)
                if result \ne failure then return result
        remove {var = value} and inferences from assignment
    return failure

Why? — Because standard DFS would blindly assign variables until the end and THEN fail the goal test. CSP backtracking fails early (the moment a constraint is violated).

Heuristics for CSPs

We can speed up backtracking immensely by making smart choices in SELECT-UNASSIGNED-VARIABLE and ORDER-DOMAIN-VALUES.

• Minimum Remaining Values (MRV): Choose the variable with the fewest legal values left (fail-fast).³3. Also known as the “most constrained variable” or “fail-first” heuristic. If a variable is going to fail, we want to know as soon as possible to prune the tree early.
• Degree Heuristic: Choose the variable involved in the largest number of constraints on remaining variables (tie-breaker for MRV).
• Least Constraining Value: Given a variable, choose the value that rules out the fewest choices for neighboring variables (leaves maximum flexibility).

Inference and Forward Checking

Forward Checking: When variable X is assigned, look at each unassigned variable Y connected to X. Delete from Y’s domain any value inconsistent with X.

• Arc Consistency (AC-3): A stronger form of inference.⁴4. AC-3 is an algorithm that recursively propagates constraints until the entire network is “arc consistent”, often solving simple CSPs completely before search even begins. If X loses a value, we re-check all neighbors of X to ensure they are still consistent.

function AC-3(csp) returns csp, possibly with reduced domains
    // Input: csp, a binary CSP with variables {X1, X2, ..., Xn}
    // Output: the CSP, possibly with reduced domains
    queue \leftarrow all arcs in csp
    while queue is not empty do
        (Xi, Xj) \leftarrow REMOVE-FIRST(queue)
        if REVISE(csp, Xi, Xj) then
            if size of Di = 0 then return false
            for each Xk in NEIGHBORS(Xi) \text{$-$} {Xj} do
                add (Xk, Xi) to queue
    return true

function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi
    revised \leftarrow false
    for each x in Di do
        if no value y in Dj satisfies constraint between Xi and Xj then
            delete x from Di
            revised \leftarrow true
    return revised

Analysis — Time complexity is O(n^2 d^3) where n is number of variables and d is domain size.

Local Search for CSPs

Local search works well on CSPs by starting with a complete (but likely inconsistent) assignment and iteratively reassigning variable values to reduce conflicts.

function MIN-CONFLICTS(csp, max_steps) returns solution or failure
    // Input: csp, a constraint satisfaction problem; max_steps, step limit
    // Output: a solution, or failure
    current \leftarrow an initial complete assignment for csp
    for i = 1 to max_steps do
        if current is a solution for csp then return current
        var \leftarrow a randomly chosen conflicted variable from csp
        value \leftarrow the value v for var that minimizes CONFLICTS(var, v, current, csp)
        set var = value in current
    return failure

Note — Min-Conflicts is remarkably effective. Given a random initial state, it can solve n-queens in almost constant time for arbitrary n (e.g., n = 10{,}000{,}000). The key heuristic is min-conflicts: choose the value that violates the fewest constraints.