7.2 Example: Pythagoras

Not all propagators exploit coreferences in products (e.g. $x\cdot x + y\cdot y = z\cdot z$ ). For the example of this section it will be essential to exploit such coreferences, and you will learn how to do it.

The example also illustrates the case where a propagator for a redundant constraint improves the performance of a script by decreasing the number of necessary propagation steps, but without significantly changing the search tree.

Problem Specification

How many triples (A,B,C) exist such that\ A^2+B^2=C^2 and $A\le B\le C\le 1000$ ?

Model

The model has three variables , , and . Each variable is constrained to the finite domain $1\#1000$ . The model imposes the constraints A^2+B^2=C^2 and $A\le B\le C$ .

The script will also create a propagator for the redundant constraint $2\cdot B^2\ge C^2$ .

Distribution Strategy

We distribute on the variables , , using the standard first-fail strategy.

proc {Square X S}
   {FD.times X X S}
end

proc {Pythagoras Root}
   [A B C] = Root
   AA BB CC
in 
   Root ::: 1#1000
   AA = {Square A}
   BB = {Square B}
   CC = {Square C}
   AA + BB =: CC
   A =<: B
   B =<: C
   2*BB >=: CC  % redundant constraint
   {FD.distribute ff Root}
end

Figure 7.2: A script that enumerates Pythagoras triples.

Script

Given the script in Figure 7.2, we can compute the number of different triples with the statement

{Browse {Length {SearchAll Pythagoras}}}

The script introduces a defined constraint

{Square X S}

saying that S is the square of X. This constraint is implemented with a propagator provided by

{FD.times X X S}

This propagator will start propagating as soon as the store constrains X to a finite domain. This in contrast to the propagator created by X*X=:S, which will start work only after both X and S are constrained to finite domains in the constraint store. To define Square with this constraint, we would have to write

proc {Square X S} {FD.decl S} X*X =: S end

The propagator for the redundant constraint does not significantly reduce the size of the search tree. However, it reduces the number of propagation steps from about 1000000 to about 500000, which makes computation twice as fast.

statistics

To find out about this, pop up the Oz Panel and reset the statistics. Also switch on the status message feature and pop up the emulator buffer. Now enter the statement

{Browse {Length {SearchAll Pythagoras}}}

and print the statistics after the execution of the statement has finished. This will show something like

solutions: 881 Variables created: 3 clones: 1488 Propagators created: 7 failures: 608 Propagator invocations: 490299

in the emulator buffer. Now remove the propagator for the redundant constraint from the definition of the script, redefine it, reset the statistics, run the statement, and print the statistics. This time you will see something like

solutions: 881 Variables created: 3 clones: 1878 Propagators created: 6 failures: 998 Propagator invocations: 1190397

If we drop the redundant constraint, it seems sensible to not have separate propagators for the squares but simply have one propagator created with

A*A + B*B =: C*C

Unfortunately, this will dramatically increase the size of the search tree. The reason for this increase is the fact that the created propagator does not realize the coreferences in the constraint it implements, that is, it treats the two occurrences of A, say, as if they were independent variables.