Constraint propagation

Arc consistency

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 ${\displaystyle x_{3}}$ is arc consistent with ${\displaystyle x_{2}}$ but the algorithm reduces the domain of ${\displaystyle x_{2}}$, arc consistency of ${\displaystyle x_{3}}$ with ${\displaystyle x_{2}}$ does not hold any longer, and has to be enforced again.