Constraint satisfaction: backtracking, constraint propagation and AC-3 on sudoku and a map of Czech regions

Variables, domains and constraints, the constraint graph, backtracking, the MRV and LCV heuristics, forward checking, AC-3 and min-conflicts — on colouring the regions of Czechia, sudoku and eight queens.

15 minutes Matěj Žalmánek 2026-10-15

Series AI basics Part 23 of 52

1. Map of artificial intelligence: what is what and how it all fits together
2. A brief history of artificial intelligence: from Turing to language models
3. Data, model, training, inference: the basic terms on a single example
4. How to read mathematical notation: symbols, indices, sums and quantifiers
5. Sets and relations: the building blocks of definitions in AI
6. Functions and mappings: why every AI model is a function
7. Logic and proofs: the rules AI reasons by
8. Graphs and trees: the structure that both search and neural networks stand on
9. Linear algebra for machine learning: vectors, matrices and why AI mostly multiplies
10. Derivatives, the gradient and the chain rule: how a model finds out which way to learn
11. Gradient descent: how a model learns
12. What probability is: from rolling dice to the Kolmogorov axioms
13. Conditional probability and Bayes’ theorem: how to update your estimate when you learn something new
14. Random variables and the cumulative distribution function: one function that tells you everything about a distribution
15. Probability density and probability mass functions: why a continuous variable has zero probability at a point
16. Expected value, variance and covariance: where a distribution lies, how wide it is and what goes with what
17. Overview of probability distributions: Bernoulli, binomial, Poisson, uniform, normal and exponential
18. Law of large numbers and central limit theorem: why averages behave so predictably
19. Statistics and parameter estimation: maximum likelihood, MAP and confidence intervals
20. Information theory: entropy, cross-entropy and KL divergence — where loss functions come from
21. State-space search: BFS, DFS, UCS and A* with animations
22. Games and adversaries: minimax, alpha-beta pruning and Monte Carlo tree search
23. Constraint satisfaction: backtracking, constraint propagation and AC-3 on sudoku and a map of Czech regions
24. Logic and knowledge systems: forward and backward chaining, resolution and expert systems
25. Planning: STRIPS, the blocks world, heuristics from relaxation and planning in AI agents
26. Local search and simulated annealing: a travelling salesman through the Czech regional capitals
27. Genetic algorithms: population, crossover, mutation and selection on a backpack for a hike
28. Evolution strategies and genetic programming: from the one-fifth rule to Kepler’s law
29. Ant colony optimization: how a pheromone trail finds a short path
30. Particle swarm optimisation: inertia, personal experience and the swarm’s experience
31. Neuroevolution: evolving the weights and shape of neural networks, and the NEAT algorithm
32. Fuzzy sets and membership functions: how to write down “somewhat warm”
33. Fuzzy logic and probability: why “somewhat warm” does not mean “probably warm”
34. Fuzzy logic: t-norms, implications and IF–THEN rules
35. Fuzzy control: Mamdani and Sugeno from a fan to a pole on a cart
36. Fuzzy clustering: the fuzzy c-means algorithm and points between clusters
37. Neuro-fuzzy systems (ANFIS): fuzzy rules that learn from data
38. Markov chains: the transition matrix, the stationary distribution and PageRank
39. Hidden Markov models: the Viterbi algorithm and the dishonest casino
40. Bayesian networks: why the grass is wet and what it means for the sprinkler
41. The Kalman filter: how to estimate where a car is and how fast it goes from imprecise measurements
42. Types of machine learning: supervised, unsupervised, semi-supervised and more
43. Prompts, context and RAG: how to give a model the right information
44. Variational autoencoders (VAE): new images from a continuous latent space
45. Generative adversarial networks (GAN): the forger versus the detective
46. Diffusion models: how pure noise becomes an image
47. Markov decision processes: states, actions, rewards and the Bellman equations
48. Q-learning and DQN: learning the value of actions, from a table to a neural network
49. Policy gradient and PPO: learning the policy directly
50. How an AI agent works: a language model in a loop with tools
51. Programming with AI agents: the task, tests and review
52. Evaluating and securing AI systems: how to measure and how to keep watch

Full series syllabus 52 of 83 topics published

