15.2.2 FD-Propagators

Oz features several propagators for finite domain variables. We only present examples here and refer to the finite domain programming tutorial otherwise. The most important propagators are those for arithmetics. Propagators can be distinguished from pure evaluators by the colons like in =: or =<:.

3*X-Y  =: 4*Z  % linear arithmetics  
3*X-=<: 4*Z  % inequations

For each FD-variable, a finite domain of possible values is maintained in the constraint store. What these propagators are doing is to restrict the upper and lower bounds of the domains of its variables; values from the interior of a finite domain are not excluded even if they contradict the logical semantics of the propagator.

Another useful propagator is the all-distinct propagator.

{FD.distinct [U V W X Y Z]} 

Whenever the value of one of the variables in the list [U V W X Y Z] gets determined, this value is excluded from the domain of the others. The all-distinct propagator requires linear space in the number of variables it administrates, in contrast to a naive implementation which require quadratic space:

U\=:V   U\=:W  U\=:X   U\=:Y   U\=:Z  
        V\=:W  V\=:X   V\=:Y   V\=:Z  
               W\=:X   W\=:Y   W\=:Z  
                       X\=:Y   X\=:Z  
                               Y\=:Z

More on FD-propagators can be found in the tutorial on finite domain constraint programming in Oz.


Denys Duchier, Claire Gardent and Joachim Niehren
Version 1.3.99 (20050412)