Q9 — Constraint Satisfaction: AC and PC

The Question

CSP over A, B, C with $D_A = D_B = D_C = \{1,2,3,4\}$:

$R_{AC}:\ A = \bmod(2C, 3) \qquad R_{BA}:\ B = \bmod(3A, 4) \qquad R_{CB}:\ C = \bmod(2B, 3)$

Step 0 — Compute the relations

$R_{AC}$: $A = \bmod(2C, 3)$

$R_{AC} = \{(2,1), (1,2), (2,4)\}$

$R_{BA}$: $B = \bmod(3A, 4)$

$R_{BA} = \{(3,1), (2,2), (1,3)\}$

$R_{CB}$: $C = \bmod(2B, 3)$

$R_{CB} = \{(2,1), (1,2), (2,4)\}$

Each relation keeps exactly three of the four offered option tuples — the keyed triples (A,B,C) twice over.

9.3 — Arc-consistent? → No

Scan for unsupported values:

• $A = 3$: needs a tuple in $R_{BA}$ with second coordinate 3 — $(1,3)$ exists ✓ supported... but check $A$'s OTHER arc $R_{AC}$: values of $A$ there are $\{1, 2\}$ — no $(3, C)$ tuple ⇒ $A=3$ unsupported.
• $B = 4$: $R_{BA}$ contains no $(4, A)$ ⇒ unsupported.

One unsupported value anywhere ⇒ not arc-consistent → B.

9.4 — Enforce AC → path-consistent → Yes

Delete unsupported values:

$D_A = \{1,2\}\ (\text{via } R_{AC}), \qquad D_B = \{1,2,3\}, \qquad D_C = \{1,2,4\}$

Re-revise every arc until stable — remaining tuples all mutually support each other. Path consistency on a three-variable cycle reduces to the composed triple test: the network admits the consistent triple below, so path-consistent → A.

9.5 — Solution → 2,2,1

Walk $R_{BA}$'s tuples and extend:

Unique solution:

$(A, B, C) = \mathbf{(2,\ 2,\ 1)}$

Verify: $2 = \bmod(2\cdot1, 3)$ ✓ · $2 = \bmod(3\cdot2, 4)$ ✓ · $1 = \bmod(2\cdot2, 3)$ ✓

Interactive trace

Tricks & Tips

Answers: 9.1 A, B, C · 9.2 A, B, C · 9.3 B · 9.4 A · 9.5 2,2,1