Q7 — Map Colouring CSP: Arc Consistency, Path Consistency, Solution

The Question

Map colouring with 3 regions $\{A, B, C\}$, all three pairwise adjacent, processed in order A, B, C.

$D_A = \{r, b, g\}, \qquad D_B = \{r, b\}, \qquad D_C = \{r, b\}$

Constraint: adjacent regions must take different colours.

The Topic in 60 Seconds

• Arc consistent (per directed arc $X \to Y$): every $x \in D_X$ has some $y \in D_Y$ with $(x,y)$ allowed. Prunes values.
• Path consistent (per triple): for every allowed pair $(x,y)$ on arc $X \!-\! Y$ there is some $z \in D_Z$ compatible with both. Prunes relations (tuples).
• Arc consistency does not imply path consistency — this question is the counter-example.

Deep-dive: Arc Consistency, Forward Checking.

The constraint graph

7.1 — Arc consistency → Yes

Check every directed arc; "compatible" = different colours:

Every value has a support → arc consistent ✓. (Easy to miss: $g \notin D_B$, but arc consistency only needs some compatible neighbour value, not the same colour.)

7.2 — Path consistency → No

Take the pair (A, C) with the allowed tuple $(r, b)$ — is there $z = b' \in D_B$ compatible with both?

• $(a, z) = (r, b')$: needs $b' \ne r$ → $b' = b$
• $(z, c) = (b, b)$: needs $b \ne b$ — impossible!

The other $D_B$ value $r$ fails the first test ($(r,r)$). So the tuple $(r,b)$ on arc A–C has no middle support through B → not path consistent → option A ✓

7.3 — Solution → g,r,b

Assign in order A, B, C with all-different:

• $A = r$: then $B = b$, and $C \in \{r,b\}$ must differ from both $r$ and $b$ → dead end (this is exactly the path-inconsistency above).
• $A = b$: symmetric dead end.
• $A = g$: $B = r$ (or b), $C = b$ (or r) → $g \ne r \ne b \ne g$ ✓

Solution: A=g, B=r, C=b → g,r,b ✓

Tricks & Tips

Interactive trace — the all-different triangle:

Tricks & Tips

Answers: 7.1 A (Yes) · 7.2 A (No) · 7.3 g,r,b