Constraint satisfaction problem

Assign values from specified domains to variables so that all stated constraints hold simultaneously. A partial assignment can be rejected when it violates a constraint or leaves an unassigned variable with no permissible value. Backtracking applies this test during a depth-first search.

The hypergraph whose vertices are the variables of a constraint satisfaction problem and whose hypergraph edges are its constraint scopes. Several constraints can have the same scope. An incidence drawing uses extra scope nodes for display; these do not become extra variables of the original problem. Ordinary treewidth of a constraint hypergraph refers to treewidth of its primal graph, equivalently to a tree decomposition covering each whole scope, not to generalized hypergraph width measures.

The graph with one vertex per variable and an edge between distinct variables occurring in a common constraint scope. Each hypergraph edge of the constraint hypergraph becomes a clique. A constraint satisfaction problem consisting only of all-different constraints on a common constraint domain is exactly a proper graph colouring problem on this primal graph.

A cardinality constraint restricts how many members of a specified collection are selected or satisfy a property. For Boolean variables, exactly $k$ selected entries gives the displayed sum; upper and lower bounds give at-most and at-least variants. Constraint propagation can maintain the number already selected and the number still available. A requirement involving many variables is a global constraint, even when it has a compact arithmetic description.

Choose $k$ distinct squares of an $n\times n$ chessboard so that no chosen pair has absolute coordinate differences $(1,2)$ or $(2,1)$. One constraint satisfaction problem representation has $k$ square-valued variables, requiring distinctness and pairwise nonattack. Another has one Boolean variable per square, a cardinality constraint fixing their sum to $k$, and one mutual-exclusion constraint for every edge of the knight attack graph. The first has fewer variables when $k$ is small but represents each unlabelled placement up to $k!$ times; the second uses only binary constraint domains and sparse local attack restrictions.

The knight attack graph has one vertex per chessboard square and an edge between squares linked by a knight move. A nonattacking placement is an independent set. Colouring squares by the parity of the coordinate sum makes this a bipartite graph, because every knight move changes that parity. Every vertex has degree at most eight, with fewer attacks near the boundary.

Represent each original value choice $X_i=v$ by a Boolean variable $p_{i,v}$ and impose an exactly-one constraint for each original variable. For every forbidden tuple $(v_i{)}_{i\in S}$ of a constraint with scope $S$, add the Boolean clause ${\bigvee }_{i\in S}\neg p_{i,v_i}$. A complete original assignment satisfies every constraint exactly when its one-hot indicators satisfy all these Boolean clauses: each forbidden-tuple Boolean clause excludes precisely that joint choice. A satisfying assignment decodes by reading the unique true indicator for each original variable.

For constraint domain sizes $q_i$, pairwise uniqueness requires ${\sum }_i\left(\genfrac{}{}{0ex}{}{q_i}{2}\right)$ Boolean clauses. If a constraint has $f_C$ forbidden tuples and arity $r_C$, its contribution is $f_C$ Boolean clauses and $r_C{f}_C$ literal occurrences. Thus bounded arity gives a polynomial-size encoding in explicitly listed domains, whereas enumerating a succinct high-arity relation can be exponential in its description length. Unit propagation on this encoding can be weaker than arc consistency on the original binary constraints.

Enumerate assignments to a cycle cutset, reject internal violations, filter all crossing binary constraints, and solve the residual forest by tree-structured constraint satisfaction. A full solution restricts to one enumerated cutset assignment; the residual tree passes preserve all its values. Conversely, a consistent cutset assignment combined with supported residual solutions satisfies every constraint. These observations prove completeness and soundness.

With $n$ variables, maximum constraint domain size $q$ and cutset size $k$, there are at most $q^k$ assignments and $O((n-k)q^2)$ residual tree work per assignment. Internal cutset and crossing-constraint tests require additional accounting. The method is attractive when a small cycle cutset is available.^[ref]

Choose an unassigned variable constrained to the greatest number of other unassigned variables. This is commonly a tie-breaker after minimum remaining values. The relevant vertex degree is computed in the remaining constraint graph, rather than counting neighbors already assigned. It aims to make each decision constrain many future decisions without changing the solution set.

A restriction on the value of one variable. In a finite-domain constraint satisfaction problem, it can be applied by deleting disallowed values from that variable's constraint domain before search. It introduces no edge in the binary constraint graph.

Replace a finite many-variable relation $R(X_1,\dots ,X_k)$ by one auxiliary variable $Y$ whose domain is the allowed tuples of $R$, together with binary constraints equating each tuple coordinate to its corresponding $X_i$. Any original satisfying assignment extends to exactly its allowed tuple, and any satisfying encoded assignment projects to a solution of $R$. The tuple domain can be large; the transformation changes arity, not necessarily representation size efficiently when $R$ is succinct.

