Constraint Satisfaction Problems Questions and Answers

Q: A variable has 6 values and forward checking removes 4. How many remain?

Subtracting the removed values from the domain gives:\[ 6 - 4 = 2 \]so 2 values remain, and the variable becomes a strong candidate for the minimum remaining values heuristic. Had all six been removed the search would backtrack immediately. Tracking domain sizes is what allows the ordering heuristic to be computed at no extra cost, since propagation has already done the work.

Q: What happens when forward checking empties a domain?

An empty domain means no value can be given to that variable under the current partial assignment, so the assignment cannot be extended to a solution and the search backtracks at once. Detecting that early is the whole point of forward checking. Defaults, constraint removal and restoration would each break correctness. Recognising a proof of failure, and acting on it immediately, is the mechanism by which inference saves search.

Q: What is the domain of a variable in a constraint problem?

The domain lists the permitted values, and propagation works by deleting values from domains until either a solution is evident or a domain empties. Constraint membership and neighbourhood are properties of the graph, and graph regions are a structural notion. Keeping the three vocabularies apart, values, constraints and structure, is what allows a description of an algorithm to be read without ambiguity.

Q: What is a unary constraint?

A unary constraint restricts one variable's domain and is applied once at the start, achieving node consistency. Binary constraints relate pairs and higher arity constraints relate more. The other options describe a cardinality condition, a special case and a timing property. Classifying constraints by how many variables they involve determines which consistency condition applies to them, which is why the arity is the first thing noted about a constraint.

Q: Why are binary constraints given special attention?

A higher arity constraint can be encoded with auxiliary variables into binary form, so the theory developed for the binary case covers everything in principle. In practice the encoding weakens propagation badly, which is why global constraints with their own propagators exist. Real problems abound in global constraints, propagation is not restricted to binary, and decomposition weakens rather than strengthens. A theoretical reduction that is a practical disaster is worth knowing about in both capacities.

Q: What is the effect of encoding a global constraint as binary constraints?

The set of solutions is unchanged, but the solver can no longer reason about the constraint as a whole and misses inferences the specialised propagator would make, as the three variables with two values example shows for all different. Satisfiability is preserved, variables increase, and checking is unaffected. A transformation that preserves meaning while destroying inference is a trap that only appears once propagation strength is being considered.

Q: What does a propagator for a constraint do?

A propagator examines the current domains and deletes values for which no support exists within its own constraint, leaving the rest to other propagators. Checking, enumeration and decomposition are different operations. The whole solver is a collection of such propagators run to a fixed point interleaved with search. Local reasoning by each constraint, combined into a global effect by iteration, is the architecture that makes the approach modular and extensible.

Q: What is a fixed point in constraint propagation?

Propagation runs until no propagator can make any further deduction, and that fixed point is the state in which search resumes. Reaching it is guaranteed because domains only shrink and are finite. Complete assignment, singleton domains and individual satisfaction are different events. An iterative process guaranteed to terminate because a finite quantity decreases monotonically is a pattern worth recognising, since it makes the termination argument immediate.

Q: Why does propagation always terminate?

Since every propagation step removes at least one value from a finite domain and nothing is ever added, the process cannot continue indefinitely. That monotonicity is what makes the fixed point well defined. Constraint counts, call limits and iteration caps are implementation details rather than the reason. Establishing termination from a decreasing finite measure is the standard argument for any such algorithm and it is worth constructing rather than assuming.

Q: What does it mean that propagation reaches a unique fixed point?

Because each propagator only removes values that no solution could use, the final domains are the same whatever order the propagators run in, which means the implementation is free to schedule them for efficiency. Solution counts, singleton domains and prescribed orders are different matters. Confluence of a rewriting process, meaning the order does not affect the result, is what allows the scheduling to be treated purely as an optimisation.

61.

A variable has 6 values and forward checking removes 4. How many remain?

A.2
B.4
C.6
D.10

Answer: A

Subtracting the removed values from the domain gives:

\[ 6 - 4 = 2 \]

so 2 values remain, and the variable becomes a strong candidate for the minimum remaining values heuristic. Had all six been removed the search would backtrack immediately. Tracking domain sizes is what allows the ordering heuristic to be computed at no extra cost, since propagation has already done the work.

Discuss in Forum

62.

What happens when forward checking empties a domain?

A.The domain is restored to its original contents and retried
B.The current assignment fails and the search backtracks
C.The variable is assigned a default value and the search continues
D.The constraint causing the emptying is removed from the problem

Answer: B

An empty domain means no value can be given to that variable under the current partial assignment, so the assignment cannot be extended to a solution and the search backtracks at once. Detecting that early is the whole point of forward checking. Defaults, constraint removal and restoration would each break correctness. Recognising a proof of failure, and acting on it immediately, is the mechanism by which inference saves search.

