2.7 An Example

To see the outlined propagate and distribute method at a concrete example, consider the problem specified by the following constraints:

$\begin{array}{c} X\neq7 \qquad Z\neq2 \qquad X-Z = {3\cdot Y} \\ X\in1\#8 \qquad Y\in1\#10 \qquad Z\in1\#10 \end{array}$

To solve the problem, we start with a space whose store constrains the variables , , and Z to the given domains. We also create three propagators imposing the constraints $X\neq7$ , $Z\neq2$ , and $X-Z={3\cdot Y}$ . We assume that the propagator for $X-Z={3\cdot Y}$ realizes interval propagation, and that the propagators for the disequations $X\neq7$ and $Z\neq2$ realize domain propagation.

The propagators for the disequations immediately write all their information into the store and disappear. The store then knows the domains

$X\in[1\#6\;\;8] \qquad Y\in1\#10 \qquad Z\in[1\;\;3\#10]$

where $[1\;\;3\#10]$ denotes the finite domain $\{1\}\cup\{3,\ldots,10\}$ . The interval propagator for $X-Z = {3\cdot Y}$ can now further narrow the domains to

$X\in[4\#6\;\;8] \qquad Y\in1\#2 \qquad Z\in[1\;\;3\#5].$

Now the space is stable but neither failed nor solved. Thus, we continue with a first distribution step. We choose to distribute with the constraint X=4 . Figure 2.2 shows the resulting search tree.

Figure 2.2: A search tree containing 3 choice nodes, 1 failure node, and 3 solution nodes.

The space obtained by adding a propagator for X=4 can be solved by propagation and yields the solution

$X=4 \qquad Y=1 \qquad Z=1$

The space obtained by adding a propagator for $X\neq4$ becomes stable immediately after this propagator has written its information into the constraint store, which then looks as follows:

$X\in[5\#6\;\;8] \qquad Y\in1\#2 \qquad Z\in[1\;\;3\#5]$

This time we distribute with respect to the constraint X=5 .

The space obtained by adding a propagator for X=5 fails since $X-Z={3\cdot Y}$ is inconsistent with the store obtained by adding X=5 .

The space obtained by adding a propagator for $X\neq5$ becomes stable immediately after this propagator has written its information into the constraint store, which then looks as follows:

$X\in[6\;\;8] \qquad Y\in1\#2 \qquad Z\in[1\;\;3\#5]$

Now we distribute with respect to the constraint X=6 .

The space obtained by adding a propagator for X=6 can be solved by propagation and yields the solution

$X=6 \qquad Y=1 \qquad Z=3$

Finally, the space obtained by adding a propagator for $X\neq6$ can also be solved by propagation, yielding the third and final solution

$X=8 \qquad Y=1 \qquad Z=5$

An alternative to the propagate and distribute method is a naive enumerate and test method, which would enumerate all triples (X,Y,Z) admitted by the initial domain constraints and test the constraints $X\neq7$ , $Z\neq2$ , and $X-Z={3\cdot Y}$ for each triple. There are 8*10*10=800 candidates. This shows that constraint propagation can reduce the size of the search tree considerably.