Constraint Satisfaction Problems Questions and Answers

Answer: A

The first two are correct. Forward checking propagates only from the newly assigned variable to its neighbours, so an inconsistency between two unassigned variables is missed until one is reached, and arc consistency is what catches it. Knowing precisely where each level of inference stops looking is what makes the progression from forward checking through arc consistency to path consistency a sequence rather than a list.

Answer: B

The first three guide systematic backtracking, choosing a variable then a value, while the fourth belongs to local search over complete assignments. Two heuristics choose variables and two choose values, and noticing which is which prevents them being confused. The variable heuristics seek early failure and the value heuristics seek to avoid it, which is the asymmetry that makes the set coherent.

Answer: C

The first three are correct. Min conflicts is a local search operating on complete assignments, repairing violations, rather than a systematic method building partial ones. The distinction matters because the two families have entirely different guarantees: systematic search can prove unsatisfiability while local search can only fail to find a solution, which is a much weaker statement.

Answer: D

Forward checking and the consistency conditions all deduce that certain values cannot appear in any solution and delete them. Least constraining value is an ordering heuristic that decides what to try first and deletes nothing. Separating inference, which shrinks the problem, from heuristics, which reorder the search, is the clearest way to organise the techniques, since the two can be combined freely.

Answer: A

Both are true and the second is the reason for the name. Because the subtree below a node grows exponentially with depth, detecting an inconsistency near the root removes far more work than detecting the same one deeper. Seeking failure rather than avoiding it is counter-intuitive until the exponential is taken into account, which makes this a good test of whether the complexity argument has been absorbed.

Answer: B

Node consistency is the weakest condition, requiring only that unary constraints be applied to each domain, which is done once at the start. Arc consistency handles binary constraints and path consistency triples. Graph connectivity, domain emptiness and pairwise assignment are different notions. A hierarchy of consistency conditions, each considering more variables at once, gives a scale on which the cost and the pruning power can be traded.

Answer: C

Path consistency looks at triples: for every consistent assignment to two variables there must be a value for a third consistent with both, which prunes more than arc consistency and costs considerably more. It is the k equal to three case of k consistency. Graph paths and traversal are different notions. Each step up the hierarchy considers one more variable and costs an order more work, which is why the higher levels are rarely enforced in full.

Answer: D

The general condition says that any consistent partial assignment of size k minus one can be extended to any further variable, with node, arc and path consistency being the cases of one, two and three. Strong n consistency for n variables permits a backtrack free solution but costs exponential effort to establish. Constraint arity, block assignment and domain size are different quantities. A parameterised family in which the extremes are trivial and intractable leaves the useful cases in the middle.

Answer: A

Enforcing consistency at every level up to the number of variables takes exponential time, so the theoretical prize of a backtrack free search is paid for in advance at the same price. In practice arc consistency, occasionally strengthened, is the sweet spot. Constraint arity, domain uniformity and solution knowledge are not the obstacle. A guarantee whose cost equals the cost of the thing it guarantees is a theoretical result rather than a practical technique, and recognising that is what keeps effort where it pays.

Answer: B

Arc consistency prunes substantially at a cost that is polynomial and modest, and specialised propagators for global constraints add strength where it is worth having. Node consistency alone is far too weak, and the higher levels cost more than they save on most problems. Finding the level of inference at which the pruning gained exceeds the effort spent is an empirical question whose answer has been remarkably stable across the field.