A timetable in which no teacher teaches two classes at once. Sudoku. Placing components on a circuit board, hospital shifts, assigning aircraft to gates. What all these problems have in common is that we are not looking for a path, but for an assignment: giving each variable a value so that all the rules hold at once. Such a problem is called a constraint satisfaction problem, and unlike general search it has one big advantage — the rules are visible, so the algorithm can reason from them, not just try things.

It builds on the parts State-space search and Graphs and trees.

1. What a constraint satisfaction problem is

Definition — CSP

Let n ∈ ℕ, n ≥ 1. A constraint satisfaction problem (CSP) is a triple (X, D, C), where

1. X = {X₁, …, X_n} is a set of n distinct variables;
2. D = (D₁, …, D_n), where for every i = 1, …, n, D_i is a non-empty set — the domain of the variable X_i, i.e. the set of values X_i may take (in this part all domains are finite);
3. C is a finite set of constraints. Each constraint is a pair (S, R), where the scope S = (X_i1, …, X_ir) is an r-tuple of pairwise distinct variables from X (r ≥ 1) and the relation R ⊆ D_i1 × … × D_ir is the set of allowed combinations of their values.

The number r is the arity of the constraint. A constraint with r = 2 is binary; for example the constraint X₁ ≠ X₂ is the pair ((X₁, X₂), {(x, y) ∈ D₁ × D₂ : x ≠ y}). A CSP is binary if and only if all its constraints are binary. Where convenient, we will also treat the scope S as the set of its variables (S ⊆ X).

In words: a CSP consists of finitely many variables, a set of admissible values for each, and a list of rules, each of which enumerates the allowed combinations of values of several variables.

Definition — assignment and solution

Let (X, D, C) be a CSP. An assignment is a function a : dom(a) → D₁ ∪ … ∪ D_n, where dom(a) ⊆ X, such that

a(X_i) ∈ D_i for every X_i ∈ dom(a).

For a constraint (S, R) ∈ C with scope S = (X_i1, …, X_ir) ⊆ dom(a), let a|_S = (a(X_i1), …, a(X_ir)) denote the values of the variables of the scope. An assignment a is

1. consistent if and only if a|_S ∈ R for every constraint (S, R) ∈ C with S ⊆ dom(a);
2. complete if and only if dom(a) = X.

A solution of a CSP is an assignment that is complete and consistent. In words: a solution gives every variable a value and violates no constraint; a consistent assignment violates no constraint whose variables all have a value already.

An assignment a is thus a function from the set of variables dom(a) ⊆ X to their domains. The consistency condition from the definition can be written as a single expression:

a is consistent ⇔ ∀(S, R) ∈ C : S ⊆ dom(a) ⇒ a|_S ∈ R

∀(S, R) ∈ C

we go through every constraint — the scope S and the relation R; a single violated one is enough and the assignment is wrong

S ⊆ dom(a)

we judge only constraints whose variables all have a value already; a constraint with a free variable cannot be decided yet, and therefore a partial assignment cannot violate it

a|_S ∈ R

the values of the variables in the scope (the restriction of a to S) must form a combination the relation allows

Example — colouring the regions as a CSP

X = {KVK, ULK, …, MSK} are the 14 regions, each has the domain D_i = {1, 2, 3, 4} (colour numbers), and C contains one constraint ((X_i, X_j), ≠) for each of the 26 shared borders, i.e. the relation {(x, y) : x ≠ y} with twelve allowed pairs out of 16.

There are |D₁| · |D₂| · … · |D₁₄| = 4¹⁴ = 268,435,456 complete assignments. Among them we are looking for those that satisfy all 26 constraints.

Why not treat it as ordinary search? We could — the state is a partial assignment, the action is “give the next variable a value”. But search would look at the state as a black box. A CSP sees inside the box: it knows which rules hold and which variables they concern. All the tricks in this part rest on that.

2. The constraint graph: colouring a map of regions

A classic problem: colour a map so that no two neighbouring countries have the same colour. We take the fourteen regions of Czechia. The variables are the regions, the domain is a set of colours, and for each shared border there is the constraint “different colours”.

Definition — constraint graph

Let (X, D, C) be a binary CSP with variables X = {X₁, …, X_n}. Its constraint graph is the undirected graph (Graphs and trees) G = (V, E), where

V = X,   E = {{X_i, X_j} : i ≠ j ∧ ∃R : ((X_i, X_j), R) ∈ C}.

