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";
}
$\endgroup$
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.

$\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

$\endgroup$
  • $\begingroup$ OP is not allowed to use alldiff, which is a pity, because this is the obvious and sensible way to do it. $\endgroup$ – Geoffrey Brent Oct 24 '19 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 Oct 24 '19 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$ – Geoffrey Brent Oct 24 '19 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 Oct 24 '19 at 5:11
  • 1
    $\begingroup$ Yes, that's the one. $\endgroup$ – Geoffrey Brent Oct 24 '19 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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