Constraint Satisfaction Problems

A constraint satisfaction problem, or CSP, describes a set of choices and the rules that connect them. Its state is a factored representation: you can inspect individual variables and their values, then reuse general methods for pruning and search.

Variables, domains, and constraints

A variable names something to choose. Its domain lists its allowed values. A constraint specifies which combinations may occur together. For workshops A and B, let each value be a time slot from $\{1,2,3\}$. The rule “A comes before B” has scope $\{A,B\}$ and relation $\{(1,2),(1,3),(2,3)\}$. Writing $A<B$ expresses the same relation compactly.

The scope names the variables involved; the relation gives the allowed tuples of values. Mixing these up leads to a model in which “red” becomes a variable. In map coloring, regions are variables and colors are values.

What counts as a solution?

An assignment gives values to variables. Three checks describe its status:

• It is partial if some variables have no value.
• It is complete if every variable has a value.
• It is consistent if it violates no constraint among the assigned variables.

A solution must be complete and consistent. With $A=2$ alone, the assignment is consistent but partial. Extending it with $B=1$ makes it complete and inconsistent. Choosing $B=3$ gives a solution to this two-variable example. A consistent partial assignment may still have no possible completion: unassigned variables can run out of compatible choices.

Read a constraint graph

For a binary CSP, draw one node per variable and one edge for each constrained pair. In a simplified Australia map, the variables are WA, NT, SA, Q, NSW, V, and T, each with domain {red, green, blue}. The neighboring pairs are WA–NT, WA–SA, NT–SA, NT–Q, SA–Q, SA–NSW, SA–V, Q–NSW, and NSW–V. Each edge requires different colors.

One solution is WA red, NT green, SA blue, Q red, NSW green, V red, and T red. Check every edge, including SA–V. T has no edge, so its color is independent of the mainland. There are 6 mainland colorings and 3 choices for T, giving 18 solutions. A constraint involving several variables needs a hypergraph representation; an extra constraint node can connect to every variable in its scope.

Domains and search size

A finite discrete domain is a fixed list, such as three colors. An infinite discrete domain might contain every nonnegative integer start time. A continuous domain might contain real-valued times. The latter two need representations and methods suited to those domains; linear programming handles continuous linear constraints.

For $n$ variables with $d$ values each, there are $d^n$ complete assignments. The map has $3^7=2187$ candidates before constraints remove any. Finite CSPs include NP-complete problems, so a general polynomial-time solution method is not known. Their internal structure still makes pruning possible: the solver can rule out a choice without listing every full assignment containing it. Only the final values determine whether the answer is valid; the path used to find them is irrelevant.

Constraints differ in how many variables they connect and in whether they state requirements or preferences. Recognizing that structure helps you write a faithful model and choose useful propagation methods.

Classify the scope

A unary constraint restricts one variable. If workshop E cannot use slot 1, apply $E\mathrm{\ne }1$ by shrinking its domain from $\{1,2,3\}$ to $\{2,3\}$ before search. A binary constraint relates two variables, such as $A<B$ or $A\mathrm{\ne }D$. A binary CSP contains unary and binary constraints only.

A higher-order constraint involves at least three variables. If task durations X, Y, and Z must fill 10 hours, write $X+Y+Z=10$. With each duration in $\{1,2,3,4,5\}$, the tuple $(2,3,4)$ fails, while $(2,3,5)$ works. Checking a higher-order rule requires the values to work together.

Keep useful global constraints

A global constraint gives a named rule over a variable-sized group. $\mathrm{Alldiff}(X_1,\dots ,X_k)$ requires different values for every pair. Its solution set equals the set defined by $k(k-1)\mathrm{/}2$ pairwise inequalities. For nine Sudoku cells, that is 36 binary constraints.

The global form also gives a solver access to group reasoning. Three variables restricted to two distinct values cannot all differ, even though each pair separately has a compatible assignment. Equal solution sets do not guarantee equal pruning strength.

A capacity rule can also be global. Here $\mathrm{Atmost}(10,P_1,P_2,P_3)$ means $P_1+P_2+P_3\le 10$: the total number of people assigned to the three tasks cannot exceed ten. The arguments represent quantities being added, so this rule permits, for example, $(3,4,3)$.

