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 syntax of 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  .

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