Problem-solving · Chapter 6

Constraint Satisfaction Problems

A CSP represents a problem as variables, domains, and constraints. Exploiting this structure can greatly reduce search compared with treating every complete assignment as a separate state.

Chapter guide

6.1 Defining Constraint Satisfaction Problems

A CSP has variables with domains and constraints restricting combinations of values. A solution is a complete, consistent assignment. Map coloring is a classic binary-constraint example.

6.2 Constraint Propagation: Inference in CSPs

Inference removes domain values that cannot participate in a solution. Arc consistency algorithms such as AC-3 propagate restrictions between neighboring variables.

6.3 Backtracking Search for CSPs

Backtracking assigns one variable at a time and abandons partial assignments that violate constraints. Minimum-remaining-values, degree, and least-constraining-value heuristics guide choices.

6.4 Local Search for CSPs

Local search begins with a complete assignment and repairs conflicts, often with min-conflicts. It can be effective for large problems such as scheduling.

6.5 The Structure of Problems

The constraint graph exposes structure. Independent components can be solved separately, while tree-structured CSPs admit efficient solution methods.

Key terms and worked assignment

Variable: a decision to make (region). Domain: allowed values (colors). Constraint: a rule restricting combinations. Backtracking: depth-first assignment that undoes a choice when it blocks every continuation. MRV chooses the unassigned variable with fewest legal values; least-constraining-value tries the value that rules out the fewest neighbor choices.

For example, if WA is coral, NT cannot be coral because WA–NT share a border. SA has five neighbors while V has two, so a degree heuristic may prefer SA when MRV ties; MRV itself depends on the current legal domains. A valid completion requires every adjacent pair to differ; three colors are sufficient for this map. The teaching solver uses fixed variable/color order, not MRV or LCV.

Interactive lab

Color a map with backtracking

Each region is a variable; colors are its domain; adjacent regions must differ. Advance the solver one assignment/backtrack at a time, or let it play the trace.

Color domain

Select a region and color to test your own assignment.

Selected region: none · Conflicts: 0

Select a region to assign a color or step the solver.

Solver complexity

Let n be the number of regions, k the maximum domain size, Δ the maximum degree, and e the number of constraint edges. Fixed-order depth-first backtracking can explore O(kⁿ) partial assignments. This implementation scans up to n variables at each search node and checks up to Δ neighbors per attempted value, giving worst-case O(kⁿ(n + Δ)) = O(nkⁿ) time because Δ≤n. Recursive working space is O(n), but this page precomputes and stores the whole assignment/backtrack trace, so solver trace memory is O(kⁿ) in the worst case (plus the O(n + e) CSP and assignment data). In the manual path, assigning one color is O(1); refreshing conflicts and the view scans the assignment/constraint graph in O(n + e) time, with O(n) assignment storage. For this fixed map, n=6, k=3, and Δ≤5; the six region controls and constraint graph are also visualization/UI memory.