% simple solution to nqueens as example of generate and test method

nqueens(N,Q):-integers(1,N,[],Ints),perm(Ints,Q),safe(Q).

safe([]).
safe([H|T]):-safe(T),not(attack(H,T)).

attack(H,T):-diag(H,1,T).

diag(Q,N,[H|T]):-Q =:= H + N.
diag(Q,N,[H|T]):-Q =:= H - N.
diag(Q,N,[H|T]):-N2 is N + 1, diag(Q,N2,T).

integers(N,N,Sofar,[N|Sofar]):-!.
integers(N,M,Sofar,List):-N2 is N + 1, integers(N2,M,[N | Sofar],List).

perm([],[]).
perm(L,[H|T]):-remove(H,L,L2),perm(L2,T).

remove(H,[H|T],T).
remove(X,[H|T],[H|T2]):-remove(X,T,T2).

% better solution to nqueens problem
% the test is pushed inside the generator, so that unsucessful
% solutions are not fully generated.

queens(N,Q):-integers(1,N,[],Ints),q*(Ints,[],Q).

q*([],Queens,Queens).
q*(Unplaced,Safe,Queens):-remove(Next,Unplaced,Rest), not(diag(Next,1,Safe)),
                          q*(Rest,[Next|Safe],Queens).