Q8 — Constraint Satisfaction: AC and PC

Three mod-relations over {1..4}: compute the tables, watch arc-consistency shave value 3 off every domain, then hunt the unique solution 2,4,1.

The Question

Consider a CSP over 3 variables A, B, C where the domains and constraints are:

$D_A = D_B = D_C = \{1,2,3,4\}$ $R_{AC}: A = \text{mod}(2C, 3)$ $R_{BA}: B = \text{mod}(2A, 7)$ $R_{CB}: C = \text{mod}(2B, 7)$

where, $\text{mod}(n,d)$ returns the remainder after dividing $n$ by $d$ , for example, $\text{mod}(8,3)=2$ , $\text{mod}(6,7)=6$ , $\text{mod}(8,7)=1$ .

Compute the three relations to match the domain constraints, then draw the constraint graph and matching-diagram, and then answer the sub-questions.

#	Question	Official answer
9.1	Which of the following tuples occur in R_AC?	A, B, C
9.2	Which of the following tuples occur in R_BA?	A, B, D
9.3	Is the given CSP arc-consistent?	B
9.4	If the given CSP is not already arc-consistent, then make it arc-consistent, and then check if the resulting network is path consistent.	A
9.5	Does the given CSP have a solution?	`2,4,1`

Step 0 — Compute the relations over $\{1,2,3,4\}$

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

$C$	$2C$	$\text{mod}(2C,3)$	Tuple $(A,C)$
1	2	2	(2,1) ✓ option B
2	4	1	(1,2) ✓ option A
3	6	0 ∉ $D_A$	pruned
4	8	2	(2,4) ✓ option C

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

Option D $(4,2)$ fails — no $C$ produces $A=4$ . → A, B, C exact.

$R_{BA}$ : $B = \text{mod}(2A, 7)$

$A$	$2A \bmod 7$	Tuple $(B,A)$
1	2	(2,1) ✓ option B
2	4	(4,2) ✓ option D
3	6 ∉ $D_B$	pruned
4	1	(1,4) ✓ option A

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

Option C $(3,1)$ fails → A, B, D exact.

$R_{CB}$ : $C = \text{mod}(2B, 7)$

By symmetry of the mod-7 form: $R_{CB} = \{(2,1), (4,2), (1,4)\}$ .

9.3 — Arc-consistent? → B (No)

AC-3 test per arc: every value needs a partner on each neighbour.

$A = 3$ : $R_{BA}$ offers no tuple with $A{=}3$ (needs $B=6$ ) → unsupported ⇒ not arc-consistent.
Same fate for $B=3$ and $C=3$ (each would need partner 6).

9.4 — After enforcing AC → path-consistent? → A (Yes)

Revise all arcs (every value loses its "3" supports simultaneously):

$D_A = D_B = D_C = \{1, 2, 4\}, \qquad R_{AC} = \{(2,1),(1,2),(2,4)\},\quad R_{BA} = R_{CB} = \{(2,1),(4,2),(1,4)\}$

Re-check every arc: all remaining values retain partners; a second pass changes nothing → arc-consistent now. Path consistency on a 3-variable network reduces to: for every consistent pair $(X, Z)$ via $Y$ , some $y$ works — equivalently here, the single composed cycle must admit a common triple. It does (next row), so path-consistent → A.

9.5 — Solution → `2,4,1`

Enumerate $R_{BA}$ 's three pairs and extend through $R_{CB}$ and $R_{AC}$ :

$(B,A)$	$C = \text{mod}(2B,7)$	$R_{AC}(A,C)$ ?
(2,1)	4	$(1,4)$ ? ✗ not in $R_{AC}$
(4,2)	1	$(2,1)$ ✓
(1,4)	2	$(4,2)$ ? ✗

Unique solution:

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

Verify all three: $2 = \text{mod}(2,3)$ ✓ · $4 = \text{mod}(4,7)$ ✓ · $1 = \text{mod}(8,7)$ ✓

Interactive trace — AC-3 revision cascade

1 / 5

D(A)=D(B)=D(C)={1,2,3,4} Arcs: R_AC, R_BA, R_CB.

domain shrinkingarc consistentvalue deleted

Tricks & Tips

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

The Question

Step 0 — Compute the relations over {1,2,3,4}\{1,2,3,4\}{1,2,3,4}

RACR_{AC}RAC​: A=mod(2C,3)A = \text{mod}(2C, 3)A=mod(2C,3)

RBAR_{BA}RBA​: B=mod(2A,7)B = \text{mod}(2A, 7)B=mod(2A,7)

RCBR_{CB}RCB​: C=mod(2B,7)C = \text{mod}(2B, 7)C=mod(2B,7)