N-queen problem

DJ can be used not only to draw graphics and build graphical user interfaces but also to solve constraint satisfaction problems in general. In this example, we consider how to describe the N-queen problem and display the solutions graphically. We will understand, through this example, arrays as well as for and entailment constraints.

  

Figure: A solution to the 8-queen problem.

The problem is described as follows: There are an N by N chessboard and N queens. One is required to place the queens on the chessboard such that no two queens attack each other, i.e., no two queens can be placed on the same row, the same column, and the same diagonal. Figure shows a solution to the 8-queen problem. The following shows the code:

 class Queens {
     static public final int N = 8;
 
     dj Square board[N][N]{fill==false};
     dj Image queens[N]{name=="queen.gif";
                        size==board[0][0].size};
     dj int pos[N] in 0..N-1;
 	   
     for (i in 0..N-1,j in 0..N-1) 
         pos[i]==j -> samePosition(queens[i],board[i][j]);
     notattack(pos,N);
     grid(board);
 }
 
 constraint notattack(int[] pos,int N){
     for (i in 0..N-2,j in i+1..N-1){
         pos[i] != pos[j];
         pos[i] != pos[j]+j-i;
         pos[i] != pos[j]+i-j;
     }
 }

N is defined as a constant. The chessboard is represented as a two-dimensional array of unfilled squares and the N queens are represented as an array of images. Every image has the same size as a grid square. We also use an attribute array, called pos, to indicate the positions of the queens. For each queen i, the element pos[i] indicates the number of the row on which the queen is placed.

The for constraint has the following meaning: For each queen i and each row j, if queen i is placed on row j, then the image queen[i] and the square board[i][j] must have the same position. The constraint

 pos[i]==j -> samePosition(queens[i],board[i][j]);

is called an entailment constraint. An entailment constraint A->B means that constraint B must be satisfied if A is satisfied. The above-mentioned for constraint can be rewritten equivalently into the following:

 for (i in 0..N-1,j in 0..N-1,pos[i]==j) 
     samePosition(queens[i],board[i][j]);

where the precedent of the entailment constraint becomes an enumerator.

The notattack constraint, which is a user-defined one, ensures that no two queens attack each other. The grid constraint constrains the layout for the board. The signature for grid is as follows:

 grid(DJComponent[][] comps)

It takes a two-dimensional array of components and ensures that the components are placed in a grid board.