% % 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) ).