%
% Non-dominating queens problem:
%
% Place N queens on an NxN board such that the minimal number
% of squares is under attack. The queens may attack each other.
%
% Author: Joachim Schimpf, IC-Parc
% Requires: ECLiPSe>=5.8
%
:- lib(ic).
:- lib(branch_and_bound).
ndq(N, Board, Attacked, NAttacks) :-
dim(Board, [N,N]), % Bool: field [I,J] is occupied
flatten_matrix(Board, Fields),
Fields :: 0..1,
sum(Fields) #= N,
dim(Attacked, [N,N]), % Bool: field [I,J] is under attack
flatten_matrix(Attacked, Attacks),
Attacks :: 0..1,
NAttacks #= sum(Attacks),
( multifor([I,J],1,N), param(Board,Attacked,N) do
findall(K-L,
(between(1,N,1,K), between(1,N,1,L), attacks(K,L,I,J)),
AttackPos),
( foreach(K-L,AttackPos), param(Board,Attacked,I,J) do
Attacked[I,J] #>= Board[K,L]
)
),
bb_min(labeling(Fields), NAttacks, _).
attacks(K,L,I,J) :- % field [K,L] attacks [I,J]
( K =:= I -> true
; L =:= J -> true
; K-L =:= I-J -> true
; K+L =:= I+J
).
flatten_matrix(M, Xs) :-
dim(M, Dims),
( multifor(Index,1,Dims), foreach(X,Xs), param(M) do
subscript(M, Index, X)
).