the other variable. This transformation maintains the problem solutions, as the removed values are in no solution anyway. Constraint propagation can make the whole problem arc consistent by repeating this removal for all pairs of variables. This process might have to consider a given pair of variables more than once. Indeed, removing values from the domain of a variable may cause other variables to become no longer arc consistent with it. For example, if is arc consistent with but the algorithm reduces the domain of , arc consistency of with does not hold any longer, and has to be enforced again. A simplistic algorithm would cycle over the pairs of variables, enforcing arc-consistency, repeating the cycle until no domains change for a whole cycle. The AC-3 algorithm improves over this algorithm by ignoring constraints that have not been modified since they were last analyzed. In particular, it works on a set of constraints that initially contains all of them; at each step, it takes a constraint and enforces arc-consistency; if this operation may have produced a violation of arc-consistency over another constraint, it places it back in the set of constraints to analyze. This way, once arc-consistency is enforced on a constraint, this constraint is not considered again unless the domain of one of its variables is changed. Path consistency Path consistency is a property similar to arc consistency, but considers pairs of variables instead of only one. A pair of variables is path-consistent with a third variable if each consistent evaluation of the pair can be extended to the other variable in such a way that all binary constraints are satisfied. Formally, and are path consistent with if, for every pair of values that satisfies the binary constraint between and , there exists a value in the domain of such that and satisfy the constraint between and and between and , respectively. The form of constraint propagation that enforces path consistency works by removing some satisfying assignment from a constraint. Indeed, path consistency can be enforced by removing from a binary constraint all evaluations that cannot be extended to another variable. As for arc consistency, this removal might have to consider a binary constraint more than once. As for arc consistency, the resulting problem has the same solutions of the original one, as the removed values are in no solution. The form of constraint propagation that enforces path consistency