
8.4 CSP Techniques and Algorithms 183
PC(C)
until stabilization of all constraints in C do
for each k : 1 ≤ k ≤ n do
for each pair i, j : 1 ≤ i<j≤ n, i = k, j = k do
c
ij
← c
ij
∩[c
ik
•
c
kj
]
if c
ij
=∅then exit(inconsistent)
end
Figure 8.5 Path consistency in a CSP
A CSP is said to be path-consistent or 3-consistent if a path-consistency algorithm
does not detect an inconsistency. However, algorithm PC, as any other filtering algo-
rithm, is not complete for consistency checking: it may not detect an inconsistent
network, as illustrated in the following example.
Example 8.13 Consider the graph coloring problem, i.e., assigning distinct colors to
adjacent vertices ...