Artificial Intelligence & Data Science is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Constraint satisfaction problems

Constraint satisfaction problems (CSPs) formalise many engineering design and scheduling tasks: they are solved by search plus constraint propagation (arc consistency, forward checking, MAC) and by exploiting structure (tree-structured CSPs).

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Constraint satisfaction problems (CSPs) model many real engineering tasks: resource allocation, scheduling, register allocation, circuit layout and configuration problems. Engineers use CSP methods to prune large search spaces quickly (via constraint propagation) and to choose good variable/value orderings so a solver finds a feasible configuration fast.

Key ideas

Start from first principles and build the CSP formalism and principal algorithms.

  • Constraint satisfaction problem (CSP): A CSP is a triple (X, D, C) where X = {X1, X2, ..., Xn} is a finite set of variables, D = {D1, D2, ..., Dn} assigns to each Xi a finite domain Di of possible values, and C is a set of constraints; each constraint restricts the allowed combinations of values for some subset of the variables (its scope). Assumption: domains are finite.

  • Assignment: A (partial) assignment is a mapping from some subset of variables to values from their domains. A complete assignment gives each variable a value.

  • Consistent assignment: An assignment is consistent if it does not violate any constraint whose scope is fully assigned in that assignment. A complete and consistent assignment is a solution to the CSP.

  • Constraint graph: Draw one node per variable; draw an undirected edge between Xi and Xj when there is a constraint whose scope includes both Xi and Xj. This graph shows problem structure visually: clusters, trees, cycles.

  • Binary CSP: All constraints have scope size ≤ 2. Any CSP can be converted to an (expanded) binary CSP; many algorithms assume binary constraints.

  • Backtracking search (basic): Depth-first search that extends a partial assignment variable-by-variable; when a constraint would be violated, backtrack. Worst-case examines all possible assignments.

  • Inference / Constraint propagation: BEFORE or DURING search, use the constraints to remove values from domains that cannot be part of any solution. Two common forms:

    • Node consistency: remove domain values that violate unary constraints.
    • Arc-consistency: For a binary constraint between Xi and Xj, the arc (Xi -> Xj) is arc-consistent if for every value a in Di there exists some b in Dj such that (a,b) satisfies the constraint between Xi and Xj. An algorithm making all arcs consistent is a common preprocessing step. For non-binary constraints, the analogous notion is generalized arc consistency (GAC): for each value of a variable in a constraint's scope, there exists a tuple of values for the other variables in the scope such that the constraint is satisfied.
  • AC-3 algorithm (arc-consistency, version 3): Maintain a queue of arcs; repeatedly pop an arc (Xi -> Xj), call REVISE(Xi, Xj): remove values a from Di that have no supporting value b in Dj. If REVISE removed values, add all arcs (Xk -> Xi) for neighbors Xk ≠ Xj back to the queue. Terminate when queue empty (all arcs consistent) or some domain becomes empty (CSP unsatisfiable).

  • Forward checking: During backtracking, when assigning a variable Xi = a, immediately remove values from the domains of unassigned neighbors that conflict with Xi = a. If any neighbor loses all values, backtrack.

  • Maintaining arc consistency (MAC): During search, after each assignment call an arc-consistency procedure (e.g., AC-3), typically initializing the queue with all arcs (Xk -> Xi) into the newly assigned variable Xi and propagating; this enforces arc consistency on the subproblem of unassigned variables and prunes more than forward checking.

  • Heuristics for variable ordering:

    • Minimum remaining values (MRV): choose the variable with the smallest number of remaining legal values in its domain (tie-breaks by degree).
    • Degree heuristic: choose the variable involved in the largest number of constraints on unassigned variables.
  • Heuristics for value ordering:

    • Least constraining value (LCV): choose the value that rules out the fewest choices for the remaining variables.
  • Tree-structured CSPs: If the constraint graph is a tree (connected acyclic), there is a linear-time algorithm:

    1. Choose any variable as root and order variables from root to leaves.
    2. Do a backward pass: for each edge parent->child starting from leaves, make the parent arc-consistent w.r.t. the child (prune parent domain values that have no support in child domain).
    3. Do a forward assignment pass from root to leaves: choose any value for root; for each child, pick a value consistent with the parent's assigned value (guaranteed to exist). Exact claim: a tree-structured CSP can be solved in O(n d^2) time where n = number of variables and d = maximum domain size (derivation below).

Derivation universities ask for (tree-CSP complexity):

  • Backward pass: each arc (parent, child) is revised once; revision checks for each value in parent's domain whether some value in child's domain supports it: cost O(d^2) per arc. With n-1 arcs in a tree, backward pass O((n-1) d^2) = O(n d^2).
  • Forward pass: assignment chooses for each child a supporting value; finding a support can be done in O(d) per child using saved supports or table lookups, so total O(n d). Combined O(n d^2).

Exact algorithm statements and assumptions are above. For diagrams: draw the constraint graph as nodes labeled by variable names; label each edge with the type of binary constraint (e.g., ≠ or >) if present.

Formulas

Time(backtracking worst-case) = O(d^n) — d is max size of any domain, n is number of variables; applies to uninformed backtracking without inference.

