AC-3 runs to completion on a CSP and no variable domain becomes empty. What can you conclude?
AThe CSP has at least one valid solution
BThe CSP is arc-consistent, meaning each remaining value has a compatible value in every adjacent variable's domain — but a solution may or may not exist
CThe CSP has no solution, since AC-3 found values to remove
DBacktracking search is no longer needed because propagation has found the solution
Arc consistency means that every remaining value in every variable's domain has at least one compatible value in each neighboring variable's domain. This is a necessary but not sufficient condition for a solution. A CSP can be arc-consistent and still have no solution — arc consistency only checks pairs of variables, missing contradictions involving three or more variables simultaneously. This is the most important misconception about constraint propagation: ensuring consistency is not the same as finding or guaranteeing a solution.
Question 2 Multiple Choice
In AC-3, when a value is removed from a variable X's domain, what happens next?
AThe algorithm terminates and reports that the problem may be unsolvable
BThe algorithm immediately backtracks to a previous variable assignment
CAll arcs pointing TO variable X are re-added to the processing queue
DAll constraints involving X are checked once and then discarded
When a value is removed from X's domain, it may make previously consistent values in X's neighbors inconsistent — because those neighbors were consistent assuming X's full domain was available. To catch these newly created inconsistencies, AC-3 re-adds all arcs pointing to X (i.e., from X's neighbors to X) to the queue. This cascading re-check is what makes AC-3 a complete arc-consistency enforcer rather than a single-pass filter. Without it, some inconsistencies would slip through.
Question 3 True / False
Arc consistency (AC-3) can sometimes solve a CSP entirely, without any backtracking search.
TTrue
FFalse
Answer: True
In well-constrained problems like easy Sudoku puzzles, propagating arc consistency after each deduction can eliminate all but one value from every variable's domain, effectively solving the puzzle. Each time a cell's value is determined, constraint propagation removes that value from all cells in the same row, column, and box — which may force other cells, which propagate further. Hard Sudoku puzzles cannot be solved this way and require search, but they still benefit from propagation dramatically reducing the search space.
Question 4 True / False
Constraint propagation guarantees that if a CSP has a solution, AC-3 will find it.
TTrue
FFalse
Answer: False
Constraint propagation ensures consistency — it removes values that provably cannot be in any solution — but it does not find solutions. After propagation, backtracking search is typically still needed to make assignments and explore the reduced space. Moreover, if propagation empties any variable's domain, it proves there is NO solution — but propagation running to completion without emptying a domain does not prove a solution exists. The combination of constraint propagation with backtracking is what provides both efficiency and completeness.
Question 5 Short Answer
What is the difference between arc consistency and satisfiability in the context of CSPs, and why does this distinction matter for algorithm design?
Think about your answer, then reveal below.
Model answer: Arc consistency is a local property: variable X is arc-consistent with Y if every value in X's domain has at least one compatible value in Y's domain. A CSP is arc-consistent if all arcs have this property. Satisfiability means a complete assignment exists that satisfies all constraints simultaneously. A CSP can be arc-consistent but unsatisfiable — arc consistency only checks pairs of variables, not combinations of three or more. This matters because it tells us constraint propagation is an inference tool that prunes the search space, not a solver that replaces search.
Algorithm designers use this distinction to avoid the 'propagation always works' misconception. AC-3 is fast (polynomial) but incomplete — it may leave work for backtracking to do. Stronger consistency checks (path consistency, k-consistency) catch more but cost more. The practical design choice is to use cheap arc consistency as an inference engine within backtracking search, running propagation after each assignment and backtracking when any domain empties.