Questions: Constraint Satisfaction Problem Solving

Question 1

You are solving a Sudoku puzzle using only constraint propagation (arc consistency). After running AC-3 to completion, several cells still have two or more possible values. What can you conclude?

• A. The puzzle has no solution — if it did, propagation would have found all unique values
• B. The puzzle has multiple solutions, since propagation would have determined unique values if only one solution existed
• C. Constraint propagation has eliminated all provably impossible values, but backtracking search is still needed to commit to specific values
• D. The remaining ambiguity indicates an error in the constraint specification

Answer: (C)

Constraint propagation (including arc consistency) is not a complete solver — it removes values that are inconsistent with current assignments, but it cannot by itself determine which of multiple consistent values is correct. Most real CSPs require both propagation and search. Propagation without search is incomplete; search without propagation is exponentially slow. Options A and B confuse propagation's capability with a complete solver's; option D is false — even correctly specified CSPs routinely require search after propagation.

Question 2

The Minimum Remaining Values (MRV) heuristic selects the next variable to assign by choosing the one with the fewest remaining legal values. Why does this tend to speed up solving?

• A. Variables with fewer remaining values are more likely to have the correct value, guiding the solver toward the solution
• B. Variables with fewer remaining values are most constrained and most likely to cause failure — detecting that failure early prunes the search tree before more variables are assigned
• C. MRV reduces the total number of constraints by eliminating variables with small domains first
• D. MRV ensures every variable gets at least one value assigned, preventing the solver from getting stuck

Answer: (B)

MRV is a 'fail-first' heuristic. If the most constrained variable will eventually fail (has no legal assignment), discovering that failure NOW — before branching on many other variables — means the solver backtracks immediately with minimal wasted work. This prunes entire subtrees of the search space at their root rather than their leaves. Option A is incorrect — fewer remaining values does not imply 'more likely to be correct.' Options C and D mischaracterize what the heuristic actually does.

Question 3

If arc consistency (AC-3) is enforced globally before any variable is assigned, the resulting reduced domains are very likely to contain a valid complete assignment.

• T. True
• F. False

Answer: False

Arc consistency removes values that have no support in neighboring domains, but it does not guarantee that a globally consistent assignment exists. A CSP can be arc-consistent yet infeasible — for example, in graph 3-coloring, arc consistency may reduce domains but cannot detect that no valid coloring exists without search. This is precisely why backtracking search remains necessary: propagation is incomplete as a solver, and arc consistency is a local property that does not imply global satisfiability.

Question 4

CSP backtracking search is more efficient than naive exhaustive enumeration because it detects constraint violations in partial assignments and abandons branches that cannot lead to solutions.

• T. True
• F. False

Answer: True

Naive enumeration generates all complete assignments before checking constraints — exponential work. Backtracking prunes the search tree as soon as a partial assignment violates a constraint, cutting off entire subtrees that could never lead to a solution. Combined with forward checking (propagating constraints from newly assigned variables), most infeasible branches are pruned before they are explored, often reducing search from exponential to tractable for practical CSP instances.

Question 5

Explain why combining constraint propagation with backtracking is more powerful than either technique used alone.

Model answer: Constraint propagation alone is incomplete — it can reduce domains by eliminating clearly impossible values, but for most CSPs it cannot determine which of the remaining consistent values is correct without committing to one. Backtracking alone is correct but exponentially slow — it must explore an enormous search tree. When combined, propagation prunes the search tree at each decision node by eliminating values made impossible by the current partial assignment, dramatically reducing the branching factor before the solver makes new commitments. Backtracking then handles the residual search. Each constraint violation detected by propagation eliminates not just one assignment but an entire subtree.

This synergy is why real CSP solvers scale to thousands of variables. The key insight is that propagation is cheap per node and dramatically reduces the size of the remaining search problem, while backtracking provides the completeness guarantee. Neither alone is practical for large real-world CSPs; together they are the foundation of every modern constraint solver.