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,7), (2,8)\} \qquad R_{BC} = \{(4,7), (5,7), (6,8)\}$

The Topic in 60 Seconds

• Arc consistent: every domain value has a support in each neighbour.
• Path consistent: every allowed pair has a middle value compatible with both.
• Making a CSP arc consistent can cascade — one pruning orphans another value.

Deep-dive: Arc Consistency, Forward Checking.

The matching diagram

8.1 — Arc consistent? → No

Check every value on the diagram:

A = 3 has no support on R_AC → not arc consistent → B ✓

8.2 — After arc consistency: path consistent? → A (path consistent)

Revise (AC-3 style):

1. $A = 3$ pruned (no C support) → $D_A = \{2\}$.
2. Cascade: $B = 5$'s support was $A = 3$ — gone! → $D_B = \{6\}$.
3. $C = 7$'s support via $R_{BC}$ was $B = 5$ — gone! → $D_C = \{8\}$.

Result: $D_A = \{2\}$, $D_B = \{6\}$, $D_C = \{8\}$ — every arc trivially consistent.

Path consistency: with singletons everywhere, the only pair is $(2, 8)$ on A–C; the middle $B = 6$ satisfies $(2, 6) \in R_{AB}$ ✓ and $(6, 8) \in R_{BC}$ ✓ → path consistent → A ✓

8.3 — Solution → 2,6,8

The cascade above leaves exactly one assignment:

$A = 2,\quad B = 6,\quad C = 8$

Verify: $(2,6) \in R_{AB}$ ✓, $(2,8) \in R_{AC}$ ✓, $(6,8) \in R_{BC}$ ✓ → 2,6,8 ✓

Tricks & Tips

Interactive AC-3 cascade — watch the domains collapse:

Tricks & Tips

Answers: 8.1 B (No) · 8.2 A (path consistent) · 8.3 2,6,8