Constraint Satisfaction Problems (CSPs): Detailed Description, Formalism, and Solving Methods

A Constraint Satisfaction Problem (CSP) is a structured decision problem where we model unknowns as variables with domains and restrict combinations via constraints so that the final assignment satisfies every constraint. Formally, a CSP instance consists of a finite set of variables, each with a finite domain, plus a set of constraints over subsets of variables; a solution is any assignment that makes all constraints true simultaneously.

Many CSPs are computationally hard in the worst case: determining whether a general finite-domain CSP is satisfiable is NP-complete, though important restricted classes become tractable.

1) Formal definition and notation

A common formal definition is: a CSP instance is a triple $(\mathbf{Vars}, \mathbf{Dom}, \mathbf{Cons})$ where:

• $\mathbf{Vars}$ is a finite set of variables.
• $\mathbf{Dom}$ gives each variable $X$ a finite domain $\mathbf{Dom}(X)$ of values.
• $\mathbf{Cons}$ is a finite set of constraints; each constraint is defined over some subset of variables and specifies which tuples of values are allowed. 2

A solution (sometimes called a satisfying assignment) is an assignment $s$ that maps every variable $X \in \mathbf{Vars}$ to a value $s(X) \in \mathbf{Dom}(X)$ and makes every constraint evaluate to true.

Satisfaction vs. satisfiable vs. unsatisfiable

• Satisfaction: an assignment satisfies a CSP if it satisfies all constraints.
• Satisfiable: there exists at least one satisfying assignment.
• Unsatisfiable: no satisfying assignment exists.

Key learning terms (1): Variables; Domain; Constraint; Assignment; Solution

2) Modeling: how real problems become CSPs

The practical power of CSPs is their modeling workflow:

1. Identify the decisions as variables.
2. Identify allowable values as domains.
3. Encode relationships/requirements as constraints.

Classic examples include scheduling, map coloring, and Sudoku.

Constraint types (conceptual)

Constraints can be:

• Unary constraints: restrict a variable’s domain.
• Binary constraints: restrict compatible pairs.
• Higher-arity constraints: restrict allowed tuples across multiple variables.

Binary constraints are especially convenient because many propagation techniques (like arc consistency) are defined using constraint graphs with directed edges.

Key learning terms (2): Constraint arity; Constraint graph; Unary/Binary/Higher-arity constraints

3) CSP search view: partial assignments and dead ends

To solve a CSP, solvers typically perform search over assignments. A central idea is that you don’t wait for full assignments: you maintain a partial assignment and check whether it is consistent with the constraints that are fully determined so far.

A standard baseline procedure is backtracking search:

• Start with an empty assignment.
• Pick an unassigned variable.
• Try values from its domain.
• If the choice violates constraints (given current assignments), backtrack.
• If all variables are assigned consistently, return success.

This “choose-try-check-undo” pattern is explicitly described for CSP backtracking search in course notes, including pseudocode structure and the role of variable/value ordering.

4) Constraint propagation: arc consistency and AC-3

Pure backtracking only checks constraints when variables become assigned. Constraint propagation improves performance by removing values from domains that cannot participate in any solution extension.

Arc consistency

A central local consistency notion is arc consistency for binary constraints. For a directed arc $(X_i \rightarrow X_j)$, the arc is arc-consistent if for every value $x \in \mathbf{Dom}(X_i)$ there exists some value $y \in \mathbf{Dom}(X_j)$ such that the binary constraint between $X_i$ and $X_j$ allows $(x,y)$.

A CSP is arc-consistent if every arc in its constraint graph satisfies this property.

AC-3 algorithm

The AC-3 algorithm enforces arc consistency by:

• Starting with a worklist of all directed arcs.
• Repeatedly selecting an arc $(X_i, X_j)$.
• Performing a “revise” step that removes values from $\mathbf{Dom}(X_i)$ that have no supporting value in $\mathbf{Dom}(X_j)$.
• When $\mathbf{Dom}(X_i)$ changes, re-adding neighboring arcs (into the worklist) because pruning may create new inconsistencies. 2

AC-3 was proposed by Mackworth in 1977, and the Wikipedia entry describes its queue/worklist behavior and directed-arc interpretation. 2

5) Heuristics: variable ordering and value ordering

Even with propagation, CSP solving often relies on heuristics to decide what to try next. Two widely used heuristics are:

MRV (Minimum Remaining Values)

MRV chooses the next variable to assign from those unassigned, selecting the one with the smallest number of legal values left (a “fail-fast” approach).

LCV (Least Constraining Value)

LCV orders domain values so that the chosen value rules out as little as possible from neighboring variables’ domains. 2

These heuristics are explicitly contrasted in CSP course material: MRV for variable selection and LCV for value ordering.

6) Computational complexity and tractability

In general, satisfiability for CSPs over finite domains is NP-complete. This motivates studying restricted CSP classes:

• limiting the constraint language or allowed constraint structure,
• restricting the domain size,
• restricting constraint arity,
• or identifying special algebraic properties that yield polynomial-time algorithms.

The complexity of CSPs and their relationship to NP-completeness is summarized in standard references on CSP complexity.

Key learning terms (3): NP-complete; Tractability; Constraint language; CSP complexity