X
assignment X
C
vars C  Q X    t vars C
conststent rel C
solution t X
partial con ststent solution empty P
P
P
P
Definition 2 (projection) Given a constraint C and a subset of variables S C vars C ,
the projection π S C is a constraint, where vars π S C    S and rel π S C
t S
t rel C
.

Definition 3 (selection) Given a constraint C and an assignment t to a subset of variables X ⊆ vars C , the selection σι C  is a constraint, where vars σι C      vars C   and rel σι C
ss
.

## 2.2 Local Consistency

inconsistency Definition 4 (arc consistency) Given a constraint C and a variable x    vars C , a value a    dom x  is is then called a if for each of the variables x    vars C  , and each of the values a    dom x  ,   x     a   is supported in C .  A CSP is if each of its constraints is arc consistent.

k Definition 5 (k-consistency) A CSP is k-consistent if and only if given any consistent partial solution over k -   distinct variables, there exists an instantiation of any k th variable such that the partial solution plus that instantiation is consistent. A CSP is strongly kconsistent if it is j-consistent for all   < j < k.