Example: Queens

Place N queens on an N x N chess board such that no two queens attack each other. The parameter of the problem is N. A solution for the 4 - queens problem looks as follows:

Figure 11: A solution to the Queens Problem

Viewpoint

We will use a clever viewpoint avoiding possible symmetries and minimizing the number of propagators.

Since we want to put one queen into each column, we use the problem variables row[0],..., row[N - 1], one for each column on the chessboard. Every variable has the set {0,..., N - 1} as initial domain. Now, an assignment row[i] = j means that the queen in the ith column should be placed into the jth row. A solution to the N-queens problem is an assignment that satisfies the following constraints:

• No two queens are allowed to be placed in the same column.( This constraint is already coded in the model since we only have one problem variable per column).
• No two queens are allowed to be placed in the same row:

  $\forall$j $\neq$ i : row[i] $\neq$ row[j]

• No two queens are allowed to be placed on the same diagonal:

  $\forall$i < j : row[i] + (j - i) $\neq$ row[j] $\wedge$ row[i] - (j - i) $\neq$ row[j]

Branching Strategy

We branch on the variables row[0],..., row[N - 1] using a first-fail strategy that tries the value in the middle of the domain of the selected variable first. This strategy works well even for large N.

Script

Listing 7 shows a script for the N - queens problem. Besides the argument space the script now has an additional parameter n. This parameter is both used to create the vector row of size n and as an argument to the upperTriangle function.

fun queens n space =
   let
      val row = Modeling.fdtermVec(space, n, [0`#(n - 1)])
   in
      Modeling.distinct (space, row, FD.BND);
      List.app (fn (i, j) =>
         let
            val rowi = Vector.sub (row, i)
            val rowj = Vector.sub (row, j)
         in
            post (space, rowi `+ (`j `- `i) `<> rowj, FD.BND);
            post (space, rowi `- (`j `- `i) `<> rowj, FD.BND)
         end) (upperTriangle n);
      Modeling.branch (space, row, FD.B_SIZE_MIN, FD.B_MED);
      row
   end

The procedure upperTriangle you see in Listing 8 is used to create the list of all pairs (i , j) of integers such that:

0 $\leq$ i$\le$j$\le$N

This list is given as parameter to the List.app procedure and is used to satisfy the constraint that no two queens are on the same diagonal. So the resulting list of upperTriangle ensures that the sequences row[0] - 1,..., row[N - 1] - (N - 1) and row[0] + 1,..., row[N - 1] + (N - 1) are both nonrepetitive and therefore reduce the amount of propagators.

fun loop i n f = if i >= n then nil else f i :: loop (i + 1) n f

fun upperTriangle n =
   List.concat (loop 0 n 
               (fn i => loop (i + 1) n (fn j => (i, j))))

Using global constraints

The script presented in Listing 7 is not optimal. For a problem of size 9, the Explorer already needs very long to search the tree. One problem is that in the script for every pair of the upperTriangle list two propagators are created. This is really waste of computational space and time.

In Listing 9 you see an improved script that uses three vectors, where the first vector is the already known row vector. The vectors add and sub are used to build the constraints $\forall$i, j : row[i] + i $\neq$ row[j] + j and $\forall$i, j : row[i] - i $\neq$ row[j] - j, i.e. there are no two queens placed on the same diagonal. The optimization now is realized through the use of the propagator distinctOffset of the FD library. DistinctOffset is an extension of the distinct propagator and has the type:

space*(int*intvar)vector*conlevel $\rightarrow$ unit

So distinctOffset creates a propagator in s for the following:

$\forall$(c_i, x_i)and (c_j, x_j)with0 $\leq$ i, j $\leq$ n - 1andi $\neq$ j : x_i + c_i $\neq$ x_j + c_j

This propagator applied to the zipped vectors row with add and row with sub optimizes the script because the new formulation of the constraint, that no two queens are placed on the same diagonal, requires only two propagators.

fun betterqueens n space =
  let
    val row = FD.rangeVec (space, n, (0, n - 1))
    val add = Vector.tabulate (n, fn i => 0 + i)
    val sub = Vector.tabulate (n, fn i => 0 - i)
  in
    FD.distinct (space, row, FD.BND);
    FD.distinctOffset (space, VectorPair.zip (add, row), FD.BND);
    FD.distinctOffset (space, VectorPair.zip (sub, row), FD.BND);
    FD.branch (space, row, FD.B_SIZE_MIN, FD.B_MED);
    row
  end