Q8 — CONSTRAINT SATISFACTION

Forward checking assigns d, stumbles twice on X3 (two domain wipeouts), then locks 3,4,q - giving both official sequences depending on how you count retries.

The Question

The figure shows a constraint graph of a Binary CSP and a part of the matching diagram. When a pair of variables (like, X1 and X5) do not have a constraint in the constraint graph then assume a UNIVERSAL RELATION in the matching diagram.

Process the variables, and their values, in ALPHABETIC order.

Based on the above data, answer the given subquestions.

The matching diagram gives the variable domains: $D_{X1} = \{a, b, c\}$ , $D_{X2} = \{d, e, f\}$ , $D_{X3} = \{1, 2, 3\}$ , $D_{X4} = \{4, 5, 6\}$ , $D_{X5} = \{p, q, r\}$ .

#	Question	Official answer
8.1	The Forward-Checking algorithm begins by assigning X1=a. What are the NEXT four values assigned to variables by the Forward-Checking algorithm? List the valu...	`d,1,2,3` / `d,3,4,q`
8.2	What is the first solution found by the Forward-Checking algorithm?	`a,d,3,4,q`

The Topic in 60 Seconds

Forward Checking (FC) assigns variables one at a time; after each assignment it prunes every unassigned neighbour's domain of values incompatible with what is already placed. If any future domain becomes empty — a wipeout — the algorithm immediately undoes the assignment and tries the next value. Variables and values are tried in alphabetical order.

Deep-dive: browse the Concepts section for Constraint Satisfaction.

Step 0 — Who constrains whom

Arc	Relation
X1–X2, X2–X5, X5–X3, X3–X4, X4–X1	real binary relations (read off the matching diagram figure)
X1–X3, X1–X5, X2–X3, X2–X4, X3–X5? no — X5–X3 is real	universal (any value pairs with any value)

Key consequence used below: once X1 = a is placed, X4's live options shrink through the X4–X1 arc, and the X3–X4 arc then has no partner left for $X3 \in \{1, 2\}$ — that is what kills the first two X3 attempts.

8.1 — Next four assignments → `d,1,2,3` (with retries) / `d,3,4,q` (successful)

Order	Variable	Value tried	FC verdict
0	X1	a (given)	neighbours X2, X4 pruned
1	X2	d	all future domains still non-empty → keep
2a	X3	1	X4's remaining domain becomes EMPTY (wipeout) → undo
2b	X3	2	same wipeout → undo
2c	X3	3	X4 retains a survivor → keep
3	X4	4	consistent with X3=3 and X1=a → keep
4	X5	q	p and r clash with the X2/X5–X3 arcs → q kept

Both official forms describe the same run:

d,1,2,3 counts every value the algorithm puts on a variable, including the two failed X3 trials that were immediately retracted — four assignment events after X1=a.
d,3,4,q lists only the assignments that stuck — equally defensible reading of "assigned".

8.2 — First solution → `a,d,3,4,q`

Continuing past 8.1, all five variables end assigned with no wipeouts:

$X1=a,\quad X2=d,\quad X3=3,\quad X4=4,\quad X5=q$

Every real arc checks out (X1–X2: a–d ✓, X2–X5: d–q ✓, X5–X3: q–3 ✓, X3–X4: 3–4 ✓, X4–X1: 4–a ✓), so this is the first complete solution FC reaches — no backtracking above the X3 level ever happens.

Interactive trace — forward checking with two wipeouts

1 / 8

D(X1)={a,b,c} D(X2)={d,e,f} D(X3)={1,2,3} D(X4)={4,5,6} D(X5)={p,q,r}

assignedbeing triedunassigned, domain shrinkingwiped out

Tricks & Tips

Answers: 8.1 d,1,2,3 / d,3,4,q · 8.2 a,d,3,4,q