Constraint Satisfaction Problems Questions and Answers

Q: What is the n queens problem as a constraint problem?

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.

Q: Why is the column per variable model better than one variable per square?

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.

Q: What is a sudoku puzzle as a constraint problem?

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.

Q: Why do most published sudoku puzzles require no search?

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.

Q: What does it mean that a puzzle requires search?

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.

Q: What is the overall message of the constraint satisfaction topic?

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.

Q: What is a binary constraint network?

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.

Q: How is a ternary constraint converted to binary form?

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.

Q: What is the dual encoding of a constraint problem?

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.

Q: Why might a modeller try more than one encoding of the same problem?

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.

81.

What is the n queens problem as a constraint problem?

A.Each column is a variable whose value is the row of its queen
B.Each square is a variable that is either occupied or empty
C.Each queen is a constraint on the positions of the others
D.The whole board is a single variable over all possible placements

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.

Discuss in Forum

82.

Why is the column per variable model better than one variable per square?

A.It reduces the number of solutions the problem has
B.It builds a constraint into the representation and has fewer variables
C.It allows the problem to be solved without any search at all
D.It produces a tree structured constraint graph

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.

Discuss in Forum

83.

What is a sudoku puzzle as a constraint problem?

A.The grid is one variable whose domain is every completed grid
B.Digits are variables whose values are the cells they occupy
C.Cells are variables with all different constraints on rows, columns and boxes
D.Rows are variables whose domains are the permutations of the digits

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.

Discuss in Forum

84.

Why do most published sudoku puzzles require no search?

A.The puzzles are constructed to have very many solutions
B.The search space is small enough to enumerate completely
C.The constraint graph of sudoku is tree structured
D.Propagation on the all different constraints determines every cell

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.

Discuss in Forum

85.

What does it mean that a puzzle requires search?

A.No further value can be deduced without assuming one
B.The puzzle has more than one distinct solution
C.The puzzle contains a contradiction somewhere
D.The propagation algorithm has been implemented incorrectly

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.

Discuss in Forum

86.

What is the overall message of the constraint satisfaction topic?

A.Constraint problems are always solvable in polynomial time
B.Structure in the representation can be exploited by inference
C.Backtracking search is sufficient for problems of any size
D.Local search should be preferred for every kind of practical problem

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.

Discuss in Forum

87.

What is a binary constraint network?

A.A network in which every variable has exactly two neighbours
B.A representation storing each constraint as two directed arcs
C.A problem in which every constraint relates exactly two variables
D.A problem whose variables all have two valued domains

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.

Discuss in Forum

88.

How is a ternary constraint converted to binary form?

A.By splitting it into three separate pairwise constraints
B.By deleting one of the three variables it involves
C.By ordering the three variables and constraining adjacent pairs
D.By introducing a new variable whose values are the allowed triples

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.

Discuss in Forum

89.

What is the dual encoding of a constraint problem?

A.Constraints become variables and shared variables become constraints
B.Variables become constraints and their domains become variables
C.The problem is stated with every constraint negated
D.Each variable is duplicated so that two copies must agree

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.

Discuss in Forum

90.

Why might a modeller try more than one encoding of the same problem?

A.The choice determines which programming language is required
B.Different encodings propagate with very different strength
C.One encoding may have solutions the other lacks entirely
D.Encodings differ in whether they can be solved at all

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.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Constraint Satisfaction Problems Questions and Answers || Constraint Satisfaction Problems MCQ Questions and Answers || Constraint Satisfaction Problems GK Questions and Answers || Constraint Satisfaction Problems GK MCQ Questions || Constraint Satisfaction Problems Multiple Choice Questions and Answers || Constraint Satisfaction Problems GK || GK on Constraint Satisfaction Problems || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Constraint Satisfaction Problems Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications