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:
*j**i*:*row*[*i*]*row*[*j*] - No two queens are allowed to be placed on the same diagonal:
*i*<*j*:*row*[*i*] + (*j*-*i*)*row*[*j*]*row*[*i*] - (*j*-*i*)*row*[*j*]

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:

0This 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 sequencesijN

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))))

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
*i*, *j* : *row*[*i*] + *i* *row*[*j*] + *j* and
*i*, *j* : *row*[*i*] - *i* *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:

So distinctOffset creates a propagator in s for the following:space*(int*intvar)vector*conlevelunit

(c_{i},x_{i})and(c_{j},x_{j})with0i,jn- 1andij:x_{i}+c_{i}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

Andreas Rossberg 2006-08-28