The model will eliminate symmetries by imposing order constraints. Propagation will be drastically improved by exploiting a redundant constraint.

- Every field of the matrix is an integer between 1 and
*N*^{2}. - The fields of the matrix are pairwise distinct.
- The sums of the rows, columns, and the two main diagonals are all equal.

2 7 6The Magic Square Puzzle is extremely hard for large N. Even for N = 4, our script will have to explore more than 10000 nodes to find a solution.

9 5 1

4 3 8

Without loss of generality, we can impose the following order constraints eliminating symmetries:

Since the sum of the sums of the rows must equal the sum of all fields, we have the redundant constraintF_{11}<F_{NN}F_{N1}<F_{1N}F_{11}<F_{N1}

* (To see this, note that sum of all fields equalsN^{2}+ 1) = N * S

1 + 2 + 3 + ... +and that the sum of each of the N rows must be S.N^{2}= * (N^{2}+ 1)

val maxValue = (valOf (Int.maxInt))div 2 fun magicsquares n space = let val nn = n * n val matrix = Vector.tabulate(n,fn x => FD.rangeVec(space,n,(1,nn))) val matrixv =Vector.concat(Vector.toList(matrix)) val sum = FD.range(space,(1,maxValue)) val sumn = FD.range(space,(1,maxValue)) val diagonal1 = Vector.tabulate(n,fn x =>(x,x)) val diagonal2 = Vector.tabulate(n,fn x =>(n-1-x,x)) val diagonal1vars = Vector.map(fn(x,y) => Vector.sub(Vector.sub(matrix,x),y))diagonal1 val diagonal2vars = Vector.map(fn(x,y) => Vector.sub(Vector.sub(matrix,x),y))diagonal2 val field11 = Vector.sub(Vector.sub(matrix,0),0) val field1N = Vector.sub(Vector.sub(matrix,0),n-1) val fieldN1 = Vector.sub(Vector.sub(matrix,n-1),0) val fieldNN = Vector.sub(Vector.sub(matrix,n-1),n-1) in FD.distinct(space,matrixv,FD.DOM); (* diagonals *) post(space,SUMV(diagonal1vars) `= FD(sum),FD.DOM); post(space,SUMV(diagonal2vars) `= FD(sum),FD.DOM); (* columns *) Vector.appi(fn(y,z)=> let val colmn = Vector.tabulate(n,fn x => Vector.sub(Vector.sub(matrix,x),y)) in post(space,SUMV(colmn) `= FD(sum),FD.DOM) end)matrix; (* rows *) Vector.appi(fn(x,y) => post(space,SUMV(y) `= FD(sum),FD.DOM))matrix; (* Eliminate symmetries *) FD.rel(space,field11,FD.LE,fieldNN); FD.rel(space,fieldN1,FD.LE,field1N); FD.rel(space,field11,FD.LE,fieldN1); (*redundant constraints *) post(space,FD(sum) `* `n `= FD(sumn),FD.DOM); FD.relI(space,sumn,FD.EQ,(nn *(nn + 1))div 2); FD.branch(space,matrixv,FD.B_SIZE_MIN,FD.B_SPLIT_MIN); {matrix} end

With the Explorer you can find out that for N = 3 there is exactly one magic square satisfying the ordering constraints of our model. Without the ordering constraints there are 8 different solutions. Omitting the propagator for the redundant constraint will increase the search tree by one order of magnitude.

Andreas Rossberg 2006-08-28