%
%  Eight-queens problem.
%  Improved solution: generate new queen only from partial
%    permutation that is safe so far.
%
:- dynamic p/1.

%
%  queens(X) -
%    Returns in X a permutation of rows that solves the problem.
%    The predicate p(N) is used to count backtracking.
%    The first solution will be returned after 336 attempts.
%
queens(X) :-
  retractall(p(_)), assert(p(0)),    % Initialize counter.
  queens(X, [], [1,2,3,4,5,6,7,8]),
  retract(p(K2)), write(K2).         % Print counter.

%
%  queens(Solution, Placed, Remaining)
%    Select Queen - a row number - from those remaining (initially 1..8).
%    If it does not attach those already Placed,
%      recurse to place the rest.
%    When the partial solution list Others is returned,
%      append Queen to the front of Others.
%
queens([], _, []).
queens([Queen|Others], Placed, Numbers) :-
  select(Queen, Numbers, NewNumbers),          % Note change in SWI 3.4.2.
  retract(p(K)), K1 is K + 1, assert(p(K1)),   % Increment counter
  noattack(Queen, Placed),
  queens(Others, [Queen|Placed], NewNumbers).

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).