5
$\begingroup$

I'm solving the magic square problem without using the alldiff operator.

To insert different values ​​in the matrix, I initialized a variable:

var y {1..n, 1..n, 1..n * n} binary;

where y[i,j,k] will equal 1 if and only if entry i, j in the matrix equals k. Then each cell contains exactly one number is given by:

s.t. OneEach {i in 1..n, j in 1..n}: sum {k in 1..n * n} y[i,j,k] = 1;

and the constraint that all entries are different is given by:

s.t. AllDifferent {k in 1..n * n}: sum {i in 1..n, j in 1..n} y[i,j,k] <= 1;

My problem now is to formalize the constraint that the sum on the rows, columns and on the diagonals is equal to the magic constant. I tried with

s.t. RowsSum {k in 1..n * n}: sum {i in 1..n, j in 1..n} k * y [i, j, k] = constant;

s.t. ColsSum {k in 1..n * n}: sum {i in 1..n, j in 1..n} k * y [j, i, k] = constant;

An additional constraint is used to calculate the value of the constant:

s.t. q1: ((k*k)/2)*(k*k+1) = constant*k;

But when I load the model, he tells me:

presolve: constraint ColsSum [1] cannot hold: body> = 15 cannot be <= 9; difference = 6 presolve: constraint RowsSum [1] cannot hold: body> = 15 cannot be <= 9; difference = 6

Without the constraints on the sum of rows and columns, the result is this:

Magic_Constant = 15

  1   2   3
  4   5   6
  7   8   9

The value of the magic constant is right, the square works because there are all the numbers from 1 to n^2, and they also appear only once. But now I must add that the sums on rows and columns must be equal to the magic constant.

Tips?

$\endgroup$
  • $\begingroup$ Since you only have n rows, you shouldn't have n^2 instances of Rowssum, and similarly for columns. $\endgroup$ – Geoffrey Brent Oct 29 '19 at 22:44
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"];
$\endgroup$
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.

$\endgroup$

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