Constraint Satisfaction Problems Questions and Answers

Answer: B

Such a system supplies a language for stating variables and constraints, propagators for the common global patterns, and search control that the modeller can direct. That combination is what makes industrial modelling practical. No guarantees of speed or structure are possible, and whether a model captures the intent remains the modeller's responsibility. A tool that makes the right things easy to say, rather than one that promises to solve everything, is what a mature framework offers.

Answer: C

The same problem can be modelled in ways that differ by orders of magnitude in solving time, chiefly according to whether the constraints chosen propagate strongly, and practitioners consistently report that modelling dominates every other consideration. Algorithm choice, variable count and language are secondary. That the formulation matters more than the solver echoes the lesson from ordinary search that reformulating a problem beats optimising the search over it.

Answer: D

Each variable independently takes any of its values, so the count is:

\[ 5^{20} \approx 9.5 \times 10^{13} \]

which is 5 to the 20. That figure is why enumeration is hopeless and why propagation matters so much. Computing the size of the space before choosing a method takes a moment and immediately rules out the naive approaches, which is exactly the estimate that should precede any implementation.

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.