Re: Non dominating queens problem

"TS" <chewthiamsoon@xxxxxxxxx> wrote in message news:<1114436008.632834.11670@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>...
> Hi, anyone got any solution in prolog to the non dominating queens
> problem?

:- import(const_domain).

queens(N, Queens) :-
make_queens(1, N, Queens),
Queens in 1..N,
queen_constraints(Queens),
!,
solution(Queens).

make_queens(N, Max, [_Queen|Queens]) :-
N =< Max,
N1 is N+1,
make_queens(N1, Max, Queens).
make_queens(N, Max, []) :- N > Max.

queen_constraints([]).
queen_constraints([Queen|Queens]) :-
noattack(Queens, Queen, 1), !,
queen_constraints(Queens).

noattack([], _, _).
noattack([OtherQueen|Queens], Queen, Dist) :-
Queen ?\= OtherQueen,
Queen ?\= OtherQueen + Dist,
Queen ?\= OtherQueen - Dist,
Dist1 is Dist + 1,
noattack(Queens, Queen, Dist1).

solution(Queens) :-
label(Queens, [card]).


A 100 queens takes 0.08 seconds on a PC
1000 queens takes somewhat longer!

CLP brings at least two orders of magnitude in performance improvement
for free as the code is the same essentially. After that you also need
to program CLP intelligently.

See www.ifcomputer.de ...
.

Relevant Pages