Convert a finite constraint to binary form

Introduce an auxiliary variable U whose values are the allowed triples for $X+Y+Z=10$. One possible value is $(2,3,5)$. Add three binary constraints: the first component of U equals X, the second equals Y, and the third equals Z. Selecting that value for U therefore requires $X=2$, $Y=3$, and $Z=5$.

Every original valid triple corresponds to a value of U, and every consistent assignment involving U yields a valid original triple. This construction lets binary methods handle a finite higher-order constraint. Its cost is the potentially large tuple domain, which is why solvers often retain the original global or higher-order rule.

Requirements and preferences

With soft constraints, the task becomes a constraint optimization problem, or COP: satisfy all hard rules and minimize total preference cost. Branch-and-bound and local search can be used for optimization.

Test the model against a known valid assignment and a known invalid one. An invented inequality between unrelated workshops removes legitimate schedules; a missing shared-trainer constraint admits impossible ones. Preferences also need care: turning “afternoon preferred” into “afternoon required” can eliminate every feasible schedule.

A model should describe the decisions directly enough that the rules are easy to express. Start by identifying what must be chosen, then assign domains and translate each requirement over the variables it actually involves.

Build a workshop timetable

Five one-slot workshops share three time slots: 1 morning, 2 midday, and 3 afternoon. Let A be Python Basics, B Python Advanced, C Statistics, D Databases, and E Ethics. Each workshop is a variable with initial domain $\{1,2,3\}$.

Shared participants require $A\mathrm{\ne }C$, $A\mathrm{\ne }D$, $C\mathrm{\ne }D$, $B\mathrm{\ne }C$, $C\mathrm{\ne }E$, and $D\mathrm{\ne }E$. Basics must precede Advanced, so $A<B$. The Ethics trainer arrives at midday, so $E\mathrm{\ne }1$. These give seven binary edges and one unary rule; C has four neighbors.

The assignment $A=2,B=3,C=1,D=3,E=2$ satisfies every rule: each shared-participant pair differs, Basics precedes Advanced, and Ethics is not in slot 1. It is the only valid assignment among the $3^5=243$ candidates. Workshops B and D may both use slot 3 because no rule requires them to differ.

Choosing one variable per slot instead would make each value a subset of workshops, with up to $2^5=32$ possible subsets per slot. Rules would then have to inspect those sets and ensure every workshop occurs once. Choosing workshops as variables keeps the constraints simpler.

Express task timing and shared resources

In job-shop scheduling, use a start-time variable for each task. Prepare takes 20 minutes, Analyze 40, and Report 30. Start times are nonnegative integer minutes. The order and 120-minute deadline give

The earliest starts are 0, 20, and 60. Working backward from the deadline gives latest starts 30, 50, and 90. Thus the windows are $S_P\in [0,30]$, $S_A\in [20,50]$, and $S_R\in [60,90]$.

Two tasks sharing a machine need a disjunctive constraint: $S_X+d_X\le S_Y$ or $S_Y+d_Y\le S_X$. Either task may go first, but they cannot overlap. A simple precedence constraint would force one particular order and remove the other possibility.

Model assignments and puzzles

For three reports assigned to three reviewers, make each report a variable with reviewer values. Use Alldiff if every reviewer handles one report. A conflict of interest removes a reviewer from the relevant report's domain.

For n-queens, let $Q_i$ be the row of the queen in column $i$. One queen per column is built into the model. For every pair, require $Q_i\mathrm{\ne }{Q}_j$ and $\mathrm{\mid }{Q}_i-Q_j\mathrm{\mid }\mathrm{\ne }\mathrm{\mid }i-j\mathrm{\mid }$ to prevent row and diagonal attacks. For eight queens this reduces the candidate space from choosing 8 squares out of 64, $\mathrm{4,426,165,368}$ placements, to $8^8=\mathrm{16,777,216}$ assignments. There are 92 solutions.

For Sudoku, the 81 cell variables have domains 1–9. Given digits impose unary constraints, and 9 rows, 9 columns, and 9 boxes each impose Alldiff.

Choose the coarsest time units that still represent every permitted start. Hourly sessions need hourly choices; minute-by-minute domains would enlarge the work without adding a useful schedule. Finish by separating preferences from hard rules and checking a small case with a known answer.

