% Ex 4.6[B]

%  Figure 4.7  Program 1 for the eight queens problem.
% solution( BoardPosition) if
%   BoardPosition is a list of non-attacking queens

solution( [] ).

solution( [X/Y | Others] )  :-	  % First queen at X/Y, other queens at Others
  solution( Others),
  member( Y,[1,2,3,4,5,6,7,8]),   % Order of alternatives defined here!
  noattack( X/Y, Others).           % First queen does not attack others

noattack( _, [] ).                  % Nothing to attack

noattack( X/Y, [X1/Y1 | Others] )  :-
  Y =\= Y1,                         % Different Y-coordinates
  Y1-Y =\= X1-X,                    % Different diagonals
  Y1-Y =\= X-X1,
  noattack( X/Y, Others).

% A solution template

template( [1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8] ).

solution1(S) :- template(S), solution(S).

% When computing all solutions, all orders are equivalent:
/*  Original Order:  member( Y,[1,2,3,4,5,6,7,8])
4 ?- time(setof(S,solution1(S),L)), length(L,N).
% 171,051 inferences in 0.22 seconds (776387 Lips) */
/* More informed order: member( Y,[1,3,5,7,2,4,6,1])
16 ?- time(setof(S,solution1(S),L)), length(L,N).
% 171,051 inferences in 0.22 seconds (776387 Lips)
*/

% When computing one solution, the informed order is much better:
/* More informed order: member( Y,[1,3,5,7,2,4,6,1])
18 ?- time(solution1(S)).
% 368 inferences in 0.00 seconds (Infinite Lips) */
/* Original Order:  member( Y,[1,2,3,4,5,6,7,8])
19 ?- time(solution1(S)).
% 9,382 inferences in 0.01 seconds (936851 Lips)
*/