constraints. In particular, for every variable among the ones, the row relative to its value in the matrix representing the constraint relating it with the one represents the allowed values of the latter. Since these row are convex, and they have a common element pairwise because of path consistency, they also have a shared common element, which represents a value of the last variable that is consistent with the other ones. Uses of local consistency All forms of local consistency can be enforced by constraint propagation, which may reduce the domains of variables and the sets of assignments satisfying a constraint and may introduce new constraints. Whenever constraint propagation produces an empty domain or an unsatisfiable constraint, the original problem is unsatisfiable. Therefore, all forms of local consistency can be used as approximations of satisfiability. More precisely, they can be used as incomplete unsatisfiability algorithms, as they can prove that a problem is unsatisfiable, but are in general unable to prove that a problem is satisfiable. Such approximated algorithms can be used by search algorithms (backtracking, backjumping, local search, etc.) as heuristics for telling whether a partial solution can be extended to satisfy all constraints without further analyzing it. Even if constraint propagation does not produce an empty domain or an unsatisfiable constraint, it may nevertheless reduce the domains or strengthen the constraints. If this is the case, the search space of the problem is reduced, thus reducing the amount of search needed to solve the problem. Local consistency proves satisfiability in some restricted cases (see Complexity of constraint satisfaction#Restrictions). This is the case for some special kind of problems and/or for some kinds of local consistency. For example, enforcing arc consistency on binary acyclic problems allows for telling whether the problem is satisfiable. Enforcing strong directional -consistency allows telling the satisfiability of problems that have induced width according to the same order. Adaptive directional consistency allows telling the satisfiability of an arbitrary problem. See also Unit propagation Constraint programming Constraint logic programming Look-ahead (backtracking) External links Constraint Propagation - Dissertation by Guido Tack giving a good survey of theory and implementation issues References Constraint programming