Constraint Satisfaction Problems Questions and Answers

Answer: A

A constraint problem gives a set of variables, a domain of permitted values for each and a set of constraints restricting which combinations are allowed, and a solution is an assignment satisfying all of them. The classical search formulation is different, and rules and objectives belong to other frameworks. Adopting a representation in which the structure of a problem is visible, rather than hidden inside a successor function, is what makes the specialised algorithms possible.

Answer: B

Because the state is described by variables, an algorithm can detect that a partial assignment already violates a constraint and discard every completion of it at once, which an atomic representation cannot express. The space is the same size, search is still required and the problems remain NP hard in general. Recognising that the gain comes from the representation rather than from any cleverness in the algorithm connects this topic directly to the earlier discussion of state representations.

Answer: C

Drawing a node for each variable and an edge for each binary constraint exposes the structure of the problem, and that structure determines which algorithms will be efficient. A tree shaped graph is solvable in linear time, and a nearly tree shaped one is nearly as easy. Search trees, statistics and domain contents are different objects. Making the structure of a problem visible so that it can be exploited is the practical reason for drawing the graph at all.

Answer: D

A global constraint such as all different relates any number of variables and has a specialised propagation algorithm far stronger than decomposing it into pairwise inequalities. It need not involve every variable, and it can in principle be decomposed, though at a heavy loss of propagation strength. Providing an efficient algorithm for a commonly occurring pattern, rather than expressing it in primitives, is what makes constraint programming systems practical.

Answer: A

Three variables each with the same two valued domain are pairwise satisfiable but cannot all differ, and only a global algorithm using matching theory detects that immediately. Readability and storage are genuine but minor benefits. The example is the standard demonstration that decomposition loses information, and it justifies the whole apparatus of specialised global constraints in constraint programming systems.

Answer: B

Backtracking chooses an unassigned variable, tries each value consistent with the assignment so far and recurses, returning when no value works. It is depth first search specialised to this representation, and its memory is linear. Backward search, restarts and recording failures describe other techniques, the last being no-good learning. A basic algorithm that is transformed by the heuristics layered on it is the pattern of this whole topic.

Answer: C

Choosing the most constrained variable first means failure is detected as early as possible, pruning the tree near the root where the saving is greatest. It is often called the fail first heuristic for that reason. Constraint counts are the degree heuristic, value selection is a separate decision, and recency is not used. Ordering so that failure comes early, rather than late, is counter-intuitive until one notices that the cost of failure grows with the depth at which it occurs.

Answer: D

The subtree below a node grows exponentially with its depth, so discovering an inconsistency at depth two removes vastly more work than discovering it at depth twenty. That is the whole justification for the fail first principle. Detection cost is comparable, termination follows from finding a solution rather than a failure, and reordering happens regardless. Attacking the exponential where it is largest is the same reasoning that makes move ordering matter in game search.

Answer: A

Assigning the variable that constrains most others reduces the branching factor of the remaining problem fastest, and it is normally used to break ties in the minimum remaining values heuristic rather than on its own. Domain size is the remaining values measure, value selection is separate and distance is not used. Two heuristics used together, one primary and one for ties, is a common and effective arrangement.

Answer: B

Having chosen a variable, trying the value that leaves the most flexibility elsewhere makes a solution more likely to be found without backtracking. Note that it runs opposite to the variable heuristic: choose the most constrained variable but the least constraining value. That asymmetry is not accidental, since one seeks to detect failure early and the other to avoid causing it, and noticing the difference is what makes both memorable.