Backtracking builds a partial assignment using depth-first search. It chooses one variable, tries a value, and continues until it finds a solution or must undo a choice. The search retains the useful earlier choices when a later one fails.

Branch on values, one variable at a time

Assigning A then B produces the same final assignment as assigning B then A. This commutativity means a CSP solver can choose one variable at each level and branch on its values. Allowing every variable order would produce $n!d^n$ leaves for only $d^n$ distinct complete assignments. For five variables with three values, that is 29,160 leaves instead of 243.

The next variable may depend on the current domains. What matters is choosing a single next variable at a node; the search does not need separate branches for all possible assignment orders.

Follow the recursive steps

1. If the assignment is complete and consistent, return it.
2. Choose an unassigned variable.
3. Try each domain value that is consistent with the current assignment.
4. Recurse after adding a value. If the recursive call fails, remove that assignment and try the next value.
5. If no value works, return failure to the caller.

Plain backtracking tests a constraint once all variables in its scope have values. With $A=1$ and B unassigned, $A<B$ has no completed pair to reject. Trying $B=1$ then fails immediately. Waiting until every variable is assigned would postpone this easy rejection.

Trace a dead end

Use the workshop rules: $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Take variables in order A, B, C, D, E and try values 1, 2, 3.

• Set $A=1$. Reject $B=1$ and choose $B=2$.
• Reject $C=1$ because of A and $C=2$ because of B; choose $C=3$.
• Reject $D=1$ because of A; choose $D=2$.
• E has no legal value: 1 is forbidden, 2 clashes with D, and 3 clashes with C.

Failure at E returns control to D. Its next value, 3, clashes with C. C has no later value, so control returns to B. Trying $B=3$ eventually produces another dead end under $A=1$. The search then tries $A=2$ and reaches $A=2,B=3,C=1,D=3,E=2$. With this order, plain backtracking tests 32 candidate values in total, including rejected ones.

What the method guarantees

Checking constraints and storing the model also have costs. The linear memory description concerns the search path, while propagation may store domains and undo records as well.

Chronological backtracking returns to the most recent choice. Faster variants improve four separate decisions: the next variable, the order of its values, the consequences inferred after a choice, and the earlier choice to revisit after failure. These improvements reduce practical work without changing what counts as a solution.

Good ordering can expose failure near the top of a search tree or preserve useful choices for later. Variable ordering and value ordering serve different purposes, so the best-looking direction differs between them.

Choose the most restricted variable

Minimum remaining values (MRV) selects the unassigned variable with the fewest currently legal values. It is also called the most-constrained-variable or fail-first heuristic. A nearly exhausted domain is likely to reveal a contradiction soon. If a domain is empty, the branch fails immediately.

Count current values after pruning, not the initial domain sizes. Without stored domains, a solver must determine which original values are still consistent with the assignment before applying MRV.

The degree heuristic breaks an MRV tie by choosing the variable with the most constraints on other unassigned variables. Such a choice affects more remaining decisions. Already assigned neighbors do not count toward this remaining degree. At the start of the Australia map, equal three-color domains tie, and SA's five neighbors give it the highest degree.

Keep options open when choosing a value

Least constraining value (LCV) tries the value that removes the fewest values from neighboring unassigned domains. Evaluating candidate values adds computation, but may avoid an expensive failed branch.

With WA red and NT green, SA can only be blue, while Q can be red or blue. Choosing Q blue would empty SA's domain. Choosing Q red removes red from NSW while preserving SA's blue. LCV therefore tries Q red.

Every variable must eventually receive a value, which makes an early test of a fragile variable useful. Only one value is needed to complete a first solution, which favors a value that leaves room for other decisions.

Combine ordering with forward checking

In the workshop schedule, apply $E\mathrm{\ne }1$ first. E has two values; A, B, C, and D each have three. MRV chooses E. Try $E=2$, and forward checking removes 2 from C and D.

C and D now tie with domains $\{1,3\}$. C has three unassigned neighbors, A, B, and D; D has two, A and C. Degree selects C. Choose $C=1$, leaving $D_D=\{3\}$ and $D_A=D_B=\{2,3\}$. MRV picks $D=3$, which forces $A=2$; the precedence rule then gives $B=3$. Five assignments find the solution with no backtracking. Fixed variable order with forward checking needs 12 assignments and reaches two dead ends.

