Node:N Queens, Next:Cumulative Scheduling, Previous:Send More Money, Up:Example Programs

The problem is to place N queens on an NxN chess board so that no queen is threatened by another queen.

The variables of this problem are the N queens. Each queen has a designated row. The problem is to select a column for it.

The main constraint of this problem is that no queen threaten another.
This is encoded by the `no_threat/3`

constraint and holds between
all pairs `(X,Y)`

of queens. It could be defined as

no_threat(X, Y, I) :- X #\= Y, X+I #\= Y, X-I #\= Y.

However, this formulation introduces new temporary domain variables and creates twelve fine-grained indexicals. Worse, the disequalities only maintain interval-consistency and so may miss some opportunities for pruning elements in the middle of domains.

A better idea is to formulate `no_threat/3`

as an FD
predicate with two indexicals, as shown in the program below.
This constraint will not fire until one of the queens has been assigned
(the corresponding indexical does not become monotone until then).
Hence, the constraint is still not as strong as it could be.

For example, if the domain of one queen is `2..3`

, then it will
threaten any queen placed in column 2 or 3 on an adjacent row, no matter
which of the two open positions is chosen for the first queen. The
commented out formulation of the constraint captures this reasoning, and
illustrates the use of the `unionof/3`

operator. This stronger
version of the constraint indeed gives less backtracking, but is
computationally more expensive and does not pay off in terms of
execution time, except possibly for very large chess boards.

It is clear that `no_threat/3`

cannot detect any incompatible values
for a queen with domain of size greater than three. This observation is
exploited in the third version of the constraint.

The first-fail principle is appropriate in the enumeration part of
this problem.

:- use_module(library(clpfd)). queens(N, L, LabelingType) :- length(L, N), domain(L, 1, N), constrain_all(L), labeling(LabelingType, L). constrain_all([]). constrain_all([X|Xs]) :- constrain_between(X, Xs, 1), constrain_all(Xs). constrain_between(_X, [], _N). constrain_between(X, [Y|Ys], N) :- no_threat(X, Y, N), N1 is N+1, constrain_between(X, Ys, N1). % version 1: weak but efficient no_threat(X, Y, I) +: X in \({Y} \/ {Y+I} \/ {Y-I}), Y in \({X} \/ {X+I} \/ {X-I}). /* % version 2: strong but very inefficient version no_threat(X, Y, I) +: X in unionof(B,dom(Y),\({B} \/ {B+I} \/ {B-I})), Y in unionof(B,dom(X),\({B} \/ {B+I} \/ {B-I})). % version 3: strong but somewhat inefficient version no_threat(X, Y, I) +: X in (4..card(Y)) ? (inf..sup) \/ unionof(B,dom(Y),\({B} \/ {B+I} \/ {B-I})), Y in (4..card(X)) ? (inf..sup) \/ unionof(B,dom(X),\({B} \/ {B+I} \/ {B-I})). */ | ?-queens(8, L, [ff]).L = [1,5,8,6,3,7,2,4]