that values of lower-index variables are all consistent with values of higher-index ones. When choosing a value for a variable, values that are inconsistent with all values of an unassigned variable can be neglected. Indeed, even if these values are all consistent with the current partial evaluation, the algorithm will later fail to find a consistent value for the unassigned variable. On the other hand, enforcing consistency with variables that are already evaluated is not necessary: if the algorithm chooses a value that is inconsistent with the current partial evaluation, inconsistency is detected anyway. Assuming that the order of evaluation of the variables is , a constraint satisfaction problem is directionally arc consistent if every variable is arc consistent with any other variable such that . Directional path consistency is similar, but two variables have to be path consistent with only if . Strong directional path consistency means both directional path consistency and directional arc consistency. Similar definitions can be given for the other forms of consistency. Constraint propagation for arc and path consistency Constraint propagation enforcing directional arc consistency iterates over variables from the last to the first, enforcing at each step the arc consistency of every variable of lower index with it. If the order of the variables is , this algorithm iterates over variables from to ; for variable , it enforces arc consistency of every variable of index lower than with . Directional path consistency and strong directional path consistency can be enforced by algorithms similar to the one for arc consistency. They process variables from to ; for every variable two variables with are considered, and path consistency of them with is enforced. No operation is required if the problem contains no constraint on and or no constraint between and . However, even if there is no constraint between and , a trivial one is assumed. If constraint propagation reduces its set of satisfying assignments, it effectively create a new non-trivial constraint. Constraint propagation enforcing strong directional path consistency is similar, but also enforces arc consistency. Directional consistency and satisfiability Directional consistency guarantees that partial solutions satisfying a constraint can be consistently extended to another variable of higher index. However, it does not guarantee that the extensions to different variables are consistent with each other. For example, a partial solution may be consistently extended to variable or to variable , but yet these two extensions