Q8 — CSP: Arc Consistency, Path Consistency, Solution

The Question

CSP over A, B, C (processed in that order), $D_A = D_B = D_C = \{1, \dots, 9\}$:

$R_{AB} = \{(2,6), (3,5)\} \qquad R_{AC} = \{(2,8), (3,7)\} \qquad R_{BC} = \{(5,7), (5,8), (6,7)\}$

The Topic in 60 Seconds

• Arc consistent: every domain value on the matching diagram has a support in each neighbour.
• Path consistent: every allowed pair $(x, y)$ on an arc has a middle value $z$ compatible with both.
• Arc consistency does not imply path consistency.

Deep-dive: Arc Consistency, Forward Checking.

The matching diagram

Only the values that appear in the relations can ever be used — draw them:

8.1 — Arc consistent → Yes

On the matching diagram, every value has support in each neighbour:

No value pruned → arc consistent ✓ (values outside the relations — 1, 4, 9, … — are already excluded by the constraints themselves.)

8.2 — Path consistency → B (not path consistent)

Test the pair (A, B) with tuple $(2, 6)$ — need $c \in D_C$ with $(2, c) \in R_{AC}$ and $(c, 6) \in R_{BC}$:

• $(2, c) \in \{(2,8), (3,7)\}$ → $c = 8$
• $(8, 6) \in R_{BC}$? $R_{BC} = \{(5,7), (5,8), (6,7)\}$ → no!

Tuple $(2,6)$ has no middle support through C → not path consistent → B ✓

8.3 — Solution → 3,5,7

Try the tuples: $(3, 5)$ on A–B, then $C$ must satisfy $(3, c) \in R_{AC}$ → $c = 7$, and $(5, 7) \in R_{BC}$ ✓

$A = 3,\quad B = 5,\quad C = 7 \Rightarrow \texttt{3,5,7}$ ✓

(Check the other branch: $(2,6)$ forces $c = 8$, but $(6,8) \notin R_{BC}$ — dead end, exactly the path-inconsistency found above.)

Tricks & Tips

Interactive tuple hunt — arc consistency passes, then path consistency catches the impostor:

Tricks & Tips

Answers: 8.1 A (Yes) · 8.2 B (not path consistent) · 8.3 3,5,7