Discuss in Forum

63.

What is the domain of a variable in a constraint problem?

A.The set of variables it is constrained with
B.The region of the constraint graph containing it
C.The set of values it may take
D.The set of constraints in which it appears

Answer: C

The domain lists the permitted values, and propagation works by deleting values from domains until either a solution is evident or a domain empties. Constraint membership and neighbourhood are properties of the graph, and graph regions are a structural notion. Keeping the three vocabularies apart, values, constraints and structure, is what allows a description of an algorithm to be read without ambiguity.

Discuss in Forum

64.

What is a unary constraint?

A.One that must be satisfied exactly once in a solution
B.One relating a variable to a constant value only
C.One that can be checked before the search begins
D.One restricting the values of a single variable

Answer: D

A unary constraint restricts one variable's domain and is applied once at the start, achieving node consistency. Binary constraints relate pairs and higher arity constraints relate more. The other options describe a cardinality condition, a special case and a timing property. Classifying constraints by how many variables they involve determines which consistency condition applies to them, which is why the arity is the first thing noted about a constraint.

Discuss in Forum

65.

Why are binary constraints given special attention?

A.Any constraint can in principle be reduced to binary form
B.Most real problems contain only binary constraints
C.Binary constraints are the only ones that can be propagated
D.Binary constraints always propagate more strongly than others

Answer: A

A higher arity constraint can be encoded with auxiliary variables into binary form, so the theory developed for the binary case covers everything in principle. In practice the encoding weakens propagation badly, which is why global constraints with their own propagators exist. Real problems abound in global constraints, propagation is not restricted to binary, and decomposition weakens rather than strengthens. A theoretical reduction that is a practical disaster is worth knowing about in both capacities.

Discuss in Forum

66.

What is the effect of encoding a global constraint as binary constraints?

A.The constraint can no longer be checked for satisfaction
B.Propagation becomes much weaker although the semantics are preserved
C.The problem becomes unsatisfiable where it previously was not
D.The number of variables in the problem is reduced

Answer: B

The set of solutions is unchanged, but the solver can no longer reason about the constraint as a whole and misses inferences the specialised propagator would make, as the three variables with two values example shows for all different. Satisfiability is preserved, variables increase, and checking is unaffected. A transformation that preserves meaning while destroying inference is a trap that only appears once propagation strength is being considered.

Discuss in Forum

67.

What does a propagator for a constraint do?

A.Generates all the assignments that satisfy the constraint
B.Converts the constraint into a set of simpler constraints
C.Removes domain values that cannot appear in any solution of it
D.Checks whether the constraint is satisfied by a given assignment

Answer: C

A propagator examines the current domains and deletes values for which no support exists within its own constraint, leaving the rest to other propagators. Checking, enumeration and decomposition are different operations. The whole solver is a collection of such propagators run to a fixed point interleaved with search. Local reasoning by each constraint, combined into a global effect by iteration, is the architecture that makes the approach modular and extensible.

Discuss in Forum

68.

What is a fixed point in constraint propagation?

A.The point at which the search has assigned every variable
B.The value at which a variable's own domain becomes a singleton
C.The moment at which the first constraint becomes satisfied
D.The state in which no propagator can remove any further value

Answer: D

Propagation runs until no propagator can make any further deduction, and that fixed point is the state in which search resumes. Reaching it is guaranteed because domains only shrink and are finite. Complete assignment, singleton domains and individual satisfaction are different events. An iterative process guaranteed to terminate because a finite quantity decreases monotonically is a pattern worth recognising, since it makes the termination argument immediate.

Discuss in Forum

69.

Why does propagation always terminate?

A.Domains only shrink and are finite in size
B.The number of constraints is bounded in advance
C.Each propagator is called at most once per variable
D.A limit on the number of iterations is imposed

Answer: A

Since every propagation step removes at least one value from a finite domain and nothing is ever added, the process cannot continue indefinitely. That monotonicity is what makes the fixed point well defined. Constraint counts, call limits and iteration caps are implementation details rather than the reason. Establishing termination from a decreasing finite measure is the standard argument for any such algorithm and it is worth constructing rather than assuming.

Discuss in Forum

70.

What does it mean that propagation reaches a unique fixed point?

A.The propagators must always be applied in a fixed prescribed order
B.The result does not depend on the order propagators are applied
C.Only one solution to the problem can be reached from it
D.Exactly one variable is left with a singleton domain

Answer: B

Because each propagator only removes values that no solution could use, the final domains are the same whatever order the propagators run in, which means the implementation is free to schedule them for efficiency. Solution counts, singleton domains and prescribed orders are different matters. Confluence of a rewriting process, meaning the order does not affect the result, is what allows the scheduling to be treated purely as an optimisation.

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