:- module(_,[queens/2],[assertions,regtypes,nativeprops]).

:- entry queens(A,B) : ( num(A), var(B) ).

:- pred queens(A,B) : ( num(A), var(B) ).

queens(A, B) :- queens_(A, B).

:- pred queens_(N, Qs) : (num(N), var(Qs)) => listnum(Qs).

queens_(N,Qs) :-
        range(1,N,Ns),
        perm(Ns,Qs),
        safe(Qs).

:- pred range(M, N, Ns) : (num(M), num(N)) => listnum(Ns).

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

:- pred perm(L1, L2) : listnum(L1) => listnum(L2).

perm([],[]).
perm([X|Y],[V|Res]) :-
        delete(V,[X|Y],Rest),
        perm(Rest,Res).

:- pred delete(El, L1, L2) : term * listnum * term => num * listnum * listnum.

delete(X,[X|Y],Y).
delete(X,[F|T],[F|R]) :-
        delete(X,T,R).

:- pred safe(L) : listnum(L).

safe([]).
safe([X|Y]) :-
        noattack(X,Y,1),
        safe(Y).

:- pred noattack/3 : num * listnum * num.

noattack(_X,[],_N).
noattack(X,[F|T],N) :-
        X=\=F,
        X=\=F+N,
        F=\=X+N,
        N1 is N+1,
        noattack(X,T,N1).

:- regtype listnum/1.
listnum([]).
listnum([X|Xs]) :- num(X), listnum(Xs).