Ordering preserves completeness because it changes the sequence of choices, without discarding legal branches. The worst-case search remains exponential. When enumerating every solution or proving infeasibility, all relevant values must eventually be explored, so LCV's early-success advantage is reduced. Its main use is finding a first solution sooner.

A dead end often has a smaller cause than the whole current assignment. Backjumping uses that cause to decide where to return, and constraint learning remembers a failure so it need not be rediscovered.

Find the choices that caused failure

On the Australia map, take the assignment order Q, NSW, V, T, SA. Let Q be red, NSW green, V blue, and T red. SA touches Q, NSW, and V, so all three colors are forbidden. Its conflict set is $\{Q,NSW,V\}$: earlier variables whose choices exclude its values.

Chronological backtracking would try changing T. Tasmania has no edge to SA, so changing its color cannot restore any option for SA. Backjumping returns to V, the most recently assigned member of the conflict set, and skips T.

A conflict set contains variables; a nogood records particular assignments. That distinction matters: another color for V may fix the failure, even though V is still a neighbor of SA.

Carry a conflict through earlier failures

Simple backjumping uses the current failure's direct conflict set. Conflict-directed backjumping carries information through several failed levels. When a failed variable X jumps to Y, Y absorbs X's conflict set with Y removed. If Y later exhausts all its values, its combined set identifies a cause further back in the assignment.

For example, use order WA, NSW, T, NT, Q, V, SA, and start with WA red, NSW red, T red. WA and NSW are not neighbors, so this partial assignment is consistent. Their choices remove red from NT, Q, and SA. Those three regions form a triangle, which cannot be colored using only green and blue.

No choice made for T changes that triangle. Conflict information can travel backward through the failed attempts and identify WA and NSW as the underlying cause. The search returns to NSW, the later of those two decisions, instead of spending time recoloring T.

Learn the failed combination

A solver can record $\{WA=\text{red},NSW=\text{red}\}$ as a nogood. Whenever both choices recur, the same triangle contradiction follows, so the branch can be rejected immediately. It would be incorrect to forbid WA red on its own: WA can be red in valid solutions with a different NSW color.

Learning adds a constraint or a cached forbidden combination. The learned condition must follow from the original constraints; failure caused merely by reaching a time limit supplies no such logical justification. A useful nogood keeps enough assignments to explain the impossibility without including unrelated choices.

Combine looking ahead and looking back

Forward checking and arc consistency remove unsupported values before a deep failure occurs. Backjumping diagnoses a failure after it occurs. Simple direct backjumping adds no pruning beyond what forward checking already detects, but conflict-directed methods can combine explanations of deeper failures. Learning preserves those explanations across later branches.

Forward checking asks what a new assignment immediately rules out for unassigned neighbors. It deletes incompatible values before search reaches those variables, making some dead ends visible several levels earlier.

Prune after an assignment

After choosing $X=x$, inspect each unassigned Y sharing a constraint with X. Delete every value in $D_Y$ that conflicts with the choice. An empty domain means the current branch has no completion, so backtrack immediately.

For $X\mathrm{\ne }Y$, assigning $X=2$ removes 2 from Y. For $X<Y$, assigning $X=2$ removes every Y value at most 2. The actual relation determines what is removed; forward checking is not limited to deleting equal values.

Pruning changes the current branch's domains. Keep an undo record, often called a trail, of every deletion caused by the choice. When that choice is undone, restore its deletions while retaining restrictions that belong to earlier choices. Copies of domains at each level provide another implementation.

Follow the workshop domains

Use slots 1–3 and rules $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$. Apply the unary rule to get $D_E=\{2,3\}$, then use fixed order A, B, C, D, E.

1. $A=1$ leaves B, C, and D with $\{2,3\}$.
2. $B=2$ leaves C with $\{3\}$.
3. $C=3$ leaves D and E each with $\{2\}$.
4. $D=2$ removes 2 from E, emptying its domain. Backtrack.

Restoring domains and trying $B=3$ forces C to 2. D and E both become 3, so assigning D empties E again. The search must change A. With $A=2$, it can reach $B=3,C=1,D=3,E=2$. This trace tries 12 values, compared with 32 candidate tests for plain backtracking in the same order.

