Magic square

Magic square is another typical constraint satisfaction problem. There is an N by N grid board. One is required to assign each grid a different digit from 1 to N such that all the rows, all the columns, and both of the diagonals have the same total. We will understand through this example aggregation constraints and array expressions for creating anonymous arrays.

  

Figure: A solution to the $3\times 3$ magic square problem.

Figure shows a solution of the $3\times 3$ magic square problem. The following shows the code:

 class Cell {
     dj Label lb;    
     dj int value in 1..Magic.N*Magic.N;
     lb.text == String(value);
 }

 class Magic { 
     public static final int N = 3; 
     dj Cell board[N][N];    
     dj int total;    

     for (i in 0..N-1)   //columns 
          sum(board[i][j].value, j in 0..N-1)==total; 
     for (j in 0..N-1)   //rows 
          sum(board[i][j].value,i in 0..N-1)==total; 
     sum(board[i][i].value, i in 0..N-1)==total; 
                         //left-upper-down diagonal
     sum(board[i][j].value, i in 0..N-1, j in 0..N-1, i+j==N-1)== total;
                         // left-bottom-up diagonal 
     alldifferent(array(board[i][j].value,i in 0..N-1,j in 0..N-1));
     grid(board); 
 }

Each grid square is a component of the class Cell, which has a label, called lb, and an integer attribute, called value, whose domain is declared to be 1..N². The constraint lb.text==String(value) ensures that value is the same as lb.text after it is converted to a string.

The board is represented as a two-dimensional array of cells. We use an integer attribute, called total, to represent the sum.

The expressions sum(...) in the constraints are called aggregation expressions. In general, an aggregation expression has the following form:

 xxx(Exp,Enumerator,...,Enumerator)

where XXX can be substituted by sum, min, or max. Every variable in Exp must occur at least once in the enumerators. For each tuple of values for the variables that satisfy the enumerators, the Exp got a value. The aggregation expression stands for the sum, minimum, or maximum of all such values.

The two for constraints say that all columns and rows have the same sum total. The two aggregation constraints say that the two diagonals have the same sum.

The alldifferent constraint takes an array of variables of some type and ensures that all the variables take different values. The argument is an anonymous array built by using an array expression. In general, an array expression has the following form:

 array(Exp,Enumerator,...,Enumerator)

where Exp is an expression. For each tupe of values for the variables in the enumerators that satisfies the enumerators, Exp has a value. This expression represents an array of all such values. The array expression in our example converts a two-dimensional array of cells into a one-dimensional array of integers.