Constraint Satisfaction Problems Questions and Answers

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.

Answer: C

Knowing the answer does not depend on the schedule frees the implementation to use priority queues, cheap propagators first and event driven wake up without affecting correctness. Propagators are called repeatedly, search order does affect which solution is found first, and fixed points are properties of states. A theoretical property that licenses an engineering freedom is exactly the kind worth establishing before optimising.

Answer: D

The variables are the unknowns of the problem, and a solution assigns a value from its domain to each of them consistently. Algorithm parameters, dynamic constraints and unassigned values are different notions. Deciding what the variables should be is the first modelling choice and it determines the whole structure of the constraint graph, so it repays more thought than it usually receives.

Answer: A

A solution gives every variable a value and violates nothing, whereas a consistent partial assignment is merely a node in the search that may or may not extend. The order of assignment is not part of the answer, and propagated domains are an intermediate state. Being precise about what constitutes an answer determines when the algorithm may stop, which is not always obvious in problems where partial progress looks like success.

Answer: B

An over constrained problem has no solution, and the practical response is usually to relax some constraints or to seek an assignment violating as few as possible, which turns it into an optimisation. Constraint counts and domain sizes are not the criterion, and multiple membership is normal. Recognising that a real problem stated as insoluble usually needs its requirements reconsidered, rather than a better solver, is the practically important response.

Answer: C

When a problem is over constrained, minimising the number of violated constraints, possibly weighted by importance, gives the best available compromise. Timetabling and staff rostering are typically posed this way from the start. Variable counts, unsatisfiability proofs and subproblem sizing are different questions. Converting an infeasible satisfaction problem into a feasible optimisation is how most real requirements are actually met.

Answer: D

Every stakeholder's preferences cannot usually be satisfied at once, so the requirement becomes the best available compromise with soft constraints weighted against one another. Optimisation is generally harder rather than easier, satisfaction can express preferences by encoding them as constraints, and constraints remain central. That a hard formulation must be softened before it matches what is actually wanted is a lesson learned repeatedly when a solver reports that no solution exists.

Answer: A

Soft constraints carry a penalty rather than a prohibition, so the solver minimises the total penalty while satisfying the hard constraints absolutely. That distinction between what must hold and what is merely preferred is essential in any real specification. Partial application, uncertainty and post hoc checking are different notions. Requiring a specification to state which of its requirements are negotiable is often the most useful question an analyst can ask.