:- use_module(library(lists)).
queens(N, L) :-
    generate(Ln,1,N),
    permutation(Ln, L),
    check_constrain_all(L).
generate([N],N,N).
generate([S|Xs],S,N):-
    S < N,
    S1 is S+1,
    generate(Xs,S1,N).


check_constrain_all([]).
check_constrain_all([X|Xs]) :-
     constrain_between(X, Xs, 1),
     check_constrain_all(Xs).

constrain_between(_X, [], _N).
constrain_between(X, [Y|Ys], N) :-
     no_threat(X, Y, N),
     N1 is N+1,
     constrain_between(X, Ys, N1).

no_threat(X, Y, I) :-
        X   \= Y,
        XI is X+I,
        XI \= Y,
        X_I is X-I,
        X_I \= Y.

queens2(N, L) :-
    generate(Ln,1,N),
    length(L,N),
    gen_and_test(Ln,L,N,1).
gen_and_test([],_,_,_).
gen_and_test(Ln,L,N,Nc):-
    Nc =< N,
    nth(Nc,L,X), 
    select(X,Ln,Lnr),
    length(Lc,Nc),
    prefix(Lc,L),
    check_constrain_all(Lc),
    Nc1 is Nc +1,
    gen_and_test(Lnr,L,N,Nc1). 

/*
| ?- queens(8, L).
L = [1,5,8,6,3,7,2,4]
| ?- statistics(runtime,V).
V = [400,260] ?  
| ?- queens(12, L).
L = [1,3,5,8,10,12,6,11,2,7|...] ?
| ?-  statistics(runtime,V).
V = [195980,195580]

?-  queens2(8,L).
L = [1,5,8,6,3,7,2,4] ?
| ?- statistics(runtime,V).
V = [230,60] ?
| ?- queens2(12,V).
V = [1,3,5,8,10,12,6,11,2,7|...] ?
| ?- statistics(runtime,V).
V = [640,410]
| ?- queens2(16,V).
V = [1,3,5,2,13,9,14,12,15,6|...] ?
| ?- statistics(runtime,V).
V = [38310,37670] 

 */