%
%  Eight-queens problem.
%

:- dynamic p/1.

%
%  queens(X) -
%    Returns in X a permutation of rows that solves the problem:
%      Generate a permutation and test if the configuration is safe.
%    The predicate p(N) is used to count backtracking.
%    The first solution will be returned after 2843 attempts.
%
queens([X1,X2,X3,X4,X5,X6,X7,X8]) :-
  retractall(p(_)), assert(p(0)),            % Initialize counter.
  permutation([X1,X2,X3,X4,X5,X6,X7,X8],
              [ 1, 2, 3, 4, 5, 6, 7, 8]),
  retract(p(K)), K1 is K + 1, assert(p(K1)), % Increment counter.
  safe([X1,X2,X3,X4,X5,X6,X7,X8]),
  retract(p(K2)), write(K2).                 % Print counter.

%
%  permutation(A, B) - A is a permutation of B.
%    Upon backtracking, generates new solutions.
%
permutation([], []).
permutation([Head|Tail], Numbers) :-
  select(Head, Numbers, NewNumbers),   % Note change in SWI 3.4.2.
  permutation(Tail, NewNumbers).

%
%  safe(List) -
%    List is a permutation of rows:
%      succeeds if this is a safe configuration for eight queens.
%    Checks each queen to see if is does not attack the others.
%
safe([]).
safe([Queen|Others]) :-
  noattack(Queen, Others),
  safe(Others).

%
%  noattack(Queen, Others) -
%    The Queen does not attack the Others.
%    Note that by using permutations,
%      there is no other queen in the same row/column.
%  noattack(Queen, Others, N) -
%    The Queen does not attack the Others on the diagonal:
%      check that the N'th Others is not +/- N rows from Queen.
%
noattack(Queen, Others) :-
  noattack(Queen, Others, 1).

noattack(_, [], _).
noattack(Queen, [Next|Others], N) :-
  Queen =\= Next - N,
  Queen =\= Next + N,
  N1 is N + 1,
  noattack(Queen, Others, N1).