Question: What is the difference between MRV and LCV heuristics? Which is for variable selection, which for value selection?
Answer
MRV (Minimum Remaining Values): selects the variable with the fewest legal values remaining. Goal: fail early — if a variable is going to cause a contradiction, better to discover it now.
LCV (Least Constraining Value): selects the value that rules out the fewest choices for neighboring variables. Goal: keep options open — choose the value that leaves the most flexibility for the rest of the search.
MRV = variable ordering. LCV = value ordering. They serve opposite purposes (fail fast vs. succeed fast).
Max’s answer: MRV is looking at minimizing the values of each variable, while LCV makes sure to leave as many options open as possible.
MRV selects the variable with the least remaining variables, while LCV selects the one that rules out fewest options Result:
Q3 — CSP
Question: If local search on a CSP finds a globally optimal solution (objective = number of satisfied constraints), what can you conclude?
Answer
If local search maximizes number of satisfied constraints and finds the global optimum with f(s) = total number of constraints m: all constraints are satisfied → the CSP is consistent and we found a solution.
If it finds a locally optimal solution with f(s) < m: we cannot conclude anything — either the CSP is inconsistent (no solution exists), or local search got stuck in a local optimum where some constraints are still violated.
Max’s answer: the problem is consistent and complete. All contrainst are satisfied Result:
Q4 — CSP
Question: Explain k-consistency and strong k-consistency. What is the relationship to arc and path consistency?
Answer
k-consistency: any consistent assignment to k−1 variables can be extended to a consistent assignment of k variables. Strong k-consistency: the problem is j-consistent for all j ≤ k.
Relationships:
1-consistency = node consistency
2-consistency = arc consistency
3-consistency (with node consistency) = path consistency
Strong k-consistency with k = n (number of variables) guarantees a solution can be found without backtracking — but achieving it is expensive.
Max’s answer: so k-consistency checks whether additional variables can be added to the current state. that first implies arc- and path-consistency. so whenever a new variable gets checked it checks for arc and path consistency. but 3-consistency does not imply 2-consistency, since k-constency only checks for new varibales and the existing contraints. but in strong-constistency you can infer that also the new variables matches all contraints Result:
Q5 — CSP
Question: What is the formal definition of a CSP? Give each component’s meaning.
Answer
A CSP is a triple ({X₁, …, Xₙ}, {D₁, …, Dₙ}, R) where:
X₁, …, Xₙ: variables
D₁, …, Dₙ: domains — Dᵢ is the set of possible values for Xᵢ
R: set of constraints — relations over subsets of variables that restrict valid assignments
A solution is a complete assignment (all variables assigned) that is consistent (no constraint violated). If a solution exists, the CSP is consistent; otherwise inconsistent.
Max’s answer: a csp is a triple of a set of variables X, a set of Domains D and a set of constraints R.
a solution is a complete assignment that is consistent Result:
Q6 — CSP
Question: Does arc consistency (or even path consistency) guarantee that a CSP has a solution? Why or why not?
Answer
No. Neither arc consistency nor path consistency guarantees a solution. They only ensure local properties:
Arc consistency: every value has some support in each neighbor’s domain.
Path consistency: every consistent pair assignment can be extended by a third variable.
These can all hold while the CSP is still globally inconsistent. You need strong n-consistency (or backtracking search) to guarantee a solution. A concrete example: 3-coloring of certain graphs is arc-consistent but has no solution.
Max’s answer: Result:
Visual Questions (graphs rendered with Python)
Click each [!example]- toggle to render the graph (Pyodide / Execute Code plugin). Then answer the question before opening the answer callout.
What you see. A 5-node CSP after the assignment X1 = R has been made (X1 shown filled red). The remaining four variables have already been forward-checked: their displayed domains are what is still legal given X1 = R. Edges are “must-differ” constraints. You must decide which variable backtracking search picks next under the MRV + degree heuristic.
Question: X1 has been assigned to R and the remaining domains have been forward-checked. Using MRV with the degree tie-breaker, which variable should be chosen next? Show your reasoning.
Answer
Domain sizes: X2=2, X3=2, X4=3, X5=2.
MRV picks the variable with the smallest domain → ties between X2, X3, X5 (all size 2). Apply the degree heuristic as tiebreaker: count constraints with unassigned variables.
⇒ Pick X3. Highest degree among MRV ties → constrains the most other variables → fail-fast.
Max’s answer: Result:
Q12 — Arc-consistent but unsatisfiable 🔴
🐍 Graph — 3 variables, pairwise "≠" constraints
import micropipawait micropip.install("matplotlib")import matplotlib.pyplot as pltfrom matplotlib.patches import Circleimport mathpos = {"X": (0, 1), "Y": (2, 1), "Z": (1, 2.7)}EDGES = [("X","Y"), ("Y","Z"), ("X","Z")]DOMAINS = {"X": "{R, G}", "Y": "{R, G}", "Z": "{R, G}"}fig, ax = plt.subplots(figsize=(7, 5))for v1, v2 in EDGES: x1, y1 = pos[v1]; x2, y2 = pos[v2] ax.plot([x1, x2], [y1, y2], "-", color="#555", lw=2, zorder=1) mx, my = (x1+x2)/2, (y1+y2)/2 ax.text(mx, my+0.1, "≠", ha="center", fontsize=14, color="#c0392b", fontweight="bold", bbox=dict(boxstyle="round,pad=0.15", fc="white", ec="none"))for v, (x, y) in pos.items(): ax.add_patch(Circle((x, y), 0.32, facecolor="#3498db", edgecolor="black", lw=2, zorder=2)) ax.text(x, y, v, ha="center", va="center", fontsize=13, fontweight="bold", color="white", zorder=3) dy = -0.7 if y < 2 else 0.55 ax.text(x, y+dy, f"D = {DOMAINS[v]}", ha="center", fontsize=11)ax.set_xlim(-1.5, 3.5); ax.set_ylim(-0.5, 4)ax.set_aspect("equal"); ax.axis("off")ax.set_title("Q12 — Is this CSP arc-consistent? Does a solution exist?\n" "(constraint on every edge: the two endpoints must DIFFER)", fontsize=11)plt.tight_layout(); plt.show()
What you see. Three variables X, Y, Z arranged as a triangle, each with the two-element domain {R, G}, and every edge carries a pairwise ”≠” constraint (no two adjacent variables may share a colour). The graph looks innocent — every value has supporting partners — but a 2-colouring of a triangle is impossible. This question tests whether you can distinguish local consistency (arc consistency) from global consistency (a solution exists).
Question: Three variables X, Y, Z each with domain {R, G}, pairwise ”≠” constraints (triangle). (a) Is this CSP arc-consistent? (b) Does a solution exist? (c) What does this tell you about the strength of AC-3?
Answer
(a) Yes, it is arc-consistent. For every variable and every value, there is a supporting value in the neighbour’s domain — e.g. for X = R, neighbour Y has G (≠ R). Same for every other (variable, value, neighbour) triple.
(b) No, no solution exists. The constraint graph is a triangle (3-cycle) — an odd cycle — and it is not 2-colourable. Any complete assignment of {R, G} to three pairwise-different variables must reuse a colour, violating an edge.
(c) The strong takeaway:arc-consistency does NOT guarantee global consistency. AC-3 will leave all domains untouched here, even though the CSP is unsolvable. Detecting this kind of failure requires path-consistency (3-consistency) or stronger. This is the classic exam trap: “the CSP is arc-consistent therefore solvable” is false.
Max’s answer: Result:
More consistency concepts (Q13–Q15)
The previous quiz covered AC-3 and the k-consistency definitions in text. These three visual questions drill the concepts the slides emphasise: node consistency, path consistency (with the exact slide example that fails), and the hierarchy of consistencies.
What you see. Three isolated variables — there are no edges drawn because there are no binary constraints. The yellow boxes above each node are unary constraints: rules that involve just one variable. Right now every domain still contains all of {1, 2, 3, 4, 5}, including values that would violate the unary rule.
Question: (a) Define node consistency. (b) Which values must be removed from each domain to make this CSP node-consistent? (c) Why is node consistency the cheapest consistency concept to enforce?
Answer
(a) Definition. A variable Xᵢ is node-consistent iff every value in Dᵢ satisfies all unary constraints on Xᵢ. A CSP is node-consistent iff every variable is. Formally: ∀x ∈ Dᵢ : Pᵢ(x) holds, where Pᵢ is the unary predicate on Xᵢ.
(b) Reduced domains.
X1 (must be odd) → D(X1) = {1, 3, 5}
X2 (must be ≥ 3) → D(X2) = {3, 4, 5}
X3 (must be ≠ 4) → D(X3) = {1, 2, 3, 5}
(c) Why cheap. Node consistency is 1-consistency — it only looks at one variable at a time, no interaction with neighbours. The fix is trivial: walk through each domain once and delete violating values. Cost: O(Σᵢ |Dᵢ|). No propagation, no queue, no fixpoint loop. It is always the first preprocessing step you do before arc consistency.
Max’s answer: Result:
Q14 — Path Consistency (the slide example) 🔴
🐍 Graph — 3 variables, all "≠", but only 2 colors
import micropipawait micropip.install("matplotlib")import matplotlib.pyplot as pltfrom matplotlib.patches import CirclePOS = {"x": (0, 1), "y": (4, 1), "z": (2, 3)}EDGES = [("x", "y"), ("x", "z"), ("y", "z")]DOMAINS = {"x": "{red, blue}", "y": "{red, blue}", "z": "{red, blue}"}fig, ax = plt.subplots(figsize=(7, 5))for v1, v2 in EDGES: x1, y1 = POS[v1]; x2, y2 = POS[v2] ax.plot([x1, x2], [y1, y2], "-", color="#555", lw=2, zorder=1) mx, my = (x1+x2)/2, (y1+y2)/2 dy = 0.18 if v2 != "z" else -0.18 ax.text(mx, my+dy, "≠", ha="center", fontsize=15, color="#c0392b", fontweight="bold", bbox=dict(boxstyle="round,pad=0.15", fc="white", ec="none"))for v, (x, y) in POS.items(): ax.add_patch(Circle((x, y), 0.32, facecolor="#16a085", edgecolor="black", lw=2, zorder=2)) ax.text(x, y, v, ha="center", va="center", fontsize=14, fontweight="bold", color="white", zorder=3) dy = -0.7 if y < 2 else 0.6 ax.text(x, y+dy, f"D = {DOMAINS[v]}", ha="center", fontsize=11)ax.set_xlim(-1.5, 5.5); ax.set_ylim(-0.5, 4.5)ax.set_aspect("equal"); ax.axis("off")ax.set_title("Q14 — Slide example: arc-consistent, but path-inconsistent.\n" "Take the assignment x=red, y=blue. Can we extend it to z?", fontsize=11)plt.tight_layout(); plt.show()
What you see. Three variables x, y, z forming a triangle, each with domain {red, blue}, every edge a pairwise ”≠” constraint. This is the exact example from the lecture slide on path consistency. The pair (x, y) is arc-consistent on its own — red has support (blue), blue has support (red). The question is whether that assignment can be extended through z while keeping arc-consistency.
Question: (a) Define path consistency of two nodes (i, j) with respect to a third node m. (b) Take the arc-consistent partial assignment x = red, y = blue. Show that nodes x and y are NOT path-consistent with z. (c) Conclude: is arc consistency enough to guarantee a solution?
Answer
(a) Definition (from the slides). Nodes i and j are path-consistent w.r.t. node m iff: for every arc-consistent assignment of i and j, there exists a value for m that is arc-consistent with both the assignment of i and the assignment of j. Formally: ∀x ∈ Dᵢ, z ∈ Dⱼ : Pᵢⱼ(x, z) → (∃y ∈ Dₘ : Pᵢₘ(x, y) ∧ Pₘⱼ(y, z)).
(b) Trace. Pick (x = red, y = blue) — this satisfies x ≠ y, so it is arc-consistent. Now look for a value of z that satisfies x ≠ z AND y ≠ z:
try z = red → violates x ≠ z (x is also red). ✗
try z = blue → violates y ≠ z (y is also blue). ✗
No value of z works ⇒ x and y are not path-consistent with z under that assignment.
(c) Conclusion. The CSP is arc-consistent (every individual value has a single supporter in each neighbour) but not path-consistent, and in fact has no solution. So arc consistency is strictly weaker than path consistency, and neither guarantees a solution. The slide’s takeaway: if you only enforce AC-3 you may search through dead branches that path-consistency would have ruled out.
Max’s answer: Result:
Q15 — The consistency hierarchy 🟡
🐍 Diagram — concentric levels of k-consistency
import micropipawait micropip.install("matplotlib")import matplotlib.pyplot as pltfrom matplotlib.patches import FancyBboxPatchlevels = [ ("1-consistency = Node consistency", "every value in Dᵢ satisfies the unary constraint Pᵢ", "#f1c40f"), ("2-consistency = Arc consistency", "every value in Dᵢ has a supporter in Dⱼ for every binary constraint Pᵢⱼ", "#e67e22"), ("3-consistency = Path consistency (assuming node consistency)", "every consistent assignment to 2 variables can be extended to a 3rd", "#e74c3c"), ("k-consistency", "every consistent assignment to (k − 1) variables can be extended to a k-th", "#9b59b6"), ("Strong k-consistency", "j-consistent for ALL j ≤ k → if k = n, solution found WITHOUT backtracking", "#2c3e50"),]fig, ax = plt.subplots(figsize=(13, 7))y = len(levels)for i, (title, body, color) in enumerate(levels): box = FancyBboxPatch((0, y-i-0.85), 12.5, 0.75, boxstyle="round,pad=0.05", fc=color, ec="black", lw=1.5) ax.add_patch(box) ax.text(0.3, y-i-0.48, title, fontsize=12, fontweight="bold", color="white", va="center") ax.text(0.3, y-i-0.72, body, fontsize=10, color="white", va="center", style="italic") # arrow showing "weaker → stronger" if i < len(levels) - 1: ax.annotate("", xy=(6.2, y-i-0.95), xytext=(6.2, y-i-0.87), arrowprops=dict(arrowstyle="->", color="#333", lw=2))ax.text(13, y-0.5, "weaker", fontsize=11, color="#666", fontweight="bold", va="center")ax.text(13, y-len(levels)+0.2, "stronger", fontsize=11, color="#333", fontweight="bold", va="center")ax.set_xlim(-0.2, 14.5); ax.set_ylim(-0.5, y+0.3)ax.axis("off")ax.set_title("Q15 — The hierarchy of consistency concepts", fontsize=13, fontweight="bold")plt.tight_layout(); plt.show()
What you see. A vertical stack of the five named consistency concepts, top (weakest) to bottom (strongest). Each row shows the standard short name and a one-line definition. The implication chain goes downward: stronger concepts imply all weaker ones (if a CSP is path-consistent it is also arc-consistent, etc., when the cheaper levels are also enforced).
Question: (a) State the precise relationship between the named consistencies and the numeric k-consistency levels. (b) Why does strong n-consistency (n = number of variables) guarantee a backtrack-free solution? (c) Why don’t we always just enforce strong n-consistency?
Answer
(a) Naming.
1-consistency = node consistency
2-consistency = arc consistency
3-consistency (combined with node consistency) = path consistency
General k-consistency: any consistent assignment of any k − 1 variables can be extended to a k-th
Strong k-consistency = j-consistent for all j ≤ k (it is k-consistency together with all weaker levels)
(b) Why strong n-consistency ⇒ no backtracking. If the CSP is strong n-consistent, then any consistent partial assignment of size n − 1 can be extended to a consistent n-th — and recursively, any consistent partial of size k can be extended to k+1. So a greedy algorithm that picks one variable at a time and assigns any value that doesn’t violate a constraint will never have to backtrack — it walks straight to a solution.
(c) Why we don’t always do it. Enforcing k-consistency for large k is expensive — exponential in k in the worst case. The slides put it bluntly: “If preprocessing time exceeds time for solving CSP, it isn’t worth it.” In practice we enforce node + arc consistency (cheap, big win) and let backtracking handle the rest. Path consistency is sometimes added for tightly-constrained problems.
Max’s answer: Result:
Beyond the lecture (optional)
These questions go beyond the SoSe 2026 lecture slides (textbook / external additions). Kept for depth, not exam-critical.
Q1 — CSP
Question: What is arc consistency, and what does AC-3 do to achieve it?
Answer
Arc consistency: variable Xᵢ is arc-consistent w.r.t. Xⱼ if for every value in Dᵢ, there exists at least one value in Dⱼ satisfying the constraint between them. A CSP is arc-consistent if all variables are arc-consistent w.r.t. all their neighbors. AC-3: maintains a queue of arcs. For each arc (Xᵢ, Xⱼ), removes values from Dᵢ with no support in Dⱼ. If Dᵢ shrinks, re-adds all arcs pointing to Xᵢ (since their support may now be gone). Repeats until queue empty. If any domain becomes empty → CSP is inconsistent.
Max’s answer: Arc consistency tests whether nodes in a graph are consistent with its neighbours. this consistency is unidirectional, meaning if domain A,B are also in the neighbour node, it is arc consistent in this direction.
Result:
Q7 — CSP
Question: What are the RCC-8 spatial relations? Name and describe at least 4.
Answer
RCC-8 describes 8 topological relations between regions (no metric needed):
DC (Disconnected): regions have no connection at all
EC (Externally Connected): regions touch but don’t overlap (share boundary only)
PO (Partial Overlap): regions overlap but neither contains the other
TPP (Tangential Proper Part): X is inside Y and shares part of Y’s boundary
NTPP (Non-Tangential Proper Part): X is strictly inside Y with no shared boundary
EQ (Equal): X and Y are the same region
TPPi and NTPPi are the inverses of TPP and NTPP respectively.
Total: 8 relations (all mutually exclusive and collectively exhaustive).
Max’s answer: Result:
Q8 — AC-3 trace 🟡
🐍 Graph — 3 variables, constraints A < B and B < C
import micropipawait micropip.install("matplotlib")import matplotlib.pyplot as pltfrom matplotlib.patches import CircleNODES = {"A": (1, 1), "B": (3, 1), "C": (5, 1)}DOMAINS = {"A": "{1, 2, 3}", "B": "{1, 2, 3}", "C": "{1, 2, 3}"}EDGES = [("A", "B", "A < B"), ("B", "C", "B < C")]fig, ax = plt.subplots(figsize=(9, 3.5))for v1, v2, lbl in EDGES: x1, y1 = NODES[v1]; x2, y2 = NODES[v2] ax.plot([x1, x2], [y1, y2], "-", color="#555", lw=2, zorder=1) ax.text((x1+x2)/2, y1+0.18, lbl, ha="center", fontsize=11, color="#c0392b", fontweight="bold")for v, (x, y) in NODES.items(): ax.add_patch(Circle((x, y), 0.35, facecolor="#3498db", edgecolor="black", lw=2, zorder=2)) ax.text(x, y, v, ha="center", va="center", fontsize=14, fontweight="bold", color="white", zorder=3) ax.text(x, y-0.7, f"D = {DOMAINS[v]}", ha="center", fontsize=10)ax.set_xlim(0, 6); ax.set_ylim(-0.5, 2)ax.set_aspect("equal"); ax.axis("off")ax.set_title("Q8 — Run AC-3 on this CSP. What are the final domains?", fontsize=12)plt.tight_layout(); plt.show()
What you see. A linear 3-node graph A–B–C with two binary “less-than” constraints (A < B on the left edge, B < C on the right). Each node currently has the same domain {1, 2, 3}. AC-3 will propagate the constraints back and forth, shrinking domains, until either every value has support in every neighbour or some domain becomes empty.
Question: Run AC-3 on this CSP step by step. What are the final domains of A, B, C after AC-3 terminates?
Answer
Core idea. For each arc (source, target), check: “for every value x in D(source), is there at least one y in D(target) such that the constraint holds?” If x has no supporter, delete x from D(source). Whenever a domain shrinks, re-add every arc that points into it (their support may now be gone).
Starting queue:(A,B), (B,A), (B,C), (C,B). Initial domains all {1,2,3}.
Step 1 — arc (A, B). “For each A, ∃ B with A<B?”
A=1 → B=2,3 ✓
A=2 → B=3 ✓
A=3 → no B in {1,2,3} satisfies 3<B → remove 3
D(A) = {1, 2}. Re-add (B, A).
Step 2 — arc (B, A). “For each B, ∃ A in {1,2} with A<B?”
B=1 → no A with A<1 → remove 1
B=2 → A=1 ✓
B=3 → A=1 or 2 ✓
D(B) = {2, 3}. Re-add (A, B), (C, B).
Step 3 — arc (B, C). “For each B in {2,3}, ∃ C with B<C?”
B=2 → C=3 ✓
B=3 → no C with 3<C → remove 3
D(B) = {2}. Re-add (A, B), (C, B).
Step 4 — arc (C, B). “For each C, ∃ B in {2} with B<C?”
Final domains: D(A) = {1}, D(B) = {2}, D(C) = {3} — the unique solution.
Why AC-3 solved this completely. The constraint chain A < B < C over a 3-element domain is so tight that pure pruning forces the unique answer. On looser CSPs, AC-3 just shrinks domains and backtracking still has to choose.
Max’s answer: Result:
Q9 — 2-colorability 🟢
🐍 Graph — Three graphs side by side
import micropipawait micropip.install("matplotlib")import matplotlib.pyplot as pltfrom matplotlib.patches import Circleimport mathdef polygon_pos(n, radius=1.0, cx=0, cy=0, start=math.pi/2): return [(cx + radius*math.cos(start - 2*math.pi*i/n), cy + radius*math.sin(start - 2*math.pi*i/n)) for i in range(n)]def draw_graph(ax, n, title): pos = polygon_pos(n) # edges: cycle for i in range(n): x1, y1 = pos[i]; x2, y2 = pos[(i+1) % n] ax.plot([x1, x2], [y1, y2], "-", color="#555", lw=2, zorder=1) for i, (x, y) in enumerate(pos): ax.add_patch(Circle((x, y), 0.22, facecolor="#bdc3c7", edgecolor="black", lw=2, zorder=2)) ax.text(x, y, str(i+1), ha="center", va="center", fontsize=11, fontweight="bold", zorder=3) ax.set_xlim(-1.5, 1.5); ax.set_ylim(-1.5, 1.5) ax.set_aspect("equal"); ax.axis("off") ax.set_title(title, fontsize=11)fig, axes = plt.subplots(1, 3, figsize=(12, 4))draw_graph(axes[0], 3, "(A) 3-cycle (triangle)")draw_graph(axes[1], 4, "(B) 4-cycle (square)")draw_graph(axes[2], 5, "(C) 5-cycle (pentagon)")fig.suptitle("Q9 — Which graphs can be 2-coloured? (constraint: neighbours differ)", fontsize=12, fontweight="bold")plt.tight_layout(rect=[0, 0, 1, 0.93]); plt.show()
What you see. Three small graphs — a triangle (3-cycle), a square (4-cycle), and a pentagon (5-cycle). Treat each as a CSP where every node is a variable, every edge is a “must-differ” constraint, and the domain of each variable is just two colours. The question is which of these can be properly 2-coloured (a proper 2-colouring assigns one of two colours to each node so no edge connects same-coloured nodes).
Question: Which of the three graphs (A) triangle, (B) 4-cycle, (C) 5-cycle can be 2-coloured such that adjacent nodes have different colours? State the rule that determines the answer.
Answer
Only (B) the 4-cycle is 2-colourable (alternate the two colours: R, G, R, G).
The rule: a graph is 2-colourable if and only if it contains no odd cycle (a graph with this property is called bipartite).
(A) Triangle — odd cycle of length 3 → not 2-colourable. Try: colour 1 = R, then 2 must be G, then 3 must differ from both 1 and 2 — impossible with 2 colours.
(B) 4-cycle — even cycle → 2-colourable.
(C) 5-cycle — odd cycle → not 2-colourable.
⭐ This is the exact reason Australia map coloring with 2 colours is infeasible — the SA-centered subgraph contains a 5-cycle (NT–Q–NSW–V–SA–NT).
Max’s answer: Result:
Q11 — Forward Checking with wipeout 🔴
🐍 Graph — 4 variables, "must differ" constraints
import micropipawait micropip.install("matplotlib")import matplotlib.pyplot as pltfrom matplotlib.patches import CircleNODES = {"A": (0, 1), "B": (2, 2), "C": (2, 0), "D": (4, 1)}EDGES = [("A","B"), ("A","C"), ("B","C"), ("B","D"), ("C","D")]DOMAINS = {"A": "{R} (assigned)", "B": "{R, G}", "C": "{R, G}", "D": "{R, G}"}COLORS = {"A": "#e74c3c", "B": "#bdc3c7", "C": "#bdc3c7", "D": "#bdc3c7"}fig, ax = plt.subplots(figsize=(9, 4.5))for v1, v2 in EDGES: x1, y1 = NODES[v1]; x2, y2 = NODES[v2] ax.plot([x1, x2], [y1, y2], "-", color="#555", lw=2, zorder=1)for v, (x, y) in NODES.items(): ax.add_patch(Circle((x, y), 0.38, facecolor=COLORS[v], edgecolor="black", lw=2, zorder=2)) ax.text(x, y, v, ha="center", va="center", fontsize=12, fontweight="bold", color="white" if v == "A" else "black", zorder=3) ax.text(x, y-0.75, f"D = {DOMAINS[v]}", ha="center", fontsize=10)ax.set_xlim(-1.5, 5.5); ax.set_ylim(-1, 3)ax.set_aspect("equal"); ax.axis("off")ax.set_title("Q11 — A = R is assigned. Now we want to assign B = G.\n" "Apply forward checking. What happens?", fontsize=11)plt.tight_layout(); plt.show()
What you see. A 4-node CSP. A has been assigned R (filled red). The grey edges are “must-differ” constraints. The question walks you through what happens if we now decide to assign B = G — does forward checking flag a problem, or does the assignment survive? Trace the FC pass carefully: B’s unassigned neighbours are C and D, and one of them already had its domain reduced by the earlier assignment of A.
Question: A is already assigned R. We now decide B = G. Apply Forward Checking. What are the resulting domains of C and D? Does any wipeout happen? What does the search do next?
Answer
Before deciding B = G, the domains are D(B) = D(C) = D(D) = {R, G} (R was removed from C and D by the prior assignment A = R? Actually no — only B and C were neighbours of A, not D. Looking at the graph: A connects to B and C. So FC after A=R removed R from D(B) and D(C). The displayed {R, G} for B and C in the figure is the state before FC of A=R was applied, for clarity of the question. Assume the FC after A=R already happened: D(B) = D(C) = {G}, D(D) = {R, G}.)
More careful answer assuming the figure shows pre-FC domains and we want the result of FC after both A=R and B=G:
After A = R: FC removes R from neighbours B, C → D(B) = {G}, D(C) = {G}, D(D) = {R, G}.
Now assign B = G. FC removes G from B’s unassigned neighbours C and D:
D(C) was {G} → remove G → D(C) = {} ⇒ WIPEOUT 💥
(No need to check D — wipeout already detected.)
Result: the branch B = G is dead. Search backtracks immediately — it does not even try to assign C or D.
This is the entire point of FC: detect the dead end now, not after two more levels of fruitless assignments.