
is a set of constraints specifying allowable combinations of values for subsets of variables.
goal test

A state _______ or _______ a black box with no internal structure.
atomic, or indivisible

defined by variables Xi with values from domain Di–factored representation.
state:

A constraint satisfaction problem consists of three elements:
 A set of variables,X=X1, X2, Xn
 A set of domains for each variable:D=D1, D2, Dn
 A set of constraints Ct

We call a solution
consistent assignment

CSP Algorithms: Algorithm can do two things:
 Search: choose a new variable assignment from many possibilities
 Inference: constraint propagation, use the constraints to spread the word: reduce the number of values for a variable which will reduce the legal values of other variables etc.

Types of Consistency
 Nodeconsistency (unary constraints)
 Arcconsistency (binary constraints)
 Pathconsistency (nary constraints)

A variable Xi is nodeconsistent if all the values of Domain(Xi) satisfy all unary constraints.
Nodeconsistency (unary constraints)

X−> Y is arcconsistent if and only if every value x of X is consistent with some value y of Y.
Arcconsistency

generalizes arcconsistency from binary to multiple constraints.
Pathconsistency (nary constraints):

