conditions all require that all consistent partial evaluations can be extended to another variable in such a way that the resulting assignment is consistent. A partial evaluation is consistent if it satisfies all constraints whose scope is a subset of the assigned variables. Node consistency Node consistency requires that every unary constraint on a variable is satisfied by all values in the domain of the variable, and vice versa. This condition can be trivially enforced by reducing the domain of each variable to the values that satisfy all unary constraints on that variable. As a result, unary constraints can be neglected and assumed incorporated into the domains. For example, given a variable with a domain of and a constraint , node consistency would restrict the domain to and the constraint could then be discarded. This pre-processing step simplifies later stages. Arc consistency A variable of a constraint satisfaction problem is arc-consistent with another one if each of its admissible values are consistent with some admissible value of the second variable. Formally, a variable is arc-consistent with another variable if, for every value in the domain of there exists a value in the domain of such that satisfies the binary constraint between and . A problem is arc consistent if every variable is arc consistent with every other one. For example, consider the constraint where the variables range over the domain 1 to 3. Because can never be 3, there is no arc from 3 to a value in so it is safe to remove. Likewise, can never be 1, so there is no arc, therefore it can be removed. Arc consistency can also be defined relative to a specific binary constraint: a binary constraint is arc-consistent if every value of one variable has a value of the second variable such that they satisfy the constraint. This definition of arc consistency is similar to the above, but is given specific to a constraint. This difference is especially relevant for non-normalized problems, where the above definition would consider all constraints between two variables while this one considers only a specific one. If a variable is not arc consistent with another one, it can be made so by removing some values from its domain. This is the form of constraint propagation that enforces arc consistency: it removes, from the domain of the variable, every value that does not correspond to a value of