Constraint Satisfaction Problems: When Rules Define the Answer

From optimization to structured assignment

In lesson 6, we explored local search, algorithms that climb fitness landscapes to optimize a single objective function. The question was: which candidate configuration has the highest quality?

But many real problems go further. They don’t just ask “what has the highest fitness?” They ask “what assignment satisfies all these rules exactly?”

Imagine a hospital scheduling problem again, but now with hard constraints: each nurse must work exactly 3 shifts per week, certain pairs of nurses cannot work the same shift (due to interpersonal dynamics or conflict of interest), and specific shifts require specific skill combinations. These are not fuzzy preferences to optimize. They are absolute requirements that any valid solution must satisfy.

Or think about configuring components in a machine, coloring a map so adjacent regions differ, solving a Sudoku puzzle, or timetabling university courses so no professor teaches two classes at once. All of these are constraint satisfaction problems (CSPs): find an assignment of values to variables such that every constraint is satisfied exactly.

This is different from both pathfinding (lesson 4-5) and optimization (lesson 6). Unlike pathfinding, there is no path to trace. Unlike optimization, there is no continuous fitness function to improve incrementally. Instead, you have discrete variables, finite domains of allowed values, and constraints that partition the space into valid and invalid assignments.

Core learnings about CSPs

• A CSP is defined by variables (what decisions must be made), domains (what values each variable can take), and constraints (what combinations are forbidden).
• Constraint propagation techniques like AC-3 preprocess the problem by removing impossible values, shrinking the search space before search begins.
• Backtracking search assigns variables one by one and prunes branches immediately when constraints are violated, avoiding blind enumeration.
• Good variable ordering and propagation heuristics (like minimum remaining values) often determine success or failure on large problems.

CSPs in mathematical terms

We formally write a CSP as:

$$P = (X, D, C)$$

This notation means a CSP consists of these three components:

• $X = \\{X_1, X_2, \dots, X_n\\}$: the set of variables. For scheduling, $X_1$ might be “Nurse A’s shift”, $X_2$ might be “Nurse B’s shift”, and so on.
• $D_i$: the domain of variable $X_i$. For scheduling, $D_1 = \\{\text{Morning}, \text{Afternoon}, \text{Night}\\}$ means Nurse A can be assigned any of these three shifts.
• $C$: the set of constraints. For scheduling, one constraint might be “Nurse A and Nurse B cannot have the same shift”, written formally as $X_A \\neq X_B$.

A solution is a complete assignment $a$ such that every constraint in $C$ is satisfied. If a valid solution exists, the CSP is satisfiable; otherwise, it is unsatisfiable.

If notation like sets and subscripts feels unfamiliar, pause and visit Function notation for AI.

Why propagation helps before search

Naive search over CSPs is exponential: if there are $n$ variables each with domain size $d$, there are $d^n$ possible complete assignments to check. Even with backtracking (pruning branches when constraints are violated), the search can be slow.

Constraint propagation is a preprocessing step that shrinks the domains before search begins. The idea is: if a value in one variable’s domain has no supporting value in some other variable’s domain under their shared constraint, then that value is impossible and can be removed.

For an example: if constraint "$X_A \\neq X_B$" exists and $X_A = \\text{Morning}$, then $\\text{Morning}$ cannot be in $X_B$‘s domain. More generally, arc consistency ensures that for any arc $(X_i, X_j)$, each value in $D_i$ has at least one supporting value in $D_j$ under their constraint.

The AC-3 algorithm repeatedly processes the queue of arcs, removing unsupported values, until no more values can be pruned. The typical worst-case complexity is:

$$O(ed^3)$$

where $e$ is the number of constraints (arcs) and $d$ is the maximum domain size.

In the nurse-scheduling visualization, $e$ is the number of “must differ” links between nurses, and $d$ is the number of shifts each nurse could still take. At the start here, $d = 3$ because each nurse can be assigned Morning, Afternoon, or Night. So the expression $O(ed^3)$ is not just abstract complexity notation: it summarizes how much pairwise consistency checking AC-3 may need before backtracking even starts. In practical terms, it tells us that dense constraint graphs or large domains make propagation more expensive, but that expense can still save much larger amounts of search later.

