Constraint Propagation: Domain Reduction by Inference

A constraint satisfaction problem assigns each variable a value from its domain so that all constraints hold. Before searching for a solution, we can shrink the problem by removing values that cannot participate in any solution.

Given a binary constraint $C(X, Y)$, a value $v \in \text{dom}(X)$ has support in $\text{dom}(Y)$ if there exists some $w \in \text{dom}(Y)$ such that $C(v, w)$ is true. A value with no support cannot appear in any solution, so we may safely remove it from $\text{dom}(X)$. This pruning step is called domain reduction by inference.

To illustrate, let $\text{dom}(X) = \{1, 2, 3, 4, 5, 6\}$ and $\text{dom}(Y) = \{2, 3\}$, with constraint $X < Y$. For each candidate $x \in \text{dom}(X)$, we check whether some $y \in \text{dom}(Y)$ satisfies $x < y$:

$$\begin{array}{l}x = 1{:}\ 1 < 2 \checkmark \\ x = 2{:}\ 2 < 3 \checkmark \\ x = 3{:}\ 3 < 2\text{ and }3 < 3\text{ both fail. Prune.} \\ x = 4, 5, 6{:}\ \text{no }y \in \{2,3\}\text{ exceeds them. Prune.}\end{array}$$

After pruning, $\text{dom}(X) = \{1, 2\}$.