Constraint propagation

Constraint propagation repeatedly removes variable values incompatible with local consequences of a constraint satisfaction problem. The goal is to reduce the remaining search while preserving all genuine solutions. For $X<Y$ with domains $\{1,2\}$, enforcing support removes two from $X$ and one from $Y$, leaving the forced pair $(1,2)$. Arc consistency checks support across binary constraints; dedicated global-constraint propagators can reason about larger sets together. Reaching a propagation fixed point does not generally prove that the whole problem has a solution, because locally supported choices can still conflict globally.

Repeatedly apply a constraint propagation operation that only deletes values from finite constraint domains, preserves their order, and preserves every valid assignment. The sum of domain sizes is a nonnegative loop variant at every changing step, so repetition reaches a fixed point. For $N$ initial candidate values there are at most $N$ changing steps. An empty domain proves failure; a non-singleton fixed point may still require backtracking or explicit enumeration. Preservation of solutions, rather than mere deletion, is essential.