# Matrix in ampl: constraint that the values ​are all different

I'm solving the magic square problem for my operational research exam.

The constraints of my model are that the sum of the elements on the lines must be equal to a constant (var constant), that the sum of the elements on the columns must be equal to the same constant and that also the sum on the diagonals must be equal to the same constant . These constraints are r, c, d1 and d2. I have also inserted a constraint q1 to find this constant because there is the property that multiplying the order of the matrix by the magic constant yields the sum of the values ​​from 1 to k^2.

For k=3, I get this matrix in output:

1 9 5
5 9 1
5 1 9

Magic_Constant: 15


But that's not good, I have to find a way to insert a constraint that says that all the values ​​in the matrix must be different (from 1 to n^2). But I can't use the alldiff operator!

How can I do?

### PARAMETER ###
param k;
param firstKnumber = ((k*k)/2)*(k*k+1);

### VARIABLE ###
var x{1..k,1..k} >= 1 <= k*k integer;
var constant;

### CONSTRAINT ###
subject to r{t in 1..k}: sum{i in 1..k} x[t,i] = constant;
subject to c{t in 1..k}: sum{i in 1..k} x[i,t] = constant;
subject to d1: sum{i in 1..k} x[i,i] = constant;
subject to d2: sum{i in 1..k} x[i,k-i+1] = constant;
subject to q1: firstKnumber = constant*k;

### OBJECTIVE ###
minimize Magic_Constant: constant;

data;
param k:= 3;
option solver gurobi;
solve;

display Magic_Constant;

for{i in 1..n} {
for {j in 1..n} {
printf "%3d ", x[i,j];
}
printf "\n";
}

• Since you only have n rows, you shouldn't have n^2 instances of Rowssum, and similarly for columns. Oct 29 '19 at 22:44

Outside an exam scenario, the correct answer is "switch to a solver that supports alldiff", but I'm assuming you are required to solve this in Gurobi.

One way to approach this within the confines of a linear integer problem is to make your decision variable a binary, with an extra dimension added. Hence, instead of "value of X at [i,j]" your decision variable now represents "whether X[i,j] = h" for h in 1..n^2.

Since this is an exam question, I won't spell out everything, but with this change it should be easy enough to represent all the constraints in linear format including the alldiff constraint.

I'm not sure if this helps you, but here is a "pure" IP model for the magic square problem, i.e. no all_different. However it's in MiniZinc (not AMPL), but it should be possible to port it to AMPL. The model also available here: http://hakank.org/minizinc/magic.mzn. (Note: it's a port of the GLPK model magic.mod, available in the GLPK distribution.)

% square order
int: n = 3;

% integers to be placed
set of 1..n*n: N = 1..n*n;

% x[i,j,k] = 1 means that cell (i,j) contains integer k
array[1..n, 1..n, N] of var 0..1: x;

array[1..n, 1..n] of var 1..n*n: square;

var int: s; % the magic sum

solve :: int_search(
[x[i,j,k] | i,j in 1..n, k in N] ++
[square[i,j] | i,j in 1..n] ++
[s],
first_fail,
indomain_min,
complete % "credit(640, bbs(5))" % "complete"
)
satisfy;

constraint
s >= 0
/\
s <= n*n*n
/\
% each cell must be assigned exactly one integer
forall(i in 1..n, j in 1..n) (
sum(k in N) (x[i,j,k]) = 1
)
/\
% each integer must be assigned exactly to one cell
forall(k in N) (
sum(i in 1..n, j in 1..n) (x[i,j,k]) = 1
)

/\
% the sum in each row must be the magic sum
forall(i in 1..n) (
sum(j in 1..n, k in N) (k * x[i,j,k]) = s
)

/\
% the sum in each column must be the magic sum
forall(j in 1..n) (
sum(i in 1..n, k in N) (k * x[i,j,k]) = s
)

/\
% the sum in the diagonal must be the magic sum
sum(i in 1..n, k in N) (k * x[i,i,k]) = s

