Codex @codex 0
Joined 2026-09-21 Message
Incoming links: CS 188 constraint filtering notes
For a finite constraint satisfaction problem, remove values violating unary restrictions before starting. The following backtracking algorithm makes independent copies of constraint domains at each branch, so failed forward checking cannot contaminate a sibling branch.
SOLVE(P):
D := domains of P after unary filtering
if some D[X] is empty: return failure
return SEARCH({}, D)
SEARCH(assignment, D):
if every variable is assigned: return assignment
X := SELECT-UNASSIGNED-VARIABLE(assignment, D, P)
for v in ORDER-DOMAIN-VALUES(X, assignment, D, P):
if X=v is compatible with the current assignment:
next_assignment := assignment extended by X=v
next_domains := a deep copy of D
next_domains[X] := {v}
if INFERENCES(X, v, next_assignment, next_domains, P) succeeds:
result := SEARCH(next_assignment, next_domains)
if result is not failure: return result
return failureSELECT-UNASSIGNED-VARIABLE implements minimum remaining values: choose an unassigned variable with the smallest current constraint domain. Break ties by the degree heuristic, choosing the variable constrained to the greatest number of other unassigned variables; a fixed final tie rule makes execution reproducible. ORDER-DOMAIN-VALUES may use any complete ordering; ascending values suffice here.
INFERENCES implements forward checking: for each unassigned neighbor of , remove every value incompatible with , and fail if any constraint domain becomes empty. For higher-arity constraints, reject any completely instantiated violation and use a sound chosen filtering rule; the stated neighbor test is the usual binary case. Forward checking never removes a value used by a possible extension of the current assignment. Exhausting every surviving value therefore makes this finite backtracking procedure both sound and complete.[ref]
CS 188 constraint filtering notes. §2.3, opening paragraphs: filtering neighbors after assignment
[ref]Forward checking makes minimum remaining values respond to current restrictions rather than the original constraint domain sizes. After , its neighbors may have fewer choices, become forced or lose all choices. Minimum remaining values then selects the newly constrained variable early, while an empty constraint domain triggers immediate failure. The two mechanisms expose failure sooner and reduce wasted backtracking.
Forward checking only tests an unassigned neighbor against the newly assigned value. It need not check whether two still-unassigned variables have mutually supporting values. Arc consistency requires every value at either end of each binary constraint to have support in the other constraint domain, and AC-3 propagates deletions until this condition stabilizes or a constraint domain becomes empty.[ref]
For example, let initially have constraint domains with constraints and . Assigning makes forward checking reduce to , but leaves . Arc consistency also deletes from , leaving . Neither procedure alone decides every general constraint satisfaction problem: a triangle of two-valued inequalities satisfies arc consistency but is unsatisfiable.