Constraint Satisfaction Problems Questions and Answers

Answer: A

Subtracting the removed values from the domain gives:

\[ 6 - 4 = 2 \]

so 2 values remain, and the variable becomes a strong candidate for the minimum remaining values heuristic. Had all six been removed the search would backtrack immediately. Tracking domain sizes is what allows the ordering heuristic to be computed at no extra cost, since propagation has already done the work.

Answer: B

An empty domain means no value can be given to that variable under the current partial assignment, so the assignment cannot be extended to a solution and the search backtracks at once. Detecting that early is the whole point of forward checking. Defaults, constraint removal and restoration would each break correctness. Recognising a proof of failure, and acting on it immediately, is the mechanism by which inference saves search.

Answer: C

The domain lists the permitted values, and propagation works by deleting values from domains until either a solution is evident or a domain empties. Constraint membership and neighbourhood are properties of the graph, and graph regions are a structural notion. Keeping the three vocabularies apart, values, constraints and structure, is what allows a description of an algorithm to be read without ambiguity.

Answer: D

A unary constraint restricts one variable's domain and is applied once at the start, achieving node consistency. Binary constraints relate pairs and higher arity constraints relate more. The other options describe a cardinality condition, a special case and a timing property. Classifying constraints by how many variables they involve determines which consistency condition applies to them, which is why the arity is the first thing noted about a constraint.

Answer: A

A higher arity constraint can be encoded with auxiliary variables into binary form, so the theory developed for the binary case covers everything in principle. In practice the encoding weakens propagation badly, which is why global constraints with their own propagators exist. Real problems abound in global constraints, propagation is not restricted to binary, and decomposition weakens rather than strengthens. A theoretical reduction that is a practical disaster is worth knowing about in both capacities.

Answer: B

The set of solutions is unchanged, but the solver can no longer reason about the constraint as a whole and misses inferences the specialised propagator would make, as the three variables with two values example shows for all different. Satisfiability is preserved, variables increase, and checking is unaffected. A transformation that preserves meaning while destroying inference is a trap that only appears once propagation strength is being considered.

Answer: C

A propagator examines the current domains and deletes values for which no support exists within its own constraint, leaving the rest to other propagators. Checking, enumeration and decomposition are different operations. The whole solver is a collection of such propagators run to a fixed point interleaved with search. Local reasoning by each constraint, combined into a global effect by iteration, is the architecture that makes the approach modular and extensible.

Answer: D

Propagation runs until no propagator can make any further deduction, and that fixed point is the state in which search resumes. Reaching it is guaranteed because domains only shrink and are finite. Complete assignment, singleton domains and individual satisfaction are different events. An iterative process guaranteed to terminate because a finite quantity decreases monotonically is a pattern worth recognising, since it makes the termination argument immediate.

Answer: A

Since every propagation step removes at least one value from a finite domain and nothing is ever added, the process cannot continue indefinitely. That monotonicity is what makes the fixed point well defined. Constraint counts, call limits and iteration caps are implementation details rather than the reason. Establishing termination from a decreasing finite measure is the standard argument for any such algorithm and it is worth constructing rather than assuming.

Answer: B

Because each propagator only removes values that no solution could use, the final domains are the same whatever order the propagators run in, which means the implementation is free to schedule them for efficiency. Solution counts, singleton domains and prescribed orders are different matters. Confluence of a rewriting process, meaning the order does not affect the result, is what allows the scheduling to be treated purely as an optimisation.