%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Exercise 4: Inefficient alternative solution

/* This solution differs for the definition of safe(Pos): 
   we first generate the list of pairs represented by Pos,
   then we check that there are no two arbitrary pairs
   which are in the same diagonal. 
   This solution is more clear, but less efficient than the 
   previous one because of the way negation is used.
*/

queens(N,Pos) :- generate(N,Pos), safe(Pos).

generate(N,Pos) :- list_from_1_to_N(N,L), perm(L,Pos).

list_from_1_to_N(N,L) :- gen(1,N,L).
gen(J,N,[J|L]) :- J<N, J1 is J+1, gen(J1,N,L).
gen(N,N,[N]).

perm([],[]).
perm(L,[X|K]) :- append(L1,[X|L2],L), append(L1,L2,M), perm(M,K).

safe(Pos) :- positions(Pos,Pairs), not(diag_attack(Pairs)).

positions(Pos,Pairs) :- aux(Pos,Pairs,1).
aux([C],[(R,C)],R).
aux([C|Pos],[(R,C)|Pairs],R) :- R1 is R+1, aux(Pos,Pairs,R1). 

diag_attack(Pairs) :- occurs((I1,J1),Pairs), 
                      occurs((I2,J2),Pairs), not(I1=I2),
                      (J1+I1=:=J2+I2; J1-I1=:=J2-I2).

occurs((I,J),[(I,J)|_]).
occurs((I,J),[(_,_)|L]) :- occurs((I,J),L).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