The variables X_i and X_j are thus joined by an edge if and only if there is a constraint whose scope consists of exactly these two variables (in either order — which is why it is enough to go through i, j both ways). The neighbours of the variable X_i in this graph are denoted N(X_i) = {X_j : {X_i, X_j} ∈ E}.

With four colours it goes smoothly. With three it does not work at all — and the graph shows why. The Central Bohemian Region borders Prague and seven regions that form a closed ring around it. A ring with an odd number of vertices needs three colours on its own (two would have to alternate regularly, and with an odd number that does not work out). The Central Bohemian Region borders all seven, so a fourth colour has to be left for it:

Theorem — three colours are not enough for the regions

Let G = (V, E) be a finite undirected graph and k ∈ ℕ, k ≥ 1. A colouring of the graph G with k colours is a function c : V → {1, …, k} such that

∀{u, v} ∈ E : c(u) ≠ c(v).

The chromatic number of the graph G is

χ(G) = min {k ∈ ℕ, k ≥ 1 : a colouring of G with k colours exists},

i.e. the smallest number of colours with which the vertices can be coloured so that every two neighbouring vertices have different colours (for a finite graph the minimum exists; |V| colours are always enough).

Lemma. Let G = (V, E) be a graph, m ≥ 3 odd and v₁, …, v_m ∈ V vertices forming a cycle, i.e. {v_i, v_i+1} ∈ E for i = 1, …, m − 1 and {v_m, v₁} ∈ E. Then there is no function c : {v₁, …, v_m} → {1, 2} that gives neighbours different colours on these edges. Proof: with two colours, the colours must alternate along the cycle; if v₁ has colour 1, then v_i has colour 1 exactly for odd i. Then v_m (odd m) has colour 1, just like its neighbour v₁. A contradiction. ∎

Theorem. Let G be the graph of regions: the vertices are the regions of Czechia (14 vertices) and {u, v} ∈ E if and only if the regions u and v share a border. Then χ(G) = 4. Proof: a colouring with four colours exists (figure above), so χ(G) ≤ 4. Suppose there were a colouring c with three colours. The ring of 7 regions around Central Bohemia is a cycle of odd length, so by the lemma c cannot make do with fewer than three colours on it — it uses all three. The Central Bohemian Region borders every region of the ring, and c(STČ) therefore differs from all three colours, which is impossible in {1, 2, 3}. A contradiction, so χ(G) ≥ 4. ∎

That four colours are enough for every map is the famous four colour theorem. It was proved by Appel and Haken in 1976 — as the first major mathematical theorem proved with the help of a computer, which checked almost two thousand cases.

3. Backtracking

Definition — backtracking

Backtracking is depth-first search that in each step assigns a value to one more variable. For an assignment a, a variable X_i ∉ dom(a) and a value v ∈ D_i, we write a ∪ {X_i ↦ v} for the assignment a extended by the value v of the variable X_i.

Input: a CSP (X, D, C) with finite domains and a consistent assignment a (empty at the start, dom(a) = ∅).
Output: a solution of the CSP that extends a, or “failure” if no such solution exists.

The procedure BT(a):

1. If dom(a) = X, return a (a complete consistent assignment is a solution).
2. Pick a variable X_i ∈ X ∖ dom(a).
3. For each value v ∈ D_i (in a fixed order): if a ∪ {X_i ↦ v} is consistent, call BT(a ∪ {X_i ↦ v}); if that call returns a solution, return it. An inconsistent value is not tried at all.
4. If no value led to a solution, return “failure” — the caller thereby goes back to the previous variable and tries its next value.

Termination: each nested call has one more assigned variable, so the depth of the recursion is at most n = |X|, and each call tries at most |D_i| values. The call tree is therefore finite and the algorithm always terminates.

Let d = max_i |D_i|. In the worst case backtracking goes through O(dⁿ) assignments. The general CSP is NP-hard, so in the worst case we cannot do better.

