/* Das N-Damen-Problem:  */


allqueens(N,Ds):- queens1(range 1 N,[],Ds),false. 
queens(N,Ds):- queens1(range 1 N,[],Ds).

queens1([],Ds,Es):-Ds=Es.
queens1(Dsunp,Dssicher,Ds):- select(D, Dsunp, Ds1unp) ,
                           noattack(D,Dssicher),
                           queens1(Ds1unp,[D|Dssicher],Ds).


range N1 N2 :=if (N1 = N2) then [N1].
range N1 N2 :=if (N1 ~= N2) then [N1|range (N1+1) N2].

sicher([D|Ds]):- sicher(Ds),noattack(D,Ds).
sicher([]).

select(Y,[X|Xs],Zs) :- X=Y,Zs=Xs.
select(Y,[X|Xs],[Z|Zs]) :- X=Z,select(Y,Xs,Zs).


noattack(X,Xs):-noattack1(X,1,Xs).

noattack1(X,N,[]). 
noattack1(X,N,[Y|Ys]):-  ((X ~= (Y+N) ) , ( X~= (Y-N) ) ) , 
                             noattack1(X,(N+1),Ys). 

append [X|Ys] Zs := [X|append Ys Zs].
append []     Zs := Zs.
 
/* goals: queens(8,DS) allqueens(8,DS) */