Heterosquare

From CometPublic

Contents 1 Definition of a heterosquare 2 Description of the model 2.1 Variables 2.2 Invariants 2.3 Constraints 3 Description of the search 4 Complete implementation

[edit] Definition of a heterosquare

A heterosquare of order n is a n*n square whose elements are distinct integers from 1 to n² such that the sums of the rows, columns and diagonals are all different. Here is an example of heterosquare of order 3 :

           19

1  2  3    6
8  9  4    21
7  6  5    18

16 17 12   15

[edit] Description of the model

[edit] Variables

We need two arrays of integer variables :

• the first one represent the square : the number in the square at row i and column j is represented by the variable at position n*(i-1) in the array
• the second one contains the sums of the rows, columns and diagonals of the square. The variables at positions 1 to n are the sums of the rows, those at positions n+1 to 2*n are the sums of the columns, and the two lasts are the sums of the diagonals.

Thus we have for a heterosquare of order n :

                                 sums[8]

square[1] square[2] square[3]    sums[1]
square[4] square[5] square[6]    sums[2]
square[7] square[8] square[9]    sums[3]

 sums[4]   sums[5]   sums[6]     sums[7]

Here is the declaration of the variables in Comet :

LocalSolver m();
range SizeSide = 1..n;  //size of a side of the square
range SizeSquare = 1..n^2;  //size of the square
range SizeSums = 1..2*n+2;  //number of sums : n rows + n colums + 2 diagonals
RandomPermutation perm (1..n^2);
var{int} square[i in SizeSquare](m,SizeSquare) := perm.get();  //numbers in the square
var{int} sums[i in SizeSums] (m,n..n^3);  //sums[1..n] : sums of the rows, sums[n+1..2*n] : sums of the columns, sums[2*n+1,2*n+2] : sums of the diagonals

[edit] Invariants

So that each variable in the array sums represent at each execution step the sum of the elements in a row/column/diagonal of the square, we use invariants.

forall (i in SizeSide) {
     sums[i] <- sum(j in SizeSide) square[n*(i-1)+j];  //sums of the rows
     sums[i+n] <- sum(j in SizeSide) square[n*(j-1)+i];  //sums of the columns
}
sums[2*n+1] <- sum(i in SizeSide) square[n*(i-1)+i];  //sums of the diagonal
sums[2*n+2] <- sum(i in SizeSide) square[n*(i-1)+n-(i-1)];

[edit] Constraints

We need two constaints :

• the elements of the square are all different
• the sums are all different

Now we can explain why we use an array to represent the square in place of a matrix : the constraint alldifferent takes as argument an array, not a matrix.

ConstraintSystem S(m);
S.post(alldifferent(sums)); 
S.post(alldifferent(square));

[edit] Description of the search

At each iteration of the search, we chose the variable with the maximum number of violations and we assigne it the value that minimizes the difference between the system violations if we assign this value to the variable and the current system violations. We use the tabu heuristic such that a variable can't be changed in the three iterations after it's last updating.

int it = 0;
int tabuLength = 3;
int tabu[SizeSquare] = -1;
while (violations > 0 && it < 10000*n) {
     selectMax (i in SizeSquare : tabu[i] < it) (S.violations(square[i])) {
          selectMin (v in SizeSquare : square[i] != v) (S.getAssignDelta(square[i],v)) {
               square[i] := v;
               tabu[i] = it + tabuLength;
          }
     }
     cout << "(" << violations << ")" << flush;
     it ++;
}

[edit] Complete implementation

include "LocalSolver";

int start = System.getCPUTime();

int n = 6;
LocalSolver m();
range SizeSide = 1..n;  //size of a side of the square
range SizeSquare = 1..n^2;  //size of the square
range SizeSums = 1..2*n+2;  //number of sums : n rows + n colums + 2 diagonals
RandomPermutation perm (1..n^2);
var{int} square[i in SizeSquare](m,SizeSquare) := perm.get();  //numbers in the square
var{int} sums[i in SizeSums] (m,n..n^3);  //sums[1..n] : sums of the rows, sums[n+1..2*n] : sums of the columns, sums [2*n+1,2*n+2] : sums of the diagonals

//invariants for the sums
forall (i in SizeSide) {
     sums[i] <- sum(j in SizeSide) square[n*(i-1)+j];  //sums of the rows
     sums[i+n] <- sum(j in SizeSide) square[n*(j-1)+i];  //sums of the columns
}
sums[2*n+1] <- sum(i in SizeSide) square[n*(i-1)+i];  //sums of the diagonal
sums[2*n+2] <- sum(i in SizeSide) square[n*(i-1)+n-(i-1)];

ConstraintSystem S(m);
S.post(alldifferent(sums)); 
S.post(alldifferent(square));

m.close();
var{int} violations = S.violations();

int it = 0;
int tabuLength = 3;
int tabu[SizeSquare] = -1;
while (violations > 0 && it < 10000*n) {
     selectMax (i in SizeSquare : tabu[i] < it) (S.violations(square[i])) {
          selectMin (v in SizeSquare : square[i] != v) (S.getAssignDelta(square[i],v)) {
               square[i] := v;
               tabu[i] = it + tabuLength;
          }
     }
     cout << "(" << violations << ")" << flush;
     it ++;
}

int finish = System.getCPUTime();
int time = finish-start;

cout << endl << "Solution :" << endl;
forall (i in SizeSide) {
     forall (j in SizeSide) {
          cout << square[n*(i-1)+j] << "  ";
     }
     cout << endl;
}
cout << sums << endl;
cout << "Violations: " << violations << endl;
cout << "Iterations: " << it << endl; 
cout << "Time : " << time << endl;