def backtracking(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment                     # everything has a value: a solution
    p = select_variable(assignment, csp)
    for h in csp.domains[p]:
        if consistent(p, h, assignment, csp):
            assignment[p] = h
            result = backtracking(assignment, csp)
            if result:
                return result
            del assignment[p]                 # dead end: go back
    return None

Why does “one variable per level” make a huge difference? General search would offer, in every state, all pairs (unassigned variable, value). The same complete assignment could then be put together in every possible order, and the tree would have

n! · dⁿ leaves instead of dⁿ

n!

the number of orders in which n variables can be assigned; the result does not depend on the order (an assignment is a set of pairs), so all but one are useless copies of the same work — backtracking throws them away by deciding about a single variable on each level

dⁿ

the number of different complete assignments: each of the n variables independently takes one of d values; this many leaves remain even if backtracking pruned nothing

On the regions with four colours, backtracking makes 14 assignments, one per region, and not once does it go back. With three colours it has to prove that no solution exists — and that means trying everything: 93 assignments before it gives up. The beginning of its run (the indentation is the depth in the tree, the colours are the numbers 1–3, ✗ means that no colour was left for the region):

KVK = 1
  ULK = 2
    PLK = 3
      PHA = 1
        STČ ✗
      PHA = 2
        STČ = 1
          LBK = 3
            JHČ = 2
              HKK = 2
                VYS = 3
                  PAK ✗
      PHA = 3
        STČ = 1
…

The very first dead end is instructive: the Ústí nad Labem Region, the Plzeň Region and Prague took all three colours from the Central Bohemian Region. Backtracking, however, goes back only to the last variable — to Prague — and recolours it, even though the real trouble lies in the odd ring. So Prague gets recoloured again and again during the run. This helpless marking time is called thrashing, and a smarter choice of variables cuts it down considerably.

4. Which variable and which value

The skeleton of backtracking leaves two questions open: which variable to take next and in what order to try its values. The answers matter more than it might seem.

Definition — MRV, degree, LCV

Let (X, D, C) be a binary CSP with constraint graph G and neighbours N(·), let a be a consistent assignment and U = X ∖ dom(a) ≠ ∅ the set of unassigned variables. For X_i ∈ U, denote the remaining values

D′_i = {v ∈ D_i : a ∪ {X_i ↦ v} is consistent}.

1. MRV (minimum remaining values) picks as the next variable one of M = {X_i ∈ U : |D′_i| = min_{Xk ∈ U} |D′_k|}, i.e. the variable with the fewest values that are not yet in conflict with the assignment.
2. The degree heuristic breaks a tie: from M it picks the variable X_i with the largest |N(X_i) ∩ U|, i.e. with the most constraints with variables not yet assigned.
3. LCV (least constraining value): for the chosen X_i, v ∈ D′_i and every X_j ∈ N(X_i) ∩ U, let D″_j(v) = {w ∈ D′_j : a ∪ {X_i ↦ v, X_j ↦ w} is consistent} and loss(v) = ∑_{Xj ∈ N(Xi) ∩ U} |D′_j ∖ D″_j(v)|. LCV tries the values v ∈ D′_i in ascending order of loss(v).

In words: MRV takes the variable with the fewest options left, the degree heuristic on a tie the one that constrains the others the most, and LCV first tries the value that crosses out the fewest options for its neighbours. For the constraint ≠ we have D′_j ∖ D″_j(v) = {v} ∩ D′_j, so the loss is simply the number of unassigned neighbours that still have v left.

For three colours on the regions, MRV together with forward checking from the next section reduces the number of assignments from 93 to 45 — it starts with the region that has the fewest colours left, and finds the contradiction twice as fast.

On an empty map all regions have three colours each and MRV does not decide. The degree heuristic would then take the Central Bohemian Region, which has 8 neighbours — the most of all; its colour immediately constrains eight other regions. Our implementation simply takes, on a tie, the first region in order from the west, i.e. the Karlovy Vary Region.

5. Forward checking

Definition — forward checking

Let (X, D, C) be a binary CSP in which every two variables are joined by at most one constraint (several constraints between the same pair can be replaced by one with the intersection of the relations). For a constraint ((X_i, X_j), R) ∈ C we write R_ij = R and R_ji = {(y, x) : (x, y) ∈ R}.

Let a be a consistent assignment, D₁, …, D_n the current (possibly already narrowed) domains, X_i ∉ dom(a) and v ∈ D_i. Forward checking after the assignment X_i ↦ v sets D_i ← {v} and, for every variable X_j ∈ N(X_i) ∖ dom(a),

D_j ← {w ∈ D_j : (v, w) ∈ R_ij};

it does not change the other domains. If after narrowing D_j = ∅ for some j, the assignment X_i ↦ v is withdrawn immediately — it cannot be extended to a solution, because X_j would have no admissible value.

In words: after every assignment, the values incompatible with the assigned value are crossed out of all unassigned neighbours, and an empty domain means an immediate step back.

def forward_check(csp, domains, assignment, p, h):
    new = dict(domains)
    new[p] = [h]
    for s in csp.neighbors[p]:
        if s in assignment:
            continue
        new[s] = [x for x in new[s] if csp.allowed(p, h, s, x)]
        if not new[s]:
            return None                       # the neighbour has nothing left: withdraw p = h
    return new

Backtracking then passes the narrowed new domains into the recursion instead of the original ones, and MRV only compares their lengths. This is what the beginning of the run with forward checking and MRV looks like on the regions with three colours. The right-hand column shows the unassigned regions with the smallest domain — MRV picks the first of them:

After the first three steps the Central Bohemian Region has a single colour left, so it gets its turn before Prague. Every further region chosen has only one option left, and in the eighth step forward checking finds that the Pardubice Region has nothing left — the contradiction is uncovered without the Pardubice Region even being tried. The whole ring is thus forced by itself; a free decision was made only for the first two regions.

The difference shows on the sudoku below. Plain backtracking, square by square along the rows, needs over 14 million assignments. With forward checking it takes 11,400. And when we add MRV to it, it drops to 81 — 30 given numbers and 51 filled in, without a single backtrack.

6. Arc consistency and AC-3

Forward checking looks only one step ahead: at the neighbours of the variable we have just assigned. It can be done more thoroughly — crossing out even between variables that do not have a value yet.

Definition — arc consistency

Let (X, D, C) be a binary CSP with the notation R_ij from the definition of forward checking, and let X_i, X_j ∈ X be variables joined by a constraint, i.e. {X_i, X_j} ∈ E. The variable X_i is arc-consistent with respect to X_j if and only if

∀x ∈ D_i ∃y ∈ D_j : (x, y) ∈ R_ij.

An ordered pair (X_i, X_j) with {X_i, X_j} ∈ E is called a directed edge; every edge of the constraint graph gives two. A CSP is arc-consistent if and only if X_i is arc-consistent with respect to X_j for every directed edge (X_i, X_j). In words: every value in the domain of every variable has, at every neighbour, at least one value with which it satisfies the constraint.

Making one directed edge consistent (the operation revise in the code below) means keeping only the values that have a partner:

D_i ← { x ∈ D_i : ∃y ∈ D_j : (x, y) ∈ R_ij }

D_i ←

we overwrite the domain in place; only the domain of X_i shrinks, the edge is directed — the opposite direction (X_j, X_i) is a separate item in the queue

x ∈ D_i

we judge each value separately; we add nothing new, so the domain can only shrink — which is why AC-3 terminates

∃y ∈ D_j

one partner in the neighbour’s current domain is enough; we ask whether x can survive, not how

(x, y) ∈ R_ij

the pair must satisfy the constraint between X_i and X_j — for map colouring simply x ≠ y

Algorithm — AC-3

Input: a binary CSP (X, D, C) with finite domains and constraint graph G = (X, E).
Output: “false” if some domain was left empty (the CSP then has no solution); otherwise “true” and domains narrowed so that the CSP is arc-consistent and has the same set of solutions as on input.

1. Put all directed edges (X_i, X_j), {X_i, X_j} ∈ E, into a queue Q.
2. If Q is empty, stop with the result “true”.
3. Take an edge (X_i, X_j) out of Q and perform D_i ← {x ∈ D_i : ∃y ∈ D_j : (x, y) ∈ R_ij} (breakdown above).
4. If D_i has shrunk: if D_i = ∅, stop with the result “false”; otherwise put into Q all edges (X_k, X_i) for X_k ∈ N(X_i), X_k ≠ X_j — their values may have just lost a partner.
5. Continue with step 2.

Termination: edges return to the queue only when some domain shrinks; the domains are finite and never grow, so after finitely many steps the queue is empty.

For c binary constraints and domains of size at most d, AC-3 takes O(c · d³).

from collections import deque

def ac3(csp):
    queue = deque((xi, xj) for xi in csp.variables for xj in csp.neighbors[xi])
    while queue:
        xi, xj = queue.popleft()
        if revise(csp, xi, xj):
            if not csp.domains[xi]:
                return False                  # empty domain: no solution exists
            for xk in csp.neighbors[xi]:
                if xk != xj:
                    queue.append((xk, xi))
    return True

def revise(csp, xi, xj):
    before = len(csp.domains[xi])
    csp.domains[xi] = [x for x in csp.domains[xi]
                       if any(csp.allowed(xi, x, xj, y) for y in csp.domains[xj])]
    return len(csp.domains[xi]) < before

AC-3 step by step

Three variables X, Y, Z, every two of which must differ, and the domains D_X = {1}, D_Y = {1, 2}, D_Z = {1, 2, 3}. The queue starts with six directed edges; a row of the table is one removal from the queue and one narrowing D_i ← by the formula above (the column “domain after” has the colour of the same term):

In step 3 Y loses the one, because its only possible partner at X is exactly 1. This puts the edge (Z, Y) back into the queue — the value 2 in Z had its partner in exactly that crossed-out one. The value 2 is, however, crossed out of Z already by the original edge (Z, Y) in step 6; the returned copy in step 7 finds nothing. (Our queue is not a set, so an edge can be in it twice — that changes nothing about the result.) After 9 steps the queue is empty and the domains are {1}, {2}, {3}: a solution without a single attempt.

O( 2c · d · d² ) = O(c · d³)

2c

every binary constraint gives two directed edges, and each of them has to be checked

d

how many times at most the edge (X_k, X_i) returns to the queue: only when D_i shrinks, and that happens at most d times

d²

the cost of one check of an edge: for each of at most d values x we look for a partner among at most d values y

7. Sudoku: propagation in practice

Sudoku is a textbook CSP: 81 variables, domains {1, …, 9} and the constraint “different values” for every pair of squares in the same row, column or 3 × 3 box. Each square thus has 20 neighbours in the constraint graph.

Example — sudoku in numbers

Neighbours of a square: 8 others in the row + 8 in the column + 4 squares of the 3 × 3 box that lie in neither its row nor its column (the remaining 4 we have already counted) = 20.

Constraints: 81 · 20 = 1620 directed edges; every pair of squares is in there twice, so there are 1620/2 = 810 binary constraints.

Size of the domains at the start: 30 given squares with the domain {given number} and 51 empty ones with nine values: 30 · 1 + 51 · 9 = 489 values. At the end each of the 81 squares has one value, so AC-3 crossed out 489 − 81 = 408 values. In doing so it took 9,372 edges from the queue.

Brute force: trying every way of filling in the empty squares means 9⁵¹ ≈ 4.6 · 10⁴⁸ assignments (dⁿ with d = 9 and n = 51 empty squares; colour as in the formula in the Backtracking section). Thanks to the consistency check, backtracking makes “only” fourteen million of them.

Let us run AC-3 alone on a puzzle with 30 given numbers, without a single blind assignment. It crosses out 408 values — and each of the 51 empty squares is left with exactly one. The sudoku is solved by pure reasoning:

That is how it goes with easy sudokus; with harder ones propagation gets stuck somewhere and search takes over — backtracking that runs propagation again after each assignment. This combination (maintaining arc consistency, MAC) is the basis of most real solvers. For comparison, on the same puzzle:

From fourteen million to zero. Brute force and clever reasoning solve the same problem — only one of them reads the rules.

8. Local search: min-conflicts

A completely different strategy: instead of building the solution piece by piece, start with a complete assignment that violates plenty of constraints, and gradually repair it. It is the local search from the part on search, only the objective function is the number of violated constraints.

Algorithm — min-conflicts

Input: a CSP (X, D, C) with finite domains and a maximum number of steps k_max ∈ ℕ.
Output: a solution of the CSP, or “failure”.

For a complete assignment a, a variable X_i and a value v ∈ D_i, let conflicts(X_i, v) be the number of constraints (S, R) ∈ C with X_i ∈ S violated by the assignment obtained from a by changing the value of X_i to v. The variable X_i is in conflict if and only if conflicts(X_i, a(X_i)) > 0.

1. Choose a random complete assignment a (a(X_i) ∈ D_i for all i).
2. Repeat at most k_max times: if a is consistent (no variable is in conflict), return a. Otherwise pick a random variable X_i in conflict and set a(X_i) ← v, where v ∈ D_i has the smallest conflicts(X_i, v) (ties broken randomly) — i.e. the value with which it violates the fewest constraints.
3. After k_max steps without a solution, return “failure”.

Termination: after k_max steps at the latest. The algorithm is not complete: “failure” does not mean that no solution exists.

The classic test is the n-queens problem: place n chess queens on an n × n board so that no two attack each other. The variable is the row of the queen in each column. For eight queens our run started with six attacking pairs and finished after 8 steps:

What exactly does the algorithm minimise? The queen in column i stands in row r_i. The number of conflicts if it were placed in row v is

conflicts(i, v) = ∑_{j ≠ i} [ r_j = v ∨ |r_j − v| = |j − i| ]

conflicts(i, v)

the cost of the move “queen from column i to row v”; min-conflicts picks the v for which it is smallest

∑_{j ≠ i} [ … ]

we add up over all the other queens; the square bracket is 1 when the condition holds, otherwise 0 — we count violated constraints

r_j = v

queen j stands in the same row; it cannot share a column, the choice of variables (one queen per column) already rules that out

|r_j − v| = |j − i|

the queens lie on the same diagonal: the shift in rows equals the shift in columns

def min_conflicts(csp, max_steps):
    a = random_complete_assignment(csp)
    for _ in range(max_steps):
        in_conflict = [x for x in csp.variables if conflicts(csp, a, x, a[x]) > 0]
        if not in_conflict:
            return a                          # nothing is grinding: a solution
        x = random.choice(in_conflict)
        costs = {v: conflicts(csp, a, x, v) for v in csp.domains[x]}
        fewest = min(costs.values())
        a[x] = random.choice([v for v in costs if costs[v] == fewest])
    return None                               # patience ran out

Our run move by move. We number both columns and rows 1–8 (row 1 at the top); the “costs” are the values conflicts(i, v) for v = 1, …, 8, and the smallest of them is in bold (their colour corresponds to the term conflicts(i, v) in the formula above). At the start the queens stood in rows 5 1 6 2 5 1 1 8.

In step 6 the algorithm drew, out of two equally good rows, the one in which the queen already stood — the move changed nothing. In steps 4 to 7 the smallest cost is 1; only in the eighth is a row with zero found in the drawn column.

Notice the middle steps: the number of conflicts stays at one for four steps — the algorithm moves queens “sideways” along a plateau until it finds a move that removes the conflict. What is surprising is how well it scales: min-conflicts solves a million queens in roughly fifty steps on average. The same method was used to schedule observations for the Hubble Space Telescope (both are described by Minton, Johnston, Philips and Laird, 1992).

9. Constraints in practice

• Timetables and planning. School timetables, shifts, classroom allocation and production plans are specified as variables, domains and constraints. Solvers such as Google OR-Tools combine propagation, search and local improvement.
• SAT solvers solve CSPs in which every variable is true/false. They verify chip designs, look for bugs in software, and package managers (for example in Linux) use them to put together versions of libraries that work with each other.
• Compilers allocate a program’s variables to processor registers by graph colouring: two variables that live at the same time must not share a register — exactly like neighbouring regions a colour.
• Configurators in online shops and manufacturing make sure the selected components go together.
• AI agents and language models often do not excel at CSPs: for a sudoku or a timetable a solver is more reliable. A good agent therefore does not think the problem through “in its head” — it translates it into variables and constraints and calls a tool on it.

10. Summary

• A CSP is a triple (X, D, C): variables, domains and constraints. A solution is a complete assignment that violates no constraint.
• Backtracking assigns variables one after another and backs out of dead ends; in the worst case it is exponential.
• The MRV and LCV heuristics choose the hardest variable and the most accommodating value; forward checking uncovers a dead end one step earlier.
• AC-3 propagates crossing out through the constraint graph until every value has a partner; it solves an easy sudoku entirely without search.
• Min-conflicts repairs a complete assignment and copes even with huge problems, such as a million queens.

Want to get hands-on? Have an AI agent write a sudoku solver with backtracking, and then add forward checking, MRV and AC-3 to it — and count how many assignments disappear.

Do you see it differently? Write to support@coden-app.com.