Constraint Satisfaction Problems Questions and Answers

Answer: A

Making one variable per column, with the row as its value, builds the column constraint into the representation and leaves only the row and diagonal constraints to state. The square by square model has far more variables and propagates worse. Constraints are not variables, and a single variable discards all structure. Encoding part of the problem into the representation, so that it cannot be violated at all, is one of the most effective modelling techniques available.

Answer: B

With one queen per column guaranteed by construction, that whole family of constraints vanishes and the search space falls from two to the n squared to n to the n. Search is still required, the graph remains complete, and the solutions are the same. Choosing a representation in which an invariant holds automatically, rather than being enforced, is a move worth looking for in every modelling problem.

Answer: C

The natural model gives each cell a variable over the digits, with twenty seven all different constraints for the rows, columns and boxes, and arc consistency on those global constraints solves most published puzzles without any search. Permutation and whole grid models propagate far worse, and inverting cells and digits is awkward. That a well modelled puzzle is solved by propagation alone is the clearest possible demonstration of what inference contributes.

Answer: D

Puzzles intended for humans are designed so that each step follows by elimination, which is exactly what constraint propagation performs, so the fixed point is the solution. Harder puzzles requiring case analysis do need search. Solutions are unique by convention, the space is large, and the graph is far from a tree. A puzzle designed to be solvable by local deduction is solvable by a propagator for the same reason, which makes it an unusually clean illustration.

Answer: A

When propagation reaches its fixed point with some domains still holding several values, the solver must assume a value and see whether it leads to a contradiction, which is exactly the case analysis a human solver resorts to. Multiple solutions, contradictions and bugs are different situations. The boundary between what deduction settles and what requires assumption is precisely the boundary between inference and search, and seeing it in a familiar puzzle makes it concrete.

Answer: B

Everything in the topic follows from using a factored representation in which constraints are visible, so that inference can prune before search rather than only during it. Plain backtracking is hopeless on real instances, local search cannot prove unsatisfiability, and the problems remain NP hard. That a change of representation, rather than a cleverer algorithm, unlocks the whole apparatus is the lesson worth carrying forward to the topics that follow.

Answer: C

A binary network has only pairwise constraints, so the constraint graph captures the problem completely and every result about graph structure applies directly. Boolean domains, degree two graphs and arc representations are different notions, though the last is how such networks are usually stored. Restricting to the binary case is what makes the connection between graph structure and algorithmic difficulty exact rather than approximate.

Answer: D

The dual encoding creates a variable whose domain is the set of satisfying tuples and constrains it to agree with each original variable, which preserves the solutions exactly. Splitting into pairs loses information, deletion changes the problem, and ordering constrains too little. A transformation that is exact but expensive is worth knowing as a theoretical device even where a specialised propagator would be used instead.

Answer: A

In the dual, each original constraint becomes a variable whose domain is its satisfying tuples, and two such variables are constrained to agree wherever they share an original variable. It converts any problem to binary form at the cost of large domains. Negation and duplication describe different transformations. Two encodings of the same problem, with different propagation behaviour, is a choice that a modeller can exploit deliberately.

Answer: B

Solutions correspond exactly between valid encodings, but the inferences a solver can draw differ enormously, and a problem intractable in one formulation may be easy in another. Trying two or three encodings is normal practice in industrial modelling. Solvability and language are unaffected. That two logically equivalent statements of a problem can differ by orders of magnitude in solving time is the most surprising and most practically important fact in the subject.