% eight_queens([X1,X2,X3,X4,X5,X6,X7,X8]) : the  Xi are the positions (on 
% columns) of eight queens on a chessboard so that no two queens attack each other

eight_queens([X1,X2,X3,X4,X5,X6,X7,X8]) :-
	perm([5,4,6,3,7,2,1,8],[X1,X2,X3,X4,X5,X6,X7,X8]),
	verify([X1,X2,X3,X4,X5,X6,X7,X8]).

verify([]).
verify([X1|X_s]) :-
	noattack(X1,X_s,1),
	verify(X_s).

noattack(X,[],N).
noattack(X_i,[X_j|X_s],N) :-
	 D1 is X_j - N,
	 D2 is X_j + N,
	 X_i \== D1,
	 X_i \== D2,
	 N1 is N+1,
	 noattack(X_i,X_s,N1).

% perm(L1,L2) : L1 is a permutation of L2
perm([],[]) .
perm([H|T],L):-
	select(H,L,R_est),
	perm(T,R_est).

select(H,[H|R_est],R_est) .
select(X,[H|T],[H|R]) :-
	select(X,T,R).



/* eight_queens([X1,X2,X3,X4,X5,X6,X7,X8]). 
| ?- eight_queens(L).

L = [1,5,8,6,3,7,2,4]

L = [1,6,8,3,7,4,2,5]

L = [1,7,4,6,8,2,5,3]
...
*/