Recognize the limit of one-step checking

After step 3, D and E both have the sole value 2 and must differ. Forward checking still has not checked that constraint: neither D nor E was newly assigned. It detects the failure only when D receives its value.

This is the central limit of forward checking. It tests the assigned variable against its unassigned neighbors, without propagating a neighbor's smaller domain onward. Arc consistency can follow those consequences between unassigned variables.

Use the maintained domains

MRV can now select the smallest remaining domain directly. A singleton domain often becomes the next choice; an empty domain signals failure without adding another assignment. Keeping domains up to date helps both inference and ordering.

For at most $n-1$ neighbors and at most $d$ values per neighbor, a forward-checking pass uses about $O(nd)$ binary checks, assuming a constant-time relation test. It removes only values incompatible with the current assignment, so backtracking stays complete. Forgetting to restore a deletion can make a later branch lose a valid solution; pruning an unrelated variable can do the same.

A value needs a compatible partner in every neighboring domain. Arc consistency makes that support requirement explicit and follows the effects of domain changes throughout a binary CSP.

Support has a direction

Node consistency first removes values forbidden by unary rules. For a binary constraint, the directed arc $X\to Y$ is consistent when every value in X has at least one compatible value in Y. That value in Y is a support. Revising the arc deletes unsupported values from its tail, X.

For $A<B$ with both domains $\{1,2,3\}$, revising $A\to B$ deletes 3 from A. Revising $B\to A$ deletes 1 from B. The resulting domains are $D_A=\{1,2\}$ and $D_B=\{2,3\}$. A surviving value may use a different support for each neighbor; the supports need not form one joint solution.

Run AC-3

AC-3 uses a queue of directed arcs:

1. Initially put every arc in the queue.
2. Remove $X\to Y$ and revise X using Y's domain.
3. If X becomes empty, stop with failure.
4. If X shrinks, add $Z\to X$ for each other neighbor Z of X, excluding Y.
5. Continue until the queue is empty.

A deletion in X can remove a support for Z, so the queue must point back into the changed domain. The arc from Y needs no immediate recheck: the deleted X values supported no value in Y, since none was compatible with Y in the first place. Nonempty closure domains are independent of processing order; different orders can reach failure at different empty domains.

Propagate a workshop decision

For the workshop rules $A\mathrm{\ne }C,A\mathrm{\ne }D,C\mathrm{\ne }D,B\mathrm{\ne }C,C\mathrm{\ne }E,D\mathrm{\ne }E,A<B,E\mathrm{\ne }1$, initial AC-3 removes 3 from A and 1 from B. It leaves C and D at $\{1,2,3\}$ and E at $\{2,3\}$.

Now decide $C=1$. The arc $A\to C$ removes 1 from A, leaving $A=2$. Revising B against A forces $B=3$. D differs from C and A, so $D=3$. E differs from D and cannot be 1, so $E=2$. Domain reductions have traveled beyond the original decision's immediate neighbors.

Maintaining arc consistency (MAC) applies this inference after every search decision. Starting from arc-consistent domains, restricting $X=x$ requires a queue of incoming arcs from its unassigned neighbors. Domain deletions must be restored when search undoes the branch.

Interpret the result and cost

A triangle with domains {red, blue} and inequalities on all three edges remains arc-consistent, yet has no solution. Each edge has supports separately, but the three choices cannot work together.

With $c$ binary constraints and maximum domain size $d$, AC-3 takes $O(c{d}^3)$ time: an arc revision checks up to $d^2$ pairs, and each arc can require up to $d$ rounds as its head loses values. MAC spends more per search node than forward checking, often in exchange for a much smaller search tree.

Separate pairwise supports can hide a group contradiction. Stronger consistency and specialized global propagation examine combinations that arc consistency misses, while numeric bounds can compress large domains into useful intervals.

Extend assignments to another variable

Path consistency examines triples. Every consistent assignment to two variables must have an extension to a third that agrees with both. In a triangle colored red or blue, X red and Y blue leave no value for Z. Path consistency removes that allowed pair and ultimately exposes infeasibility. It can remove tuples from relations, so it does more than delete individual domain values.

