⏱️ 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
  1. What Constraint Propagation Means in a CSP
  2. AC-3: How It Prunes the Search Space Before Search Begins
  3. What This Means for You If You Build Assignment Systems
  4. What the arXiv Abstract Doesn’t Highlight
  5. AC-3 vs Other Ways to Propagate or Avoid Constraints
  6. When AC-3 Isn’t Enough
  7. Frequently Asked Questions
    1. Does AC-3 solve a Sudoku by itself?
    2. What is an arc in AC-3?
    3. Does it work for constraints involving more than two variables?
  8. 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"]
AC-3 only prunes binary constraints, the ones between pairs of variables. Foto de CDC en Unsplash

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:

TechniqueWhat it guaranteesWhen it appliesRelative cost
AC-3Arc consistency: every remaining value has support in each neighboring variableBefore search, as preprocessing, or repeated at every backtracking nodeLow compared to PC-2; only looks at pairs of variables
PC-2Path consistency: also validates triples of variables, stronger than AC-3CSPs where binary constraints alone can’t catch every inconsistencyHigher; checks combinations of three variables instead of two
Forward checkingChecks only the still-unassigned variables against the latest decision madeInside backtracking, at every search stepCheaper than AC-3 per step, but propagates less
OR-Tools CP-SATCombines propagation, search heuristics and parallelism in a complete solverIndustrial-scale CSPs with hundreds or thousands of variablesHigher, but you don’t have to implement it: it’s a ready-to-use library
Apt’s paper unifies AC-3, PC-2, DAC and DPC in 1999. Foto de Trnava University en Unsplash

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.

📬 Get new articles by email

We only email about big articles (1-2 a month).

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

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
Categories: Tech NewsTutorials

El Solitario Editorial

Article prepared by the El Solitario editorial team from cited sources, under the editorial responsibility of Luis Navarro. More details in "How we work".

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published. Required fields are marked *

You can include code inside <code>…</code> or, for several lines, <pre><code>…</code></pre>.

This site uses Akismet to reduce spam. Learn how your comment data is processed.