Time(tree-CSP) = O(n · d^2) — n variables, d = max domain size; applies when constraint graph is a tree and constraints are binary.

AC-3 worst-case time = O(a · d^3) — a = number of directed arcs (two per undirected binary constraint) in the constraint graph, d = maximum domain size; this is for the standard AC-3; some variants can be analyzed as O(a · d^2) depending on data structures.

Space(assignment only) = O(n) — storing the current partial assignment; plus additional space for domains/pruning info typically O(a · d) (or O(n · d) for variable-centered storage).

(Each symbol: n = number of variables (dimensionless), d = maximum domain size (dimensionless), a = number of directed arcs (two per undirected binary constraint) (dimensionless).)

Worked examples

Example 1 — Model answer: Map-colouring (Australia) with 3 colours {R,G,B}. Problem: Variables = {WA, NT, SA, Q, NSW, V, T}. Constraints: neighbouring states must differ (binary ≠ constraints). Show a backtracking solution using MRV and LCV; show steps. Solution sketch (model answer expected):

  1. All domains initially {R,G,B}. Using MRV (tie anywhere), pick WA first (degree high). Suppose assign WA = R.
  2. Forward-check neighbors: NT and SA cannot be R, their domains become {G,B}.
  3. Next MRV variable could be NT (domain size 2). Try NT = G. Forward-check: SA domain still {G,B} but SA cannot be G if adjacent to NT? SA adjacent to NT and WA; since WA=R and NT=G, SA cannot be R or G => SA must be B (domain size 1). Assign SA = B by propagation.
  4. Continue with constraints: Q adjacent to NT and SA; since NT=G and SA=B, Q cannot be G or B => Q = R. NSW adjacent to SA and Q: SA=B, Q=R → NSW != B and != R => NSW = G. V adjacent to SA and NSW → SA=B, NSW=G => V != B and != G => V = R. T can be any color (not adjacent to others in mainland) choose R.
  5. Full assignment found: WA=R, NT=G, SA=B, Q=R, NSW=G, V=R, T=R. A full-marks answer shows the assignment and explains the MRV and propagation steps.

Example 2 — AC-3 run (model answer): Variables: X, Y. Domains: D(X) = {1,2,3}, D(Y) = {1,2}. Constraint: X > Y (binary). Show AC-3.

  1. Initialize queue with arcs (X->Y), (Y->X).
  2. Pop (X->Y): REVISE(X,Y): remove x values with no y supporting x>y. For x=1: no y<1 → remove 1. For x=2: y=1 supports → keep. For x=3: y=1 or 2 supports → keep. Now D(X) = {2,3}. Since D(X) changed, add arcs (Z->X) for neighbors Z of X other than Y (none here).
  3. Pop (Y->X): REVISE(Y,X): for y=1, exists x in {2,3} with x>1 so keep; y=2, exists x=3 → keep. No change.
  4. Queue empty → done. Result: D(X)={2,3}, D(Y)={1,2}. Explain each queue operation and show final domains.

A full exam answer will state the initial queue, each REVISE call, which values removed, and termination condition.

Common mistakes

  • Saying arc-consistency guarantees a solution: arc-consistency is only a necessary condition, not sufficient (except in special cases like trees).
  • Mistaking node-consistency, arc-consistency and path-consistency or swapping their definitions.
  • Wrong complexity claims: writing O(d^n) for algorithms that use effective propagation (e.g., MAC) without justification.
  • In tree-CSP proofs, forgetting to count arcs as (n-1) or double-counting an undirected edge as two revisions incorrectly.
  • When tracing AC-3, failing to add the correct incoming arcs back to the queue after a REVISE removal.

For your exam

  • Short note: compare forward checking vs MAC; state strengths and tradeoffs (computation vs pruning). Full marks need algorithmic descriptions and typical use-cases.
  • Derivation: prove tree-structured CSP algorithm and its O(n d^2) complexity; include per-arc cost and number of arcs (n−1). Full answer shows both passes and cost breakdown.
  • Numerical/tracing: run AC-3 on a small CSP and show queue operations and domain changes step-by-step. Full marks need initial queue, each pop, REVISE effects, and final domains or contradiction.
  • Diagram: draw constraint graph for a given CSP, label nodes with variables and edges for binary constraints; if asked, mark a spanning tree or cycle. Full marks need clear labels and explanation.
  • Short program (optional): if asked for a solver sketch, pseudocode for backtracking with forward checking and MRV is acceptable; full marks require correctness comments.

Quick check

  1. Define a CSP in one sentence.
  2. What does MRV heuristic choose and why?
  3. State one guarantee of AC-3 (what it ensures after completion).

Answers: 1) A CSP is a triple (X,D,C) of variables, finite domains and constraints such that solutions are complete assignments consistent with all constraints. 2) MRV picks the unassigned variable with the fewest legal values remaining to fail early and reduce branching. 3) AC-3 ensures every arc (Xi->Xj) is arc-consistent: every value in Di has at least one supporting value in Dj (or detects an empty domain meaning unsatisfiable).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?