Place $N$ queens on an $N\times N$ chessboard so that none share a row, column or diagonal. One constraint satisfaction problem encoding uses a column variable $C_r\in \{1,\dots ,N\}$ for each row, with $C_r\ne C_s$ and $|C_r-C_s|\ne |r-s|$ whenever $r\ne s$. The pigeonhole principle explains why one queen per row loses no solutions. Prescribed occupied cells give the queens completion problem.

Complete a prescribed subset of occupied cells to a solution of the N-queens problem while retaining every prescribed queen. In a row-variable constraint satisfaction problem, a clue $(r,c)$ gives the singleton constraint domain $D_r=\{c\}$. Conflicting clues prove impossibility immediately, but nonattacking clues need not extend to a full solution. Backtracking decides the finite problem; hill climbing can search large candidate boards without an exhaustive guarantee.

A binary constraint satisfaction problem whose constraint graph is a tree. Restrict constraint domains by unary conditions first. Choose a rooted tree orientation and process children before parents. For each child $j$ of $i$, retain in $D_i$ only values having a compatible value in the already reduced $D_j$. Thus every retained parent value has support in each child subtree.

If the root constraint domain becomes empty, no solution exists. Otherwise choose any root value, then recursively choose supported child values. A child-to-parent arc consistency pass need not enforce full arc consistency in both directions; the chosen directional condition suffices for this construction.

The proof uses mathematical induction on subtrees. A retained leaf value satisfies its unary requirements. Each retained parent value has a supported value in every child subtree. Those subtree solutions can be combined because the tree has no edges between different child subtrees. Therefore every retained parent value extends to a whole subtree solution, and every retained root value extends to a complete solution without backtracking.

For $N$ variables and maximum constraint domain size $d$, scanning all value pairs once per edge costs $O(N{d}^2)$ time complexity in Big O notation, when one binary constraint evaluation has unit cost. If a constraint requires summing bundle values, its evaluation cost must also be counted.

A directed requirement for a binary constraint $R_{ij}$: every remaining $x\in D_i$ has at least one support $y\in D_j$ with $(x,y)\in R_{ij}$. Revising the arc $i\to j$ deletes unsupported values from $D_i$; it does not directly delete values from $D_j$. Full arc consistency requires the condition in both directions on every edge of the constraint graph. On general graphs, it need not imply that a complete solution exists.

Compute an arc-consistency closure by revising every directed constrained pair in complete sweeps until one sweep deletes nothing. The first sweep is unconditional. With $v$ variables, maximum constraint domain size $d$, and $e$ constrained pairs, at most $vd$ deletions permit at most $vd+1$ sweeps. At $O(d^2)$ per revision plus $O(v)$ per emptiness scan, a direct time complexity bound is $O((vd+1)(e{d}^2+v))$. AC-3 uses a work list to avoid scanning unrelated arcs after each local change.

The greatest componentwise subdomains of given finite initial constraint domains satisfying every directed arc consistency condition, allowing empty subdomains. Repeated sound revisions to a fixed point produce this same closure regardless of revision order, provided every affected arc is eventually reconsidered.

For the proof, fix subdomains $E_i$ of the initial $D_i$ satisfying arc consistency. If all current $D_i$ contain $E_i$, every value in $E_i$ has a support in $E_j\subseteq D_j$, so revising $i\to j$ preserves $E_i$. Mathematical induction shows that every revision preserves every such family $E$. At termination the current domains themselves satisfy arc consistency, so they are the greatest such family. Algorithms that stop immediately on the first empty constraint domain need not finish computing the closure, but correctly establish that no complete solution exists.

An arc consistency algorithm maintaining a work list of directed constrained variable pairs. Revising $i\to j$ deletes each value of $D_i$ with no compatible value in $D_j$. If $D_i$ shrinks, incoming arcs $k\to i$ are reconsidered; the just-used neighbor $j$ need not be included, since deleted values had no support in $D_j$ and hence supported no surviving value there. Initially empty constraint domains are rejected before processing.

Each deletion preserves every complete solution: a solution using the removed value would supply its missing support. Therefore an empty constraint domain certifies impossibility. Successful termination establishes arc consistency but need not establish satisfiability. A triangle of two-valued inequality constraints supplies a counterexample: all values have pairwise support, but no assignment can satisfy all three inequalities.

For $v$ variables, $e$ constrained pairs and maximum constraint domain size $d$, assume constant-time compatibility tests for combined pair relations. A revision costs $O(d^2)$, and each shrinking source constraint domain can cause at most $d$ rounds of reconsideration of its incoming arcs. Thus there are $O(ed)$ revisions and time complexity $O(v+e{d}^3)$. Fixed $d$, including two-valued constraint domains, gives linear time in $v+e$.

