Constraint Satisfaction Problems Questions and Answers

Answer: C

The variable must be assigned in any case, so it is best to discover quickly whether it can be, whereas the value is a free choice and should be the one most likely to succeed. Both follow from the same aim of minimising total work. Constraint type, algorithm family and convention are not the explanation. Two rules that appear contradictory until the asymmetry between a forced choice and a free one is noticed is a good test of whether a heuristic has been understood or merely memorised.

Answer: D

When a variable is assigned, forward checking deletes conflicting values from the domains of the variables it constrains, and backtracks immediately if any domain becomes empty. It catches failures much earlier than plain backtracking and supplies the domain sizes the minimum remaining values heuristic needs. Full consistency checks, deeper lookahead and feasibility proofs are different operations. Inference interleaved with search, rather than performed once at the start, is the organising idea of the whole topic.

Answer: A

Forward checking propagates only from the assigned variable to its neighbours, so two unassigned variables left with incompatible domains are not noticed until one of them is reached. Arc consistency propagates further and catches exactly that case. Direct violations and empty domains are precisely what it does detect. Knowing where a technique stops looking is what identifies the next technique in the sequence and explains why it exists.

Answer: B

An arc from X to Y is consistent when every remaining value of X has some value of Y consistent with it, and enforcing it across the whole problem deletes values no solution could use. Satisfaction concerns complete assignments, non-empty domains are weaker, and connectivity is a property of the graph. Defining a local property whose global enforcement prunes the search is the pattern every consistency notion follows.

Answer: C

AC-3 keeps a queue of arcs, revises each by deleting unsupported values, and re-queues the arcs pointing at any variable whose domain changed, terminating when the queue empties or a domain does. Its complexity is cubic in the number of variables for binary constraints. The other options misread the numeral. A worklist algorithm that reprocesses only what a change could have affected is a pattern common to many propagation problems.

Answer: D

Deleting a value from a domain may remove the support some neighbour was relying on, so every arc directed into the changed variable is put back on the queue. Re-queuing everything would be correct but wasteful. Constraint addition and assignment are different events. Revisiting only what a change can possibly have invalidated is what keeps an incremental algorithm efficient, and identifying that set precisely is the design work.

Answer: A

Arc consistency removes values that certainly cannot participate in a solution but does not establish that any complete assignment exists, and a problem may be arc consistent and have no solution at all. It is a necessary rather than a sufficient condition. Cycles do make the gap larger, since arc consistency is decisive for trees. A pruning technique that removes some failures and not all is still valuable, and knowing which it removes prevents it being trusted too far.

Answer: B

A tree structured problem can be made arc consistent in one sweep from the leaves and then solved without any backtracking at all, in time linear in the number of variables. That is why identifying or creating tree structure is so valuable. Complete graphs are the hardest case, domain uniformity is irrelevant and a single cycle already breaks the guarantee. A structural property that converts an exponential problem into a linear one is worth checking for before any search is attempted.

Answer: C

Choosing a root, ordering the variables so that every parent precedes its children, making each arc from parent to child consistent in reverse order and then assigning forward gives a solution with no backtracking. The work is linear in the variables and quadratic in the domain size. Enumeration, repeated propagation and graph completion are unnecessary or harmful. An algorithm exploiting a structural property directly is far better than a general one applied to a structured instance.

Answer: D

If deleting a few variables leaves a tree, every assignment to that cycle cutset can be tried and the remaining tree solved in linear time, giving a cost exponential only in the cutset size. Finding the smallest cutset is itself hard, so a heuristic is used. Partitioning, constraint removal and domain conditioning are different techniques. Reducing an exponential in the problem size to one in a structural parameter is the central idea of parameterised algorithms.