7
$\begingroup$

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";
}
Improve this question
$\endgroup$
1
  • $\begingroup$ Since you only have n rows, you shouldn't have n^2 instances of Rowssum, and similarly for columns. $\endgroup$
    – G_B
    Commented Oct 29, 2019 at 22:44

4 Answers 4

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
4
$\begingroup$

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"];
Improve this answer
$\endgroup$
3
$\begingroup$

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.

(1) https://www.bigfishgames.com/blog/how-to-solve-sudoku-puzzles-quickly-and-reliably/

(2) http://www.cross-plus-a.com/sudoku.htm

Improve this answer
$\endgroup$
5
  • $\begingroup$ OP is not allowed to use alldiff, which is a pity, because this is the obvious and sensible way to do it. $\endgroup$
    – G_B
    Commented Oct 24, 2019 at 0:19
  • $\begingroup$ @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... $\endgroup$
    – Oguz Toragay
    Commented Oct 24, 2019 at 0:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – G_B
    Commented Oct 24, 2019 at 0:35
  • $\begingroup$ @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? $\endgroup$
    – Oguz Toragay
    Commented Oct 24, 2019 at 5:11
  • 1
    $\begingroup$ Yes, that's the one. $\endgroup$
    – G_B
    Commented Oct 24, 2019 at 6:07
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Matteo
    Commented Oct 29, 2019 at 16:05
  • $\begingroup$ This is the result with your constraint: pastebin.com/MxaVjt7W $\endgroup$
    – Matteo
    Commented Oct 29, 2019 at 17:14
  • $\begingroup$ Full-code: pastebin.com/waq6FjPd $\endgroup$
    – Matteo
    Commented Oct 29, 2019 at 17:17
  • $\begingroup$ @MatteoD'Alessio, pastebin.com/S9kakVVV $\endgroup$
    – Oguz Toragay
    Commented Oct 29, 2019 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.