Constraint Satisfaction Problems (CSP)

Backtracking CSP solver — the core algorithm

def backtracking_search(csp):
    return backtrack({}, csp)

def backtrack(assignment, csp):
    # If all variables assigned, return solution
    if len(assignment) == len(csp.variables):
        return assignment

    # Select an unassigned variable (heuristic applied here)
    var = select_unassigned_variable(assignment, csp)

    for value in order_domain_values(var, assignment, csp):
        if csp.consistent(var, value, assignment):
            assignment[var] = value

            # Propagate constraints (forward checking / AC-3)
            inferences = inference(csp, var, value, assignment)
            if inferences is not None:
                assignment.update(inferences)
                result = backtrack(assignment, csp)
                if result is not None:
                    return result
                # Remove inferences
                for inf_var in inferences:
                    del assignment[inf_var]

            del assignment[var]

    return None   # failure — triggers backtrack

Arc consistency condition: every value in Dᵢ has at least one compatible value in Dⱼ. If this fails for some x ∈ Dᵢ, remove x from Dᵢ (domain reduction).

AC-3 algorithm — O(cd³) where c = number of arcs, d = domain size

from collections import deque

def ac3(csp):
    """AC-3 arc consistency algorithm.
    Returns False if an inconsistency is found; True otherwise.
    Modifies csp.domains in place (domain reduction)."""
    queue = deque(csp.all_arcs())  # all (Xi, Xj) pairs

    while queue:
        Xi, Xj = queue.popleft()
        if revise(csp, Xi, Xj):
            if len(csp.domains[Xi]) == 0:
                return False  # domain wipeout → inconsistency
            # Xi's domain changed; re-check all arcs pointing INTO Xi
            for Xk in csp.neighbors[Xi]:
                if Xk != Xj:
                    queue.append((Xk, Xi))

    return True  # all arcs consistent

def revise(csp, Xi, Xj):
    """Remove values from Di that have no support in Dj.
    Returns True if Di was reduced."""
    revised = False
    for x in list(csp.domains[Xi]):
        # x has no support in Dj → remove it
        if not any(csp.consistent(Xi, x, Xj, y) for y in csp.domains[Xj]):
            csp.domains[Xi].remove(x)
            revised = True
    return revised

Tree-structured CSPs are tractable: solve by topological sort then arc-consistency pass from leaves to root, then assign root-to-leaves. Any value consistent at each step is guaranteed globally consistent.

1. What is the difference between forward checking and arc consistency (AC-3) in CSP solving? (Answer: Forward checking: when a variable is assigned, eliminate inconsistent values from UNASSIGNED neighbours only. Checks only one level of arcs. Arc consistency (AC-3): enforce arc consistency across all pairs — for every arc (Xi, Xj), ensure every value in Xi's domain has a consistent value in Xj's domain. Propagates further than forward checking. AC-3 catches failures earlier (before backtracking) but costs more per step. FC is a cheaper partial form of arc consistency.)
2. What is the minimum remaining values (MRV) heuristic and why does it help CSP performance? (Answer: MRV (Fail-First): choose the variable with the FEWEST legal values remaining in its domain as the next to assign. Intuition: variables likely to fail (few remaining values) are tried first — failures are detected early before wasting effort on other variables. Mathematically: MRV minimises the expected search tree size by exposing contradictions early. Compared to random variable ordering, MRV can reduce search by orders of magnitude on structured CSPs (e.g., n-queens, scheduling).)
3. What is the degree heuristic for tie-breaking in CSP variable selection? (Answer: When multiple variables have the same minimum remaining values (MRV tie), use the degree heuristic: choose the variable with the most constraints on other UNASSIGNED variables. High-degree variables are likely to constrain others more — removing them early reduces branching factor in subsequent choices. Degree heuristic is a tie-breaker for MRV, not a primary ordering. Together: MRV + degree heuristic significantly outperforms random variable ordering on benchmark CSPs.)
4. What is the least constraining value (LCV) heuristic and how does it differ from MRV? (Answer: MRV selects which VARIABLE to assign next (fail-first). LCV selects which VALUE to assign to the chosen variable (succeed-first). LCV: choose the value that rules out the fewest choices for neighbouring unassigned variables. Intuition: LCV tries the most promising value first — if this assignment leads to a solution, we find it faster. If it fails, we still need to backtrack. MRV and LCV have opposite philosophies: MRV finds failures fast; LCV finds solutions fast.)
5. What is the difference between a CSP and a constraint optimisation problem (COP)? (Answer: CSP: find ANY assignment that satisfies all constraints — a feasibility problem. Solution is valid or invalid. COP: find an assignment that satisfies all constraints AND MAXIMISES (or minimises) an objective function — an optimisation problem. Examples: CSP — solve a sudoku (any valid completion). COP — schedule nurses to shifts satisfying all constraints while minimising overtime cost. COP algorithms: branch-and-bound with constraint propagation, local search (simulated annealing, genetic algorithms), integer programming.)