Constraint Satisfaction Problems

A different way to frame a problem

A Constraint Satisfaction Problem (CSP) is defined by three things: a set of variables, each needing a value assigned to it; a domain for each variable, listing the values it's allowed to take; and a set of constraints, which restrict which combinations of values are allowed across variables. Solving a CSP means finding an assignment of a value to every variable such that no constraint is violated.

This framing is deliberately generic. Sudoku is a CSP: 81 variables (cells), domains of {1..9}, and constraints that every row, column, and 3x3 box contains no duplicates. Exam scheduling is a CSP: variables are exams, domains are time slots, and constraints prevent two exams with overlapping students from sharing a slot. Map coloring, job-shop scheduling, and resource allocation all fit the same mold — which is exactly why CSP solvers are general-purpose tools rather than problem-specific hacks.

Backtracking: the baseline algorithm

The standard way to solve a CSP is backtracking search: assign a value to one variable at a time, checking after each assignment whether any constraint is already violated. If a violation is detected, immediately abandon that branch and try a different value — there's no point continuing to assign other variables when the current partial assignment is already doomed. If all values for a variable fail, backtrack further, undoing the previous variable's assignment and trying its next alternative.

This is depth-first search over partial assignments, with early failure detection built in. The early detection is what separates it from naive generate-and-test (try every full assignment, then check it): backtracking prunes an entire subtree of possibilities the moment a partial assignment becomes invalid, which is often an exponential saving.

Constraint propagation: catching failures before they happen

Backtracking alone only detects a violated constraint after an assignment is made. Constraint propagation goes further: it proactively removes values from a variable's domain that could never participate in any valid solution, before that variable is even assigned, often detecting failure far earlier than plain backtracking would.

Arc consistency is the standard propagation technique. A variable X is arc-consistent with respect to variable Y if, for every remaining value in X's domain, there's at least one value in Y's domain that satisfies the constraint between them. The AC-3 algorithm repeatedly removes values that break arc consistency across every pair of constrained variables until no more removals are possible — sometimes this alone solves simple CSPs outright, and it always shrinks the search space before backtracking begins.

Why Sudoku solvers rarely need deep search

A well-implemented Sudoku solver can solve almost every standard puzzle using constraint propagation alone — repeatedly applying arc consistency (and stronger forms like "naked pairs" and "hidden singles," which are specialized propagation rules) until every cell has only one remaining candidate. Backtracking search is only invoked as a fallback for the rare puzzle where propagation alone leaves genuine ambiguity, at which point the solver guesses a value for one under-constrained cell and backtracks if that guess leads to a dead end.

This is the general CSP-solving pattern in practice: propagate as much as possible first, because it's cheap and deterministic, and fall back to search only for whatever ambiguity remains.

CSP techniques compared

CSPs versus other search and optimization approaches

It's worth distinguishing CSPs from the other search techniques in this track. A* search (Heuristics & Search in AI) finds a least-cost path to a single goal state; a CSP has no notion of path cost at all — any valid assignment is equally acceptable unless the problem is extended into a constraint optimization problem with an objective function layered on top. Genetic algorithms search by evolving a population of full (possibly invalid) candidate solutions toward higher fitness; CSP backtracking instead builds a single valid partial assignment incrementally and never considers an invalid full assignment at all. Each approach fits different problem shapes, and real scheduling systems sometimes combine CSP-style hard-constraint pruning with optimization-style objective scoring for the "best" solution among many valid ones.

What's next

CSPs handle problems with hard, binary constraints — a value either satisfies a constraint or it doesn't. Many real-world problems are softer than that, with constraints that are partially true or matters of degree. The next module, Fuzzy Logic Systems, covers exactly that case: reasoning with degrees of truth instead of strict binary logic.