k-consistency requires every consistent assignment to any $k-1$ variables to extend to any additional variable. For binary CSPs, 1-consistency corresponds to node consistency, 2 to arc consistency, and 3 to path consistency. Strong k-consistency includes every level from 1 through k. With strong n-consistency on n variables and nonempty domains, any consistent partial assignment can be extended until it is a solution, without backtracking. Establishing this property has exponential worst-case time and memory costs.

Count values in Alldiff

Alldiff requires distinct values for all variables in its scope. If a group of m variables has only n distinct possible values and $m>n$, no assignment can satisfy it.

For three cells with domains $\{4,7\}$, pairwise inequalities are arc-consistent: each 4 has support 7 in every neighbor, and each 7 has support 4. The global count nevertheless fails because three different values are needed and only two exist.

If two cells both have domain $\{4,7\}$, they must use 4 and 7 between them. Those values can be removed from every other cell in that row. This naked pair reasoning uses a subset of the whole Alldiff scope. A simple global propagator can also process singleton variables repeatedly, remove their values elsewhere, and check whether too few distinct values remain. Stronger propagators recognize constrained subsets as well.

Tighten numeric bounds

Bounds propagation stores a domain by its minimum and maximum. Bounds consistency requires each endpoint to have a satisfying extension for each relevant constraint; it does not check every interior value.

For two buses carrying 100 people, let $B_1\in [0,50]$ and $B_2\in [0,70]$, with $B_1+B_2=100$. The second bus carries at most 70, forcing $B_1\ge 30$. The first carries at most 50, forcing $B_2\ge 50$. The tightened windows are $[30,50]$ and $[50,70]$.

For Prepare, Analyze, and Report taking 20, 40, and 30 minutes in that order, a 120-minute deadline gives latest starts 30, 50, and 90. Nonnegative starts give earliest starts 0, 20, and 60. Propagating forward and backward obtains these windows before a start time is chosen.

Choose useful strength

Each Sudoku cell has 20 distinct peers: 8 in its row, 8 in its column, and 4 additional cells in its box. Across 81 cells that gives $81\times 20\mathrm{/}2=810$ distinct unequal pairs. Global constraints preserve the same solutions as those pairs but can expose naked pairs and shortages sooner. Stronger inference costs more per pass; practical solvers balance that cost against the search it saves, often combining arc consistency with specialized global and bounds propagation.

Local search starts with a value for every variable, even when some constraints fail. Min-conflicts repairs this complete assignment by moving one conflicted variable to a value with as few conflicts as possible.

Choose a repair

1. Construct a complete assignment, randomly or greedily.
2. If no constraint is violated, return the solution.
3. Randomly choose a variable involved in a violated constraint.
4. Evaluate each of its domain values against the other variables, which stay fixed.
5. Choose a value with the fewest conflicts, breaking ties randomly, and repeat until success or a step limit.

A conflicted variable participates in at least one violated constraint. It is not necessarily the variable with the largest number of violations. Random choice among conflicted variables and tied values helps prevent a rigid repeated sequence.

Repair a 4-queens board

Use one queen per column, with row variables $Q_1,Q_2,Q_3,Q_4$. A pair conflicts if its rows are equal or its row difference equals its column difference. Begin with $(2,4,2,3)$. Columns 1 and 3 share row 2; columns 3 and 4 attack diagonally. The conflicted variables are Q1, Q3, and Q4.

Choose Q3 and evaluate rows while Q1, Q2, and Q4 remain fixed:

Row 1 yields $(2,4,1,3)$, a solution. If Q1 had been chosen instead, its counts for rows 1–4 would be 0, 1, 2, and 2. Moving it to row 1 gives $(1,4,2,3)$, leaving the Q3–Q4 diagonal conflict. A locally best repair can therefore lead to another incomplete repair process.

Count constraints involving the selected variable. Counting all violations in each resulting board gives the same ordering, because unrelated constraints contribute a constant to every candidate. It simply requires more work. Use one consistent conflict definition when comparing candidates.

Repair an existing schedule

When a trainer becomes unavailable, the current timetable is already a complete assignment. Min-conflicts can start there and move sessions until the new and existing constraints hold. A small change often needs few repairs, although one move can create new conflicts elsewhere. If retaining the old plan matters, attach an explicit cost to changing an assignment; minimizing violations alone does not minimize disruption.

