Specifications PyCSP³ Tools Instances Competitions About

Constraint AllDifferent

The constraint allDifferent, see [R94], [vH01] and [GMN08], ensures that the variables in list must all take different values. A variant, called allDifferentExcept in the literature, see [BCR14] and [C12], enforces variables to take distinct values, except those that are assigned to some specified values (often, the single value 0). This is the reason why we introduce an optional element except.

allDifferent($X$,$E$) with $X=\langle x_1,x_2,\ldots \rangle$ and $E$ the set of discarded values iff $\forall (i,j) : 1 \leq i \lt j \leq |X|, x_i \neq x_j \lor x_i \in E \lor x_j \in E$
allDifferent($X$) iff allDifferent($X$,$\emptyset$)

The syntax is:

Syntax

 <allDifferent>
  <list> (intVar wspace)2+ </list>
  [<except> (intVal wspace)+ </except>]
</allDifferent> 

Note that the opening and closing tags of list are optional if list is the unique parameter of the constraint, which gives:

Syntax

<allDifferent> (intVar wspace)2+ </allDifferent>   <!-- Simplified Form -->

For example, below, the first constraint below forces all variables x1,x2,x3,x4,x5 to take different values, and the second constraint forces each of the variables of the 1-dimensional array y to take either the value 0 or a value different from the other variables.

Example

<allDifferent> 
  x1 x2 x3 x4 x5 
</allDifferent> 
<allDifferent>
  <list> y[] </list>
  <except> 0 </except>
</allDifferent> 

Possible restricted forms of allDifferent can be built by forcing variables to be, for example, symmetric and/or irreflexive. This is explained in the full specifications, but not allowed in XCSP³-core.

Variant allDifferent-list

If allDifferent contains several lists of integer variables, then the constraint ensures that the tuple of values taken by variables of the first element list is different from the tuple of values taken by variables of the second element list. If more than two elements list are given, all tuples must be different. A variant enforces tuples to take distinct values, except those that are assigned to some specified tuples (often, the single tuple containing only 0), specified in the optional element except.

Syntax

<allDifferent>
    (<list> (intVar wspace)2+ </list>)2+
    [<except> ("(" intVal ("," intVal)+ ")")+ </except>]
</allDifferent>

In the text below, allDifferent-list refers to allDifferent defined over several lists of integer variables.

{gbl("allDifferent-list", "X,E")}with $X=\langle X_1, X_2,\ldots \rangle$ and $E$ the set of discarded tuples {item($\forall (i,j) : 1 \leq i \lt j \leq |X|, X_i \neq X_j \lor X_i \in E \lor X_j \in E$)}
{gbl("allDifferent-list", "X")} iff {item(gbl("allDifferent-list", "X,\\emptyset"))}

Example

<allDifferent id="c1">
    <list> x1 x2 x3 x4 </list>
    <list> y1 y2 y3 y4 </list>
</allDifferent>
<allDifferent id="c2">
    <list> v1 v2 v3 v4 </list>
    <list> w1 w2 w3 w4 </list>
    <list> z1 z2 z3 z4 </list>
    <except> (0,0,0,0) </except>
</allDifferent>

Variant allDifferent-matrix

The constraint allDifferent-matrix, sometimes called allDiffmatrix, ensures that the values taken by variables on each row and on each column of a matrix are all different. It admits a parameter $M=[X_1,X_2,\ldots,X_n]$, with $X_1=\langle x_{1,1},x_{1,2},\ldots,x_{1,m} \rangle$, $X_2=\langle x_{2,1},x_{2,2},\ldots,x_{2,m} \rangle$, $\ldots$,

a two-dimensional array of variables given by an element matrix, assuming here a matrix of size $n \times m$.

{gbl("allDifferent-matrix", "M")}with $M=[X_1,X_2,\ldots,X_n]$ iff

$\forall i : 1 \leq i \leq n$, {gbl("allDifferent", "M[i]")}
$\forall j : 1 \leq j \leq m$, {gbl("allDifferent", "M^T[j]")}

Syntax

<allDifferent>
  <matrix> ("(" intVar ("," intVar)+ ")")2+ </matrix>
</allDifferent>

Example

<allDifferent>
  <matrix> 
    (x1,x2,x3,x4,x5)
    (y1,y2,y3,y4,y5)
    (z1,z2,z3,z4,z5)
  </matrix>
</allDifferent>