all_different(L)

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

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

In order to solve the space problem, B-Prolog defines 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 let 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 of 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) 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 terms of the size of L. Note that the two lists, Left and Right, are not merged into one bigger list. Otherwise, the constraint would still take quadratic space.