Experiments with a good initial assignment have required relatively few repair steps even for a million queens. Larger boards still make each step more expensive. Min-conflicts has also been used for Hubble scheduling, with a reported reduction from about three weeks to about 10 minutes to schedule a week of observations.

Interpret search behavior

Many random CSP families change from mostly solvable to mostly unsolvable as the constraint-to-variable ratio rises. Near that transition, deciding how choices interact is often hardest. Loosely constrained problems can have many easily reached solutions. Highly constrained unsatisfiable problems may be quickly rejected by complete propagation-based solvers.

Reaching a min-conflicts step limit means no solution was found in that run. The problem may still be solvable. The method's practical strength comes from efficient repairs, including equal-score moves, despite solutions being a tiny fraction of all possible assignments.

Repair search can stop improving while conflicts remain. To continue, the solver needs a way to move through equal-score states or change which moves appear worthwhile. The required outcome also matters: a quick feasible repair and a proof of infeasibility demand different methods.

Move through a plateau

A local minimum has violations but no single-variable move that lowers their count. A plateau is a connected region of assignments with the same score. Downhill-only moves can become trapped; a sideways move changes the state without lowering the score.

For 4-queens, $(1,4,2,3)$ has one conflict between Q3 and Q4. With other queens fixed, Q3's counts for rows 1–4 are 1, 1, 3, and 2; Q4's are 2, 2, 1, and 2. Neither variable has an improving move.

Moving Q3 to row 1 gives $(1,4,1,3)$, still with one conflict, now Q1–Q3 sharing a row. In this new state Q1's counts are 1, 0, 3, and 1. Moving Q1 to row 2 produces $(2,4,1,3)$ and eliminates the conflict. The sideways move changed which improving moves were available.

Keep search moving

A tabu list is short-lived memory. It discourages returning immediately to a state just left. A restart explores a different region, while annealing can cross a higher-conflict region within the current run.

With constraint weighting, start each weight at 1 and score a state by the sum of the weights of its violated constraints. Choose a change that reduces this weighted score, then increase the weights of constraints that remain violated. Repeated failures become more costly, reshaping the search landscape. A zero weighted score still means that every positively weighted hard constraint is satisfied.

Choose the evidence you need

Local search is incomplete: it may miss an existing solution, and a finite unsuccessful run leaves infeasibility unresolved. Finite-domain backtracking with propagation is complete: eventually it finds a solution or exhausts every possible completion.

Use local search when a large, loosely constrained problem needs one feasible assignment or a fast repair. Backtracking with MRV and MAC is a strong choice for tight puzzles and whenever the task requires an infeasibility result. Runtime still depends on the instance; these are method choices grounded in their guarantees.

The workshop schedule has the unique solution $A=2,B=3,C=1,D=3,E=2$. Adding $C\mathrm{\ne }1$ eliminates it. Min-conflicts may try repairs until its limit, but only a complete search that exhausts the remaining cases establishes that the organizer must change a requirement, such as adding another slot.

A constraint graph can reveal smaller problems inside a large one. Independent components can be solved separately, and acyclic components admit a particularly efficient algorithm with a backward pruning pass and a forward assignment pass.

Split disconnected components

A connected component is independent when no constraint links its variables to another component. Solve each component, then combine one solution from each. If any component is unsatisfiable, the full CSP is unsatisfiable. In the Australia map, Tasmania is independent of the mainland.

With n variables divided into independent groups of size c, solving one full assignment takes work on the order of $O((n\mathrm{/}c)d^c)$ instead of $O(d^n)$. For 60 binary variables split into three groups of 20, separate exhaustive searches consider at most $3\times 2^{20}=\mathrm{3,145,728}$ assignments instead of about $1.15\times {10}^{18}$. Enumerating every combined solution would still require listing the combinations; the saving describes solving the component problems.

Order a tree from its root

A binary CSP is tree-structured when its constraint graph is acyclic. A connected tree has one path between each pair of variables; a forest contains separate trees. First apply unary restrictions. Choose any root and order variables so that every parent appears before its children.

