%LP 2011-2012  DCC-FCUP


rainhas(N,Rs):- range(1,N,Ns), perm(Ns,Rs), seguras(Rs).

%basta testar as diagonais
ataca(R,Rs):- ataca(R,1,Rs).

ataca(X,N,[Y|Ys]):- X is Y+N ;X is Y-N. 
ataca(X,N,[Y|Ys]):- N1 is N+1, ataca(X,N1,Ys).

seguras([]).
seguras([R|Rs]):- seguras(Rs), not ataca(R,Rs).

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

%length([],0).
%length([X|Y],N):- length(Y,N1), N is N1+1.

perm([],[]).
perm([X|Y],[U|V]):- delete(U,[X|Y],Z), perm(Z,V).

delete(X,[X|Y],Y).
delete(X,[Y|Z],[Y|Z1]):- delete(X,Z,Z1).

rainhas1(N,Rs):- range(1,N,Ns), rainhas(Ns,[],Rs).

rainhas([],Rs,Rs):-!.
rainhas(Naocoloc,Seguras,Rs):- delete(R,Naocoloc,Naocoloc1),
    not ataca(R,Seguras),
    rainhas(Naocoloc1,[R|Seguras],Rs).
