The Constraint Programming Solver (Experimental)

Eight Queens

The Eight Queens problem is a special instance of the N-Queens problem, where the objective is to position N queens on an N × N chessboard such that no two queens can attack each other. The CLP solver provides an expressive constraint for variable arrays that can be used for solving this problem very efficiently.

You can model this problem by using a variable array a of dimension N, where $a_ i$ is the row number of the queen in column i. Because no two queens can be in the same row, it follows that all the $a_ i$’s must be pairwise distinct.

In order to ensure that no two queens can be on the same diagonal, the following two expressions should be true for all i and j:

\[ a_ j - a_ i <> j -i \]
\[ a_ j - a_ i <> i -j \]

These expressions can be reformulated as follows:

\[ a_ i - i <> a_ j - j \]
\[ a_ i + i <> a_ j + j \]

Hence, the $(a_ i + i)$’s are pairwise distinct, and the $ (a_ i-i)$’s are pairwise distinct. One possible formulation is as follows: 

proc optmodel;
   num n init 8;
   var A {1..n}        >= 1     <= n     integer;
   /* Define artificial offset variables. */
   var B {1..n, -1..1} >= 1 - n <= n + n integer;
   con Bdef {i in 1..n, k in -1..1}:
      B[i,k] = A[i] + k * i;

   con OffsetsMustBeAlldifferent {k in -1..1}:
      alldiff({i in 1..n} B[i,k]);
   solve with CLP / varselect=fifo;
   /* Replicate typical PROC CLP output from an OPTMODEL array */
   create data out from {i in 1..n}<col('A'||i)=A[i]>;
quit;

The VARSELECT= option specifies the variable selection strategy to be first-in, first-out—the order in which the CLP solver encounters the variables.

The corresponding solution to the Eight Queens problem is displayed in Figure 6.2.

Figure 6.2: A Solution to the Eight Queens Problem

A Solution to the Eight Queens Problem