% generated: 10 November 1989
% option(s): 
%
%   (queens) queens_8
%
%   from Sterling and Shapiro, "The Art of Prolog," page 211.
%
%   This program solves the N queens problem:  place N pieces on an N
%   by N rectangular board so that no two pieces are on the same line
%   - horizontal, vertical, or diagonal.  (N queens so placed on an N
%   by N chessboard are unable to attack each other in a single move
%   under the rules of chess.)  The strategy is incremental generate-
%   and-test.
%
%   A solution is specified by a permutation of the list of numbers 1 to
%   N.  The first element of the list is the row number for the queen in
%   the first column, the second element is the row number for the queen
%   in the second column, et cetera.  This scheme implicitly incorporates
%   the observation that any solution of the problem has exactly one queen
%   in each column.
%
%   The program distinguishes symmetric solutions.  For example, 
%
%   ?- queens(4, Qs).
%
%   produces
%
%   Qs = [3,1,4,2] ;
%
%   Qs = [2,4,1,3]

:- main.

q:- 	statistics(runtime,_), 
	queens(16,L), statistics(runtime,[_,Y]), 
	write(L), nl,
	write('time : '), write(Y), nl,
	halt_or_else(0,true).




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




queens([],Qs,Qs).

queens(UnplacedQs,SafeQs,Qs):-
	sel(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).




sel([X|Xs],Xs,X).

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




range(N,N,[N]):- !.

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




:- q.