Directed arc consistency in this order requires each earlier variable to have support in every later neighbor. On a tree, those later neighbors are its children. The direction of support is parent to child, even though the algorithm processes children before parents.

Prune backward, assign forward

1. Read the order backward, excluding the root. For each child, revise the arc from its parent to that child. Delete unsupported values from the parent's domain.
2. If a domain empties, report no solution.
3. Read the order forward. Choose any surviving root value, then give each child a value compatible with its assigned parent.

The child's descendants have already been processed when its parent is revised. A surviving parent value therefore has support in each child, and each child value already has support farther down. Different child branches have no edges connecting them, so those supports can be chosen independently. That is why the forward pass needs no backtracking.

Follow the workshop tree

Fix $C=1$ in the workshop schedule and remove 1 from the other workshops' domains. The remaining graph is the path B–A–D–E, with domains $\{2,3\}$ and constraints $A<B,A\mathrm{\ne }D,D\mathrm{\ne }E$.

Choose root A and order A, B, D, E. The backward pass revises $D\to E$, then $A\to D$, with no changes. Finally $A\to B$ removes 3 from A because B has no larger value. Assigning forward gives $A=2,B=3,D=3,E=2$. Restoring $C=1$ gives the complete timetable.

For n variables with maximum domain size d, the backward pass revises $n-1$ arcs at up to $O(d^2)$ each, yielding $O(n{d}^2)$ time. The guarantee depends on acyclicity. A cycle can connect separate child branches and invalidate the independence that made those local choices safe.

A graph with a few cycles may still be close enough to a tree to solve efficiently. Cutset conditioning assigns selected variables first; tree decomposition groups variables into overlapping parts. Both make the remaining coordination tree-shaped.

Condition on a cycle cutset

A cycle cutset is a set of variables whose removal leaves a tree or forest. Check every remaining cycle, not just the most visible one. For the Australia map, removing SA leaves the path WA–NT–Q–NSW–V plus isolated T. For the workshop graph, removing C leaves B–A–D–E.

For each assignment to the cutset that satisfies its internal constraints:

1. Remove incompatible values from the remaining domains.
2. Solve each remaining tree using backward pruning and forward assignment.
3. If all succeed, combine their assignments with the cutset values. Otherwise try another cutset assignment.

In the workshop problem, $C=1$ leaves a solvable tree. With $C=2$, A and B must come from $\{1,3\}$ and $A<B$ forces $A=1,B=3$. D must differ from both A and C, giving $D=3$. E cannot be 1 and must differ from C and D, leaving no value. With $C=3$, A and B must be 1 and 2; D must then be 2, again leaving E no value.

For cutset size c, there are at most $d^c$ assignments, each followed by a tree problem of cost $O((n-c)d^2)$. The total is $O(d^c(n-c)d^2)$. Small c makes this useful; it remains exponential in c. Finding a minimum cutset is NP-hard, but a valid nonminimum cutset still gives a correct procedure.

Join overlapping bags

A tree decomposition arranges sets of variables, called bags, in a tree. It must satisfy three conditions:

• Every variable appears in a bag.
• Every constraint's scope fits inside at least one bag.
• Bags containing any one variable form a connected part of the bag tree.

The third rule is the running-intersection property. If X appears at both ends of a bag path, it must appear throughout that path. Otherwise distant bags could choose inconsistent X values without any intervening agreement check.

Each bag's locally valid assignments become values of a mega-variable. Adjacent bags must agree on shared variables. The resulting tree coordinates the local solutions. For a triangle X–Y–Z–X plus edge Z–W, bags $\{X,Y,Z\}$ and $\{Z,W\}$ cover every edge and agree on Z.

The decomposition's tree width is its largest bag size minus 1. A graph's tree width is the minimum across valid decompositions. For width w, the standard CSP bound is $O(n{d}^{w+1})$. Fixed bounded width controls the exponent.

Remove value symmetry

When color names have no special meaning, permuting red, green, and blue preserves validity. The six mainland Australia solutions are six renamings of one pattern. Fixing the order NT before SA before WA in the color order red, green, blue keeps one representative. Such a symmetry-breaking constraint is valid only when the renaming preserves the original rules. A rule requiring a particular region to be red makes that color special and changes which permutations remain symmetries.