/* queens(N,Queens) :-
Queens is a placement that solves the N queens problem,
represented as a permutation of the list of numbers [1,2,..,N].
*/
queens(N,Qs) :- range(1,N,Ns), queens(Ns,[],Qs).
queens(UnplacedQs,SafeQs,Qs) :-
select(Q,UnplacedQs,UnplacedQs1),
not attack(Q,SafeQs),
queens(UnplacedQs1,[Q|SafeQs],Qs).
queens([],Qs,Qs).
range(I,N,[I|Ns]) :- I < N, I1 is I+1, range(I1,N,Ns).
range(N,N,[N]).
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]) :- select(X,Ys,Zs).
attack(X,Xs) :- attack(X,1,Xs).
attack(X,N,[Y|Ys]) :- X is Y+N ; X is Y-N.
attack(X,N,[Y|Ys]) :- N1 is N+1, attack(X,N1,Ys).
% Program 14.3: Placing one queen at a time