% -*- Prolog -*-
%
% N-queens solver.
%  from the Prolog benchmarks.
%

% $Id: 220,v 1.1 2000/11/12 12:22:46 peteg Exp $

:- list(X) ::= [] ; [X | list(X)].
:- compile(not_attack/3).
:- compile(range/3).

queens(N,Qs) :-
	range(1,N,Ns),
	queens(Ns,[],Qs).

queens([],Qs,Qs).
queens(UnplacedQs,SafeQs,Qs) :-
	select(UnplacedQs,UnplacedQs1,Q),
	not_attack(SafeQs,Q),
	queens(UnplacedQs1,[Q|SafeQs],Qs).

not_attack(Xs,X) :-
	not_attack(Xs,X,1).

not_attack([],_,_).
%not_attack(_A0, _B0, _C0) :-
%        unify(_A0, []).
not_attack([Y|Ys], X, N) :-
	X =\= Y + N,
	X =\= Y - N,
	N1 is N + 1,
	not_attack(Ys,X,N1).
%not_attack(_A0, _B0, _C0) :-
%        unify(_A0, [_D0|_E0]),
%        is_not_equal(_B0, +(_D0, _C0)),
%        is_not_equal(_B0, -(_D0, _C0)),
%        is(_F0, +(_C0, 1)),
%        not_attack(_E0, _B0, _F0).

select([X|Xs],Xs,X).
select([Y|Ys],[Y|Zs],X) :- select(Ys,Zs,X).

range(N,N,[N]) :- !.
range(M,N,[M|Ns]) :-
	M < N,
	M1 is M + 1,
	range(M1,N,Ns).

% The driver / count solutions stuff.
%:- dynamic(count/1).

count_queens :-
%	asserta(count(0)),
	queens(8, Queens),
%	write(Queens), nl,
%	count(X),
%	retract(count(X)),
%	X1 is X + 1,
%	asserta(count(X1)),
	fail.
%count_queens :-
%	count(X),
%	write("Number of solutions = "), write(X), nl,
%	retract(count(X)).
count_queens.

% Benchmarking
benchmark :-
	benchmark(50).

benchmark(0) :- !.
benchmark(X) :-
	count_queens,
	X0 is X - 1,
	benchmark(X0).

%main :- queens(8, Queens), write(Queens), nl.