If growth notation is unclear, visit Big-O growth intuition for search.

Backtracking after propagation

If propagation alone does not solve the CSP (reduces all domains to singletons), backtracking search takes over. The algorithm works as follows:

One useful extra term before the steps: forward checking means that after you assign one variable, you immediately remove now-impossible values from neighboring variables’ domains. If a neighbor is left with no legal values, you can abandon that branch early.

1. Pick an unassigned variable (many heuristics exist, like choosing the one with fewest remaining values, called minimum remaining values or MRV).
2. Try assigning it a value from its domain.
3. Check consistency with all existing assignments (forward checking).
4. If consistent, continue recursively to the next variable.
5. If inconsistent, backtrack immediately, undoing the assignment and trying a different value.

Backtracking is not blind search, the key is that it fails fast. The moment a variable assignment violates a constraint with an earlier assignment, the algorithm backtracks instead of exploring deeper on a doomed branch.

In practice, good variable ordering (MRV) and propagation (forward checking) often determine whether backtracking solves a problem in seconds or hours.

Exploring a realistic CSP: nurse scheduling

The interactive visualizer uses five nurses, three shift values, and a graph of “must differ” constraints. The goal is to assign each nurse to exactly one shift such that no two connected nurses share the same shift.

The visualization lets you observe two sequential phases:

1. AC-3 propagation shrinks the domains by removing unsupported values.
2. Backtracking search assigns variables one by one, using the reduced domains as a starting point.

Watch how much work AC-3 does before search begins, it often prunes a large fraction of the search space, making backtracking much faster.

Walkthrough: Propagation then search

Run this sequence to see the two-phase process:

1. Keep the algorithm on AC-3 and click Run until the queue is empty. Observe how domains become smaller without building a full assignment yet.
2. Watch the “violated constraints” count drop as propagation removes impossible values.
3. Now switch to Backtracking and click Run. Notice that the search space is much smaller because AC-3 already eliminated deadends.
4. Inspect the trace to see variable assignments and any points where backtracking occurs due to conflicts.

In human terms: smart preprocessing shrinks the search space dramatically. By removing impossibilities before you start assigning variables, you avoid wasting effort exploring obviously doomed branches. This is why propagation before search is the standard approach for CSPs in practice.

Relation to earlier lessons

• Lesson 4/5 emphasized path search over states.
• Lesson 6 emphasized optimization over fitness landscapes.
• This lesson emphasizes consistent assignments under explicit rules.

Concrete bridge: we still search, but the object changes from paths (lessons 4,5) and fitness peaks (lesson 6) to constraint-consistent variable assignments.

Why this matters in practice

CSP formulations appear in timetabling, scheduling, configuration, and allocation systems. Once a problem is phrased as variables + domains + constraints, you can apply propagation and structured search directly rather than naive brute force.

Notation quick reference

Symbol	Meaning	Detailed Explanation
$P$	a CSP instance	CSP in one mathematical frame
$X$	variable set	CSP in one mathematical frame
$X_i$	variable $i$	CSP in one mathematical frame
$D_i$	domain of $X_i$	CSP in one mathematical frame
$C$	constraint set	CSP in one mathematical frame
$e$	number of arcs/constraints	Why AC-3 helps before search
$d$	maximum domain size	Why AC-3 helps before search
$O(ed^3)$	AC-3 complexity summary	Why AC-3 helps before search

Concept deep dives

• Function notation for AI
• Big-O growth intuition for search

What comes next

In lesson 8, we move to planning: finding action sequences that transform the world from an initial state to a goal state under explicit action models.

Next: Post 8, Planning and STRIPS

---

References and Further Reading

• Mackworth, A.K. “Consistency in Networks of Relations.” Artificial Intelligence 8(1), 1977.
• Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2020. Chapter 6.
• Dechter, Rina. Constraint Processing. Morgan Kaufmann, 2003.
• Haralick, R.M. and Elliott, G.L. “Increasing Tree Search Efficiency for Constraint Satisfaction Problems.” Artificial Intelligence 14(3), 1980.

---

This is Lesson 7 of 18 in the AI Starter Course.