AC-3 Constraint Propagation

A constraint satisfaction problem (CSP) consists of variables, their possible values, and constraints. AC-3, Arc Consistency Algorithm 3, removes values that have no supporting value in a neighboring domain.

The variables here are a, b, c, and d, each initially a digit from 0 through 9. Propagation reduces domains; it does not necessarily choose one complete assignment. Run the cells in order; only Python’s standard library is needed.

Equations and Queue

The four equations form a cycle. A queued triple (xi, xj, value) means: revise the domain of xi using the equation xi + xj = value. The deque supports removing the oldest pending arc and appending arcs that need another check.

# a + b = 3
# b + c = 4
# c + d = 2
# d + a = 1

# using AC-3 to solve it
# the domains of a, b, c, d are all 0~9 digits
# the constraints are the four equations above

from collections import deque
from typing import List, Tuple

Display the Current Domains

This helper prints each variable’s remaining candidates. It does not change domains and does not imply that arbitrary choices from the four lists can be combined into a solution.

def print_domains(domains: dict):
    print("a: {}".format(domains['a']))
    print("b: {}".format(domains['b']))
    print("c: {}".format(domains['c']))
    print("d: {}".format(domains['d']))

Process Pending Arcs

The loop calls revise on one directed arc. If a domain shrinks, incoming arcs from other neighbors are queued again because values they previously supported may now have lost their support.

An empty domain proves inconsistency and returns False. An empty queue means no listed arc currently needs revision, so the function returns True. It does not mean all domains are singletons.

The next cell defines revise. Python resolves that name when ac3 is called, so define all helpers before running solve.

def ac3(constraints: List[Tuple[str, str, int]], domains: dict):
    queue = deque(constraints)
    while queue:
        (xi, xj, value) = queue.popleft()
        if revise(domains, xi, xj, value):
            print(f'queue: {queue}')
            print_domains(domains)            
            if not domains[xi]:
                return False
            for xk, xl, this_value in constraints:
                if xl == xi and xk != xj:
                    # print the constraints that will be added to the queue
                    print(f'adding {xk}+{xl}={this_value}')
                    queue.append((xk, xi, this_value))
    return True

Remove Unsupported Values

For every candidate x in the first domain, any(…) asks whether at least one y in the second domain satisfies the equation. If not, x is marked for deletion.

The function collects deletions first, then removes them. Modifying a list while iterating over it could skip candidates. Its Boolean return value reports whether the domain changed, not whether the whole CSP is solved.

def revise(domains: dict, xi: str, xj: str, value: int):
    revised = False
    print(f'revising {xi}+{xj}={value}')
    del_x = []
    for x in domains[xi]:
        if not any(x + y == value for y in domains[xj]):
            del_x.append(x)
            revised = True
    for x in del_x:
        domains[xi].remove(x)
    return revised

Initialize and Propagate

The wrapper creates fresh digit domains, runs propagation, and returns either the reduced domains or None. This implementation initializes variables from the first position of each constraint tuple; the example includes every variable there.

def solve(constraints: List[Tuple[str, str, int]]):
    domains = {x: list(range(10)) for x in set(x for x, _, _ in constraints)}
    if ac3(constraints, domains):
        return domains
    return None

Supply the Constraints

Each tuple describes a sum equation. Although the equation is symmetric, a revision is directional. The original example supplies one direction per equation. For the standard full AC-3 treatment, include each reverse arc as well, such as (‘b’, ‘a’, 3) for (‘a’, ‘b’, 3).

Do not infer bidirectional consistency merely because the arithmetic equation is symmetric: the queue processes only the directions it receives.

constraints = [
    ('a', 'b', 3),
    ('b', 'c', 4),
    ('c', 'd', 2),
    ('d', 'a', 1),
]

Follow the Domain Changes

The trace prints each revision attempt. When something is removed, it also prints the remaining queue and the updated domains. Requeued arcs reflect consequences of a domain change, not new constraints.

For this example, the final candidate sets are a and d in {0, 1}, b in {2, 3}, and c in {1, 2}. There are still multiple possibilities; they are not independent choices.

domains = solve(constraints)
if domains:
    print('final result of domains:')
    print_domains(domains)
else:
    print('No solution')
revising a+b=3
queue: deque([('b', 'c', 4), ('c', 'd', 2), ('d', 'a', 1)])
a: [0, 1, 2, 3]
b: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
c: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
d: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
adding d+a=1
revising b+c=4
queue: deque([('c', 'd', 2), ('d', 'a', 1), ('d', 'a', 1)])
a: [0, 1, 2, 3]
b: [0, 1, 2, 3, 4]
c: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
d: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
adding a+b=3
revising c+d=2
queue: deque([('d', 'a', 1), ('d', 'a', 1), ('a', 'b', 3)])
a: [0, 1, 2, 3]
b: [0, 1, 2, 3, 4]
c: [0, 1, 2]
d: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
adding b+c=4
revising d+a=1
queue: deque([('d', 'a', 1), ('a', 'b', 3), ('b', 'c', 4)])
a: [0, 1, 2, 3]
b: [0, 1, 2, 3, 4]
c: [0, 1, 2]
d: [0, 1]
adding c+d=2
revising d+a=1
revising a+b=3
revising b+c=4
queue: deque([('c', 'd', 2)])
a: [0, 1, 2, 3]
b: [2, 3, 4]
c: [0, 1, 2]
d: [0, 1]
adding a+b=3
revising c+d=2
queue: deque([('a', 'b', 3)])
a: [0, 1, 2, 3]
b: [2, 3, 4]
c: [1, 2]
d: [0, 1]
adding b+c=4
revising a+b=3
queue: deque([('b', 'c', 4)])
a: [0, 1]
b: [2, 3, 4]
c: [1, 2]
d: [0, 1]
adding d+a=1
revising b+c=4
queue: deque([('d', 'a', 1)])
a: [0, 1]
b: [2, 3]
c: [1, 2]
d: [0, 1]
adding a+b=3
revising d+a=1
revising a+b=3
final result of domains:
a: [0, 1]
b: [2, 3]
c: [1, 2]
d: [0, 1]

From Domains to Assignments

Two complete solutions satisfy all four equations:

a b c d
1 2 2 0
0 3 1 1

Choosing a = 0 and b = 2 from their remaining domains would still violate a + b = 3. Local domain filtering is therefore different from selecting a globally consistent assignment.

Try: add the reverse arcs and compare the trace and final domains. Then fix a to one value and consider what further propagation would imply.

Answers and discussion
  1. Reverse arcs change the work, but not these final domains. Add ('b', 'a', 3), ('c', 'b', 4), ('d', 'c', 2), and ('a', 'd', 1). The queue now explicitly checks support in both directions, so the revision trace changes. For this particular example, the final domains remain a: {0, 1}, b: {2, 3}, c: {1, 2}, and d: {0, 1}: each surviving value participates in one of the two complete solutions above. Other CSPs can need reverse arcs to remove additional values.
  2. Fixing a selects one of the two solutions. If a = 0, the equations force b = 3, then c = 1, then d = 1. If a = 1, they force b = 2, c = 2, and d = 0. Set the chosen domain to a singleton and rerun ac3 on that domain dictionary. Calling solve instead would recreate all digit domains and discard the restriction. Fixing a to any other digit makes the CSP inconsistent.

Takeaway: unsupported values can be removed without branching, but surviving values do not generally certify that every combination is valid.