A common situation in integer programming is to have a set of general integer variables that are all required to take on different values. Examples would include the sequence of cities visited in a traveling salesman problem, or the 9 values in a square of a Sudoku puzzle.

The primary syntax for the @ALLDIFF function is:

@ALLDIFF( 'set_name', variable_name);

where 'set_name' is the name assigned to this set of general integer variables, and variable_name is the name of a variable belonging to the set. Note that the @ALLDIFF function can be used inside an @FOR looping function to place multiple variables into the same set. Some examples of @ALLDIFF are:

Example 1:        @ALLDIFF( 'SET1', X); @ALLDIFF( 'SET1', Y);

  makes the scalar variables X and Y members of the all-different set called 'SET1',

Example 2:        @FOR( CITIES( I): @ALLDIFF( 'SEQSET', Z( I)));

  assigns all variables of attribute Z to the all-different set 'SEQSET'.

By all-different, we mean that the variables in the set will all take on different integer values ranging from 1 to N, when N is the number of variables in the set.

For an interesting application of @ALLDIFF, you can refer to the SUDOKUALLDIFF.LG4 model in the LINGO Samples folder. This model solves the well-know Sudoku puzzle, where one fills a 9x9 grid with the digits 1,2,...9, so that each digit appears once in:

a) each column,

b) each row,

c) each of the nine 3x3 subsquares,

d) the main diagonal,

e) the reflected diagonal.

Some versions of the puzzle do not require (d) and (e).

Looking at the sample model SUDOKUALLDIFF, we find the following constraints that enforce properties a) through c) above:

! Each entry is in the interval [1, 9];

@for( sxs(i,j):

 @bnd( 1, y(i,j), 9);

   );

 

! For each row i, the entries must be all different integers;

@for( side( i):

  @for( side(j):

     @alldiff( 'row'+side(i), y(i,j));

      );

    );

 

! For each col j, the entries must be all different;

@for( side( j):

  @for( side(i):

     @alldiff( 'col'+side(j), y(i,j));

      );

    );

 

! For each subblock, the entries must be all different;

@for( sxs(i1,j1) | @mod(i1,3) #eq# 1 #and# @mod(j1,3) #eq# 1:

  @for( sxs(i,j) | i1 #le# i #and# i #le# i1+2

    #and# j1 #le# j #and# j #le# j1+2:

     @alldiff( 'blk'+side(i1)+side(j1), y(i,j));

      );

    );

Model: SUDUKOALLDIFF

Note that Y(i,j) represents the value stored in row i and column j of the puzzle.

An interesting feature of the calls to the @ALLDIFF function in this model are the references to the set SIDE, where SIDE is used to represent the 9 rows and 9 columns of the puzzle. Using set names allows us to construct unique names for the different sets of all-different variables. Generating the scalar version of this model, we find find the following @ALLDIFF references to enforce the all-different condition for row 1 of the puzzle:

@ALLDIFF( 'ROW1', Y_1_1); @ALLDIFF( 'ROW1', Y_1_2);

@ALLDIFF( 'ROW1', Y_1_3); @ALLDIFF( 'ROW1', Y_1_4);

@ALLDIFF( 'ROW1', Y_1_5); @ALLDIFF( 'ROW1', Y_1_6);

@ALLDIFF( 'ROW1', Y_1_7); @ALLDIFF( 'ROW1', Y_1_8);

@ALLDIFF( 'ROW1', Y_1_9);

In this case, we concatenated the set name of the first row (i.e., "1") to the word "ROW" to construct the all-different set name for the first row of the puzzle: "ROW1".

Solving this models gives us the following solution to the puzzle:

 

   Sudoku Puzzle Solution:

   .....................................

   .  3  5  4  .  1  6  2  .  7  8  9  .

   .  2  9  1  .  7  8  3  .  6  5  4  .

   .  7  6  8  .  9  4  5  .  2  3  1  .

   .....................................

   .  6  1  2  .  8  3  9  .  4  7  5  .

   .  8  4  5  .  6  7  1  .  9  2  3  .

   .  9  3  7  .  2  5  4  .  1  6  8  .

   .....................................

   .  1  7  6  .  3  9  8  .  5  4  2  .

   .  5  2  3  .  4  1  7  .  8  9  6  .

   .  4  8  9  .  5  2  6  .  3  1  7  .

   .....................................

 

Specifying Bounds on Variables on an Alldiff Set

You will note from above that the default values of the variables in an Alldiff set with N members will be contained in the set of positive integers {1..N}, with each variable having a unique value. For most applications this should be sufficient. However, there may be times when you wish to override these bounds of 1 to N, so that the variables can take on a different set of values. In the model fragment below, we create an Alldiff set called MYALLDIFF that contains the three variables X, Y and Z.

!First call passed the lower and upper bounds on

the Alldiff variables;

  @ALLDIFF( 'MYALLDIFF', 10, 20);

 

!Add X, Y amd Z variables to the set;

  @ALLDIFF( 'MYALLDIFF', X);

  @ALLDIFF( 'MYALLDIFF', Y);

  @ALLDIFF( 'MYALLDIFF', Z);

Note the additional @ALLDIFF call at the top to explicitly specify the variable bounds: @ALLDIFF( 'MYALLDIFF', 10, 20). In this case, instead of the variable values running from 1 to 3, they will now values contained in the interval of 10 to 20. Subsequent @ALLDIFF calls are as before, with two arguments consisting of the set name and a new variable name to add to the set.