% file:    queens.pl
% author:  Robert Keller
% purpose: Illustrate non-deterministic or backtrack programming, wherein
% we can use the rationale in finding a single solution to find all solutions.

% queens(N, Solution) produces solutions to the N-queens problem.

queens(N, Solution) :- 
    revRange(1, N, Range),              % produce Range [N, N-1, ..., 1]
    solve(Range, Range, [], Solution).  % solve the problem


% solve(Cols, Rows, Acc, Solution)

solve([], _, Acc, Acc).         % No more columns, solution achieved in Acc.

solve([Col | Cols], Rows, Acc, Sol) :-  % Extend the partial solution Acc.
    member(Row, Rows, Residue),         % Choose a Row to pair with Col.
    noAttack([Col, Row], Acc),          % The new pair cannot attack others.
    solve(Cols, Residue, [[Col, Row] | Acc], Sol).      % Extend to Cols.


% noAttack([Col, Row], Pairs) succeeds if pair [Col], Row] does not
% attack the other Pairs, assuming the other Pairs don't attack each other.

noAttack(_, []).                % No more pairs to check

noAttack([Col1, Row1], [[Col2, Row2] | Pairs]) :-       % Check [Col2, Row2].
    Col1 =\= Col2,                                      % not same column
    Row1 =\= Row2,                                      % not same row
    abs(Col1-Col2) =\= abs(Row1-Row2),                  % not same diagonal
    noAttack([Col1, Row1], Pairs).                      % Check rest of pairs.


% member(A, L, R) selects a member A from list L, with R as the residue.

member(A, [A | X], X).                              % Choose the first memeber.
member(A, [B | X], [B | Y]) :- member(A, X, Y).     % Choose another member.


% revRange(M, N, R) makes R be [N, N-1, N-2, ..., M]

revRange(M, N,      []) :- M > N.
revRange(M, N, [N | L]) :- M =< N, N1 is N-1, revRange(M, N1, L).


% show the solutions for specific N:

test(N) :-
    setof(Solution, queens(N, Solution), Set) ->
      (
      length(Set, L),
      nl, write('There are '), write(L), write(' solutions for '), write(N), 
      write(' queens:'),
      nl, nl,
      member(X, Set, _),
      write(X),
      nl, nl,
      fail
      )
    ; nl, write('There is no solution for '), write(N), write(' queens.'), nl.

test(_).	% always succeed.

:- test(4).	% sample test