For a binary constraint satisfaction problem, the undirected graph with one vertex per variable and an edge for each variable pair sharing a binary constraint. Unary conditions restrict constraint domains but add no edges. A more general constraint can be represented in a primal constraint graph by joining every pair of variables in its scope; such edges do not make a genuinely many-variable constraint binary.

After restricting constraint domains, a binary constraint can become automatically satisfied for every remaining pair of values. Removing such constraints can reveal a tree and enable tree-structured constraint satisfaction.

A set of vertices whose deletion leaves a forest. For a binary constraint satisfaction problem, fixing these variables and filtering the remaining constraint domains leaves independent instances of tree-structured constraint satisfaction. A valid cutset need not be minimum; smaller cutsets reduce the exponential enumeration in cutset conditioning.

A restriction involving two variables in a constraint satisfaction problem, represented by the allowed value pairs $R_{ij}$. Multiple restrictions on the same pair can be combined by intersection. For bundle allocation, disjointness and the two directional envy-free allocation inequalities together define one compatibility relation.

The set of values permitted for a variable $X_i$ in a constraint satisfaction problem. All assignments before relational constraints form the Cartesian product ${\prod }_i{D}_i$, whose cardinality is ${\prod }_i|D_i|$ for finite domains. Unary restrictions can be incorporated directly into the constraint domain by deleting forbidden values.

A finite constraint satisfaction problem on a $9\times 9$ array. Each entry must be one of the integers $1,\dots ,9$, and every row, column, and designated $3\times 3$ box must contain each value once. Given entries constrain the possible completions; backtracking searches those completions.

Kakuro is a numerical cross-sum puzzle on a grid. Each open cell holds a digit from one to nine; every specified horizontal or vertical run must sum to its clue without repeating a digit within that run. It is naturally a constraint satisfaction problem: cells are variables, digits are domains, and each run combines a sum constraint with an all-different constraint. This formulation supports general reasoning about feasible domains and search strategies without selecting or solving a particular puzzle.

Forward checking in a constraint satisfaction problem updates the domains of unassigned variables after assigning one variable. Remove any remaining value immediately incompatible with the new assignment; if a domain becomes empty, backtrack. For $X\ne Y$ with both domains $\{1,2\}$, assigning $X=1$ removes one from the domain of $Y$. Basic forward checking only enforces constraints involving the latest assigned value; it does not generally propagate every interaction among still-unassigned variables. Stronger constraint propagation can therefore detect failures earlier at additional computational cost.

The minimum remaining values heuristic chooses an unassigned variable with the smallest current legal domain during constraint search. It tries the most constrained choice first: a domain of size zero proves failure, and size one forces a value. If one variable has two remaining digits and another has seven, the first is selected, with a separate rule for ties. This can expose contradictions earlier but does not guarantee a minimum search tree. The heuristic depends on domains after the chosen propagation method, not simply on each variable's original domain size.

Constraint propagation repeatedly removes variable values incompatible with local consequences of a constraint satisfaction problem. The goal is to reduce the remaining search while preserving all genuine solutions. For $X<Y$ with domains $\{1,2\}$, enforcing support removes two from $X$ and one from $Y$, leaving the forced pair $(1,2)$. Arc consistency checks support across binary constraints; dedicated global-constraint propagators can reason about larger sets together. Reaching a propagation fixed point does not generally prove that the whole problem has a solution, because locally supported choices can still conflict globally.

Repeatedly apply a constraint propagation operation that only deletes values from finite constraint domains, preserves their order, and preserves every valid assignment. The sum of domain sizes is a nonnegative loop variant at every changing step, so repetition reaches a fixed point. For $N$ initial candidate values there are at most $N$ changing steps. An empty domain proves failure; a non-singleton fixed point may still require backtracking or explicit enumeration. Preservation of solutions, rather than mere deletion, is essential.

An all-different constraint requires its variables to take pairwise distinct values. For domains $D(X)=D(Y)=\{1,2\}$ and $D(Z)=\{1,2,3\}$, the first two variables consume values one and two in every solution, forcing $Z=3$. Pairwise inequality propagation may miss this deduction, while a global propagator can use a matching in a bipartite graph between variables and values. Hall's marriage theorem supplies the feasibility condition: every subset of variables needs at least as many available values as variables. This constraint appears in schedules, assignments and numerical puzzles.

Choose an unassigned variable with the fewest currently legal values. No legal values detects failure immediately; exactly one legal value forces a choice. This ordering can reduce the search tree without changing the set of solutions.