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 implementation 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.