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 bound-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, 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]