Constraint Satisfaction¶
CSP Fundamentals¶
Definition¶
A Constraint Satisfaction Problem is defined by:
Variables: \(X = \{X_1, X_2, \ldots, X_n\}\)
Domains: \(D_i\) for each variable (set of possible values)
Constraints: relations restricting combinations of values
A solution is an assignment of values to all variables that satisfies every constraint.
Types of constraints:
Unary: restricts a single variable (e.g., \(X_1 \neq \text{red}\)).
Binary: relates two variables (e.g., \(X_1 \neq X_2\)).
Higher-order (global): involves three or more variables (represented via constraint hypergraph).
Preference (soft) constraints: define optimization problems, solvable via linear programming.
Map Coloring Example¶
Variables: regions (e.g., WA, NT, SA, Q, NSW, V, T for Australia).
Domains: {Red, Green, Blue}.
Constraints: adjacent regions must have different colors.
Constraint graph: nodes = variables, edges = binary constraints.
Backtracking Search¶
Basic Algorithm¶
Depth-first search with one variable assigned per level:
Select an unassigned variable.
Try each value in its domain.
If consistent with constraints, recurse.
If no value works, backtrack to the previous variable.
Complexity: \(O(d^n)\) in the worst case for \(n\) variables with domain size \(d\).
Variable Ordering — MRV¶
Minimum Remaining Values (MRV): choose the variable with the fewest legal values remaining. Fails early on constrained variables (“fail-first” strategy).
Degree heuristic (tiebreaker): among MRV-tied variables, choose the one involved in the most constraints on unassigned variables.
Value Ordering — LCV¶
Least Constraining Value (LCV): choose the value that rules out the fewest choices for neighboring variables. Maximizes future flexibility (“fail-last” for values).
Forward Checking¶
After assigning a variable, immediately remove inconsistent values from the domains of neighboring unassigned variables.
Acts as an early warning system: if any neighbor’s domain becomes empty, backtrack immediately.
Detects failure earlier than plain backtracking.
Constraint Propagation and Arc Consistency¶
Arc Consistency (AC-3)¶
An arc \((X_i, X_j)\) is arc-consistent if for every value in \(D_i\), there exists a consistent value in \(D_j\).
AC-3 algorithm:
Initialize queue with all arcs.
For each arc \((X_i, X_j)\), remove values from \(D_i\) that have no support in \(D_j\).
If \(D_i\) changed, re-enqueue all arcs \((X_k, X_i)\) where \(k \neq j\).
If any domain becomes empty, the CSP has no solution.
Complexity: \(O(ed^3)\) where \(e\) = number of arcs, \(d\) = max domain size.
Forward checking is a restricted form of arc consistency (only checks arcs from assigned to unassigned variables).
Structured CSPs¶
If the constraint graph is a tree (no loops), the CSP can be solved in \(O(nd^2)\) time.
Algorithm: choose a root, apply directed arc consistency from leaves to root (topological order), then assign values from root to leaves.
For non-tree graphs: tree decomposition or cutset conditioning to exploit near-tree structure.
Reference: Topological Search (U. Washington)
Iterative (Local Search) Methods¶
Min-Conflicts algorithm:
Start with a complete random assignment.
Select a variable that violates a constraint.
Reassign it to the value that minimizes the number of conflicts.
Repeat until solution found or max iterations reached.
Effective for large CSPs (e.g., million-queens). Typically solves n-Queens in roughly \(O(n)\) steps.