= Solution
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 failure
``
SELECT-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 $Y$ of $X$, remove every value incompatible with $X=v$, 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.<CS 188 constraint filtering notes>[§2.3, opening paragraphs: filtering neighbors after assignment]{ref}<CS 188 constraint ordering and structure notes>[§2.4, Minimum Remaining Values]{ref}
Back to article page
