⏱️ Reading time: 8 min
An empty Sudoku grid looks like a brute-force problem: try every number in every cell until something fits. But before guessing anything, you can rule out many of the options just by looking at the constraints between neighboring cells. That early filtering is called constraint propagation, and the algorithm that popularized it in classic artificial intelligence is AC-3, one of the algorithms that researcher Krzysztof Apt unified into a single formal framework in a 1999 paper still used as a reference (arxiv.org/abs/cs/9909009v1).
📑 En este artículo
- What Constraint Propagation Means in a CSP
- AC-3: How It Prunes the Search Space Before Search Begins
- What This Means for You If You Build Assignment Systems
- What the arXiv Abstract Doesn’t Highlight
- AC-3 vs Other Ways to Propagate or Avoid Constraints
- When AC-3 Isn’t Enough
- Frequently Asked Questions
- References
What Constraint Propagation Means in a CSP
A CSP (constraint satisfaction problem) has three parts: a set of variables, a domain of possible values for each one, and a set of constraints stating which combinations of values are valid. Sudoku is a CSP: each empty cell is a variable, its domain is the numbers 1 through 9 that could still go there, and the constraint is that no row, column or box repeats a number. An exam schedule is another typical CSP: each course is a variable, the domain is the available time slots, and the constraint is that no professor gives two exams at the same time.
Solving a CSP by brute force means trying combinations until one satisfies every constraint. That works for small problems, but the search space grows fast: each variable added multiplies the possible combinations by the size of its domain. Constraint propagation attacks the problem earlier: it uses the constraints themselves to eliminate values that could never be part of a solution, without having to try them.
AC-3: How It Prunes the Search Space Before Search Begins
AC-3 works on pairs of variables connected by a constraint, which it calls arcs, the same notion Apt uses to formalize the algorithm within his generic commutativity framework (arxiv.org/abs/cs/9909009v1). For each arc (Xi, Xj), it checks whether every value left in Xi’s domain has at least one compatible value in Xj’s domain. If it finds a value of Xi with no possible match in Xj, it removes that value from Xi’s domain: that value could never be part of a valid solution.
The algorithm keeps a queue of all the arcs still pending review. Every time it checks an arc and removes at least one value, it puts back in the queue every arc that points to the variable that just changed, because that reduction can open up new eliminations elsewhere in the constraint graph. The process ends when the queue is empty: at that point, every value surviving in every domain has at least one compatible value in every neighboring variable. That state is called arc consistency. The same queue-and-requeue logic is what the open source library python-constraint implements (github.com/python-constraint/python-constraint), the library already cited in References.
A small example with two Sudoku cells in the same row makes this concrete. If cell A has domain {2, 5} because the rest of the numbers were already ruled out by other constraints, and cell B has domain {2, 5, 7}, the constraint that A and B cannot repeat a number still allows several combinations: there is nothing to prune yet. But if a separate constraint reduces A’s domain to a single value, {5}, then the arc (B, A) gets reviewed again and 5 is removed from B’s domain, because B can no longer be 5 without repeating A’s number. That removal from B can, in turn, trigger a review of other arcs involving B. AC-3 never decides a final value on its own: it only reduces the domains until nothing more can be ruled out, and that smaller result is what the search algorithm (typically backtracking) receives to finish choosing the values.
flowchart TD
A["Queue with all arcs"] --> B["Pop an arc (Xi, Xj)"]
B --> C{"Any value of Xi without support in Xj?"}
C -- "Yes" --> D["Remove that value from Xi's domain"]
D --> E["Re-enqueue the arcs pointing to Xi"]
E --> B
C -- "No" --> F{"Any arc left in the queue?"}
F -- "Yes" --> B
F -- "No" --> G["Arc consistency reached"]
What This Means for You If You Build Assignment Systems
If you work in backend, building a product configurator, an academic scheduler or a shift assigner, the practical decision is where to place the propagation: before the search, as an input filter, or inside each step of the backtracking, so that every partial decision immediately prunes the domains of the variables still to be assigned. Implementing AC-3 by hand makes sense as a learning exercise or for a small, bounded CSP with few variables and clear binary constraints, like the Sudoku example above.
For a real-scale problem (hundreds of variables, constraints spanning more than two variables, compute time limits), it’s better to use a mature solver than to rewrite AC-3: Google offers CP-SAT inside OR-Tools, a solver that combines SAT and CP methods for constraint satisfaction problems (developers.google.com/optimization/cp), and it already ships with constraint propagation, search heuristics and parallelism built in.
What the arXiv Abstract Doesn’t Highlight
Apt’s paper abstract describes AC-3 as one particular case, not the central topic. Its stated goal is more ambitious: using the notions of commutativity and semi-commutativity, the paper shows that AC-3 and three other classic propagation algorithms (PC-2, DAC and DPC) are instances of a single generic algorithm (arxiv.org/abs/cs/9909009v1). In other words, the same idea of pulling arcs from a queue and checking them works for arc consistency (AC-3), path consistency (PC-2) and the directional versions DAC and DPC, changing only which property gets verified at each check.
AC-3 vs Other Ways to Propagate or Avoid Constraints
AC-3 is not the only way to prune a search space before or during backtracking. Three well-known alternatives solve the same problem with different trade-offs:
| Technique | What it guarantees | When it applies | Relative cost |
|---|---|---|---|
| AC-3 | Arc consistency: every remaining value has support in each neighboring variable | Before search, as preprocessing, or repeated at every backtracking node | Low compared to PC-2; only looks at pairs of variables |
| PC-2 | Path consistency: also validates triples of variables, stronger than AC-3 | CSPs where binary constraints alone can’t catch every inconsistency | Higher; checks combinations of three variables instead of two |
| Forward checking | Checks only the still-unassigned variables against the latest decision made | Inside backtracking, at every search step | Cheaper than AC-3 per step, but propagates less |
| OR-Tools CP-SAT | Combines propagation, search heuristics and parallelism in a complete solver | Industrial-scale CSPs with hundreds or thousands of variables | Higher, but you don’t have to implement it: it’s a ready-to-use library |
When AC-3 Isn’t Enough
AC-3 only understands binary constraints, the ones connecting exactly two variables. A constraint like requiring all nine numbers in a Sudoku box to be distinct involves nine variables at once, not a pair, so using it with AC-3 means decomposing it first into binary constraints between every pair of cells in the box. That decomposition is straightforward for Sudoku, but in CSPs with constraints that genuinely span more than two variables, as in much of shared-resource allocation, it complicates the implementation or loses part of the original information.
It also doesn’t solve the CSP by itself. Reaching arc consistency reduces the domains, but it doesn’t guarantee a complete valid assignment exists: a search algorithm, usually backtracking, is still needed to finish choosing one value per variable. And the more variables and values per domain the problem has, the more arcs need checking and the more often each check repeats as domains get updated, so the benefit of applying AC-3 depends on how much it actually prunes: in a CSP with very loose constraints, the time it takes to run can outweigh the little it reduces.
Frequently Asked Questions
Does AC-3 solve a Sudoku by itself?
No. It reduces the domains of the empty cells by removing numbers that no longer have any valid place, but it usually leaves more than one possible value per cell. The final choice of which number goes in each cell is made by a search algorithm, like backtracking, using the domains AC-3 already pruned.
What is an arc in AC-3?
An ordered pair of variables connected by a constraint, for example (Cell A, Cell B). The algorithm checks each arc in one direction: checking (A, B) verifies that every value of A has a compatible match in B, and (B, A) has to be checked separately for the reverse direction.
Does it work for constraints involving more than two variables?
Not directly. AC-3 works with binary constraints. To use it with constraints over three or more variables, they have to be decomposed first into equivalent binary constraints, which isn’t always simple or free in compute time.
References
- The Rough Guide to Constraint Propagation (Apt, 1999): formalizes AC-3, PC-2, DAC and DPC as instances of a single generic propagation algorithm.
- Apt, cs.AI/9811024: the earlier paper by the same author that The Rough Guide to Constraint Propagation extends and simplifies.
- Google OR-Tools, CP-SAT Solver: official documentation for the constraint solver Google maintains, focused on feasibility and constraints rather than optimization.
- python-constraint: open source Python library implementing AC-3 and backtracking for small to medium CSPs.
Featured image: Foto de Bozhin Karaivanov en Unsplash
How each article is made (sources, testing and editorial criteria): How we work.
Did it work for you? Got a different error? Say so below: questions get answered and help the next reader.
Leave a comment
0 Comments