these two evaluations may not be consistent with each other. However, constraint propagation can be used to prove satisfiability in some cases. A set of binary constraints that is arc consistent and has no empty domain can be inconsistent only if the network of constraints contains cycles. Indeed, if the constraints are binary and form an acyclic graph, values can always be propagated across constraints: for every value of a variable, all variables in a constraint with it have a value satisfying that constraint. As a result, a solution can be found by iteratively choosing an unassigned variable and recursively propagating across constraints. This algorithm never tries to assign a value to a variable that is already assigned, as that would imply the existence of cycles in the network of constraints. A similar condition holds for path consistency. The special cases in which satisfiability can be established by enforcing arc consistency and path consistency are the following ones. enforcing arc consistency establishes satisfiability of problems made of binary constraints with no cycles (a tree of binary constraints); enforcing path consistency establishes satisfiability for binary constraints (possibly with cycles) with binary domains; enforcing strong consistency establishes satisfiability of problems containing variables. Special cases Some definitions or results about relative consistency hold only in special cases. When the domains are composed of integers, bound consistency can be defined. This form of consistency is based on the consistency of the extreme values of the domains, that is, the minimum and maximum values a variable can take. When constraints are algebraic or Boolean, arc consistency is equivalent to adding new constraint or syntactically modifying an old one, and this can be done by suitably composing constraints. Specialized constraints Some kinds of constraints are commonly used. For example, the constraint that some variables are all different are often used. Efficient specialized algorithms for enforcing arc consistency on such constraints exist. The constraint enforcing a number of variables to be different is usually written or alldifferent([X1,...,Xn]). This constraint is equivalent to the non-equality of all pairs of different variables, that is, for every . When the domain of a variable is reduced to a single value, this value can be removed from all other domains by constraint propagation when enforcing arc consistency. The use of the specialized constraint allows for exploiting properties that do not hold for individual binary disequalities. A first property is that the