Since we want to put one queen into each column, we use the problem
variables
row[0],..., row[N - 1]
The procedure upperTriangle you see in Listing 8 is used
to create the list of all pairs (i , j) of integers such that:
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
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.
j
i : row[i]
row[j]
i < j : row[i] + (j - i)
row[j]
row[i] - (j - i)
row[j]
Branching Strategy
We branch on the variables
row[0],..., row[N - 1]
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
0
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)
i
j
N
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.
i, j : row[i] + i
row[j] + j
i, j : row[i] - i
row[j] - j
space*(int*intvar)vector*conlevel
So distinctOffset creates a propagator in s for the following:
unit
(ci, xi)and (cj, xj)with0
i, j
n - 1andi
j : xi + ci
xj + cj
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