Next: Cumulative Scheduling, Previous: Send More Money, Up: CLPFD Example Programs [Contents][Index]
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 bounds 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]