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

% $Id: 090,v 1.3 2000/08/26 14:02:58 peteg Exp $

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([Y|Ys], X, N) :-
	X =\= Y + N, X =\= Y - N,
	N1 is N + 1,
	not_attack(Ys,X,N1).

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

%main :- queens2(4, Queens), write(Queens), nl.

main :- count_queens.

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