%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%  The N Queens Problem  %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Last revision: August 2002 (G.Rossi)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% The problem.
% Place N queens on the chess board so that they do not 
% attack each other
%
% Data representation.
% The chess board of dimension N is represented as a set Board of N pairs 
% [Row,Colm]: [r,c] in Board means that a queen is placed on the chess board
% at row r and column c
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

queens(Board) :- 
  write('Give the dimension of the chess board: ') &
  read(N) &
  queens(Board,N).

queens(Board,N) :- 
  Board = {C : exists([X,V], C = [X,V] & X in int(1,N))} &
  forall(C in int(1,N), exists([R,CC],
                        R in int(1,N) & 
                        CC is C-1 &
                        forall(I in int(1,CC), admissible(Board,I,R,C)) &
                        [C,R] in Board)).

admissible(X,I,R,C) :-
    [I,V1] in X & V1 neq R &
    [I,W1] in X & W2 is R+C-I & W1 neq W2 &
    [I,Z1] in X & Z2 is R+I-C & Z1 neq Z2.


%%%%%%%%%%%%%%%%%%%%%%%  SAMPLE GOALS   %%%%%%%%%%%%%%%%%%%%%%%%%%

% {log}=> queens(Board).
% Give the dimension of the chess board: 4.
% Board = {[1,2],[2,4],[3,1],[4,3]}
% Another solution?  (y/n)y
% Board = {[1,3],[2,1],[3,4],[4,2]}
% Another solution?  (y/n)y
% no
%
% {log}=> queens(Board).
% Give the dimension of the chess board: 8
% Board = {[1,1],[2,5],[3,8],[4,6],[5,3],[6,7],[7,2],[8,4]}
% ...


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% start predicate
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

start :- 
   nl &
   write('*********************************************************************') & 
   nl &
   write('queens(-Board):') & nl &
   write('determine an admissible positioning of N queens on the chess board Board ') & 
   nl &
   write('*********************************************************************') & 
   nl & nl.

%:-start.