all_different(L)

The constraint all_different(L) holds if the variables in L are pair-wisely different. One naive implementation method for this constraint is to generate binary disequality constraints between all pairs of variables in L. This section gives an implementation of the naive method that uses a liner number of propagators. Stronger filtering algorithms have been proposed for the global constraint [13] and the algorithm adopted for all_distinct in B-Prolog is presented in [22].

The naive method that splits all_different into binary disequality constraints has two problems: First, the space required to store the constraints is quadratic in the number of variables in L; Second, splitting the constraint into small granularity ones may lose possible propagation opportunities.

To solve the space problem, we define all_different(L) in the following way:

      all_different(L) => all_different(L,[]).

      all_different([],Left) => true.
      all_different([X|Right],Left) =>
          outof(X,Left,Right),
          all_different(Right,[X|Left]).

      outof(X,Left,Right), var(X), {ins(X)} => true.
      outof(X,Left,Right) => 
          exclude_list(X,Left),exclude_list(X,Right).

For each variable X, let Left be the list of variables to the left of X and Right be the list of variables to the right of X. The call outof(X,Left,Right) holds if X appears in neither Left nor Right. Instead of generating disequality constraints between X and all the variables in Left and Right, the call outof(X,Left,Right) suspends until X is instantiated. After X becomes an integer, the calls exclude_list(X,Left) and exclude_list(X,Right) to exclude X from the domains of the variables in Left and Right, respectively.

There is a propagator outof(X,Left,Right) for each element X in the list, which takes constant space. Therefore, all_different(L) takes linear space in the size of L. Notice that the two lists Left and Right are not merged into one bigger list. Or, the constraint still takes quadratic space.