/\
% the sum in the co-diagonal must be the magic sum
sum(i in 1..n, k in N) (k * x[i,n-i+1,k]) = s

/\
% for output
forall(i,j in 1..n) ( square[i,j] = sum(k in N) (k * x[i,j,k]))
;

output [
"\ns: ", show(s)
] ++
[
if  j = 1 then "\n" else " " endif ++
show(square[i,j])
| i,j in 1..n
] ++ ["\n"];


In AMPL's website, there is a code for solving sudoku which is very similar to your problem. In their code they also used alldiff. The only thing that you need to add to the following model is some constraint to consider the diagonal summation as well. By the way, "a Sudoku puzzle is defined as a logic-based, number-placement puzzle. The objective is to fill a 9×9 grid with digits in such a way that each column, each row, and each of the nine 3×3 grids that make up the larger 9×9 grid contains all of the digits from 1 to 9. Each Sudoku puzzle begins with some cells filled in"(1). In some sudokus, main diagonals also contain the digits 1 through 9. This variant is called Sudoku X (Diagonal Sudoku)(2).

The AMPL code for Sudoku:

param given {1..9, 1..9} integer, in 0..9;
# given[i,j] > 0 is the value given for row i, col j
# given[i,j] = 0 means no value given
var X {1..9, 1..9} integer, in 1..9;
# x[i,j] = the number assigned to the cell in row i, col j
subj to AssignGiven {i in 1..9, j in 1..9: given[i,j] > 0}: X[i,j]= given[i,j];
# assign given values
subj to Rows {i in 1..9}: alldiff {j in 1..9} X[i,j];
# cells in the same row must be assigned distinct numbers
subj to Cols {j in 1..9}: alldiff {i in 1..9} X[i,j];
# cells in the same column must be assigned distinct numbers
subj to Regions {I in 1..9 by 3, J in 1..9 by 3}: alldiff {i in I..I+2, j in J..J+2} X[i,j];
# cells in the same region must be assigned distinct numbers


Edit: Thanks to @GeoffreyBrent, I think I need to provide this link, where you can find another version of the AMPL code for sudoku problem.

• OP is not allowed to use alldiff, which is a pity, because this is the obvious and sensible way to do it. Oct 24 '19 at 0:19
• @GeoffreyBrent , reading the question again, I just understand what the OP means when said: “I can’t use the alldiff operator!”. Alright I need to think about that, there should be a way... Oct 24 '19 at 0:29
• I think the usual way to handle this in a LIP framework is to make the decision variable binary and then add another dimension, so the DV now represents "whether cell [i,j] has value k". It's not nearly as tidy or as clear as alldiff though. Oct 24 '19 at 0:35
• @GeoffreyBrent I edited my answer. Can you please have a look at the approach in the provided file to see if it’s the same approach that you talked in your comments? Oct 24 '19 at 5:11
• Yes, that's the one. Oct 24 '19 at 6:07

Please check this link to my answer to your previous question. I included a link in which without using alldiff, Sudoku problem (where the magic constant is equal to 9) has been solved. You may find some tips and hints there. I hope it helps.

Edit: Try the following constraints for the rows and columns:

subject to RowsSum {i in I}: sum {j in J, k in K} k*y[i, j, k] = constant;
subject to ColsSum {j in J}: sum {i in I, k in K} k*y[i, j, k] = constant;
subject to Diag: sum {i in I, k in K} k*y[i, i, k] = constant;
subject to ADiag: sum {i in I, k in K} k*y[i, n-i+1, k] = constant;


I translated the code by @hakank into AMPL.

• Hi, the Sudoku problem you linked to me in the previous post uses almost the same method I used. My only problem at the moment is to set the constraints on the sum of the elements of rows and columns. Oct 29 '19 at 16:05
• This is the result with your constraint: pastebin.com/MxaVjt7W Oct 29 '19 at 17:14
• Full-code: pastebin.com/waq6FjPd Oct 29 '19 at 17:17
• @MatteoD'Alessio, pastebin.com/S9kakVVV Oct 29 '19 at 18:26