Constraint Satisfaction Problems Questions and Answers

Answer: C

Every propagation step costs time at every node of the search tree, and pays only if it removes more work than it consumes, so the right level depends on how constrained the problem is. Tightly constrained problems reward strong propagation and loosely constrained ones do not. The two are combined in every practical solver, and inference alone rarely suffices. Recognising the trade as a genuine one, rather than assuming more inference is better, is what allows a solver to be tuned to a problem class.

Answer: D

Backtracking search can commit early to a poor branch and spend an enormous time in it, and restarting with different randomised choices, while keeping the learned no-goods, escapes that. Geometric or Luby schedules govern when to restart. Queue management, reordering and warm starting are different mechanisms. Abandoning work that is going badly, while retaining what was learned from it, converts a heavy tailed runtime distribution into a manageable one.

Answer: A

Without learning a restart would repeat the same work, but with the recorded no-goods the search is genuinely further forward and avoids the region that caused the trouble. Together the two techniques transformed satisfiability solving. Memory rises, the space is not provably smaller, and termination is not guaranteed sooner. Two techniques that are each modest alone and transformative together are worth noticing as a pair rather than individually.

Answer: B

Backtracking searches often show a distribution in which most runs finish quickly and a few take orders of magnitude longer, dominated by unlucky early choices. Restarts truncate the tail and dramatically improve the expected time. Uniformity, skew towards short runs and asymptotic growth are different phenomena. A distribution whose mean is dominated by rare extreme cases calls for a quite different response from one that is merely slow on average.

Answer: C

That pattern is the signature of a heavy tail caused by unlucky early branching, and restarting with different random choices while keeping the learned no-goods truncates it directly. Stronger propagation helps generally but does not address the tail, model size is fixed by the problem, and local search would lose the ability to prove unsatisfiability. Matching the remedy to the shape of the runtime distribution, rather than to its average, is the diagnostic skill here.

Answer: D

A local search that fails to find a solution has established only that it did not find one, since it never enumerates the space and may simply have looked in the wrong region. Systematic search with propagation can exhaust the space and prove absence. Constraint evaluation and initialisation are unaffected. That a negative result from an incomplete method carries no information is the same point made about incomplete search algorithms generally, and it decides which family a problem requiring a proof must use.

Answer: A

Verification, planning and design problems frequently require a proof that no solution exists, and only a complete method can supply one. Size, constraint arity and domain size affect which method is faster rather than which is capable. Asking what must be concluded from a negative result, before choosing a method, is a question that settles the choice immediately and is easily overlooked when only positive results are anticipated.

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.