/* 

  Nqueens problem in Picat.
  
  From Bratko: Prolog Programming for AI, 4th edition, page 105ff
  First approach.
 
  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.

main => go.


go ?=>
  template(S), % for N = 8
  solution(S),
  println(S),
  fail,
  nl.

go => true.

% More general solution
% N=12: 3.8s
go2 ?=>
  N = 12,
  % S = $[(I/Y) : I in 1..N],
  % S=template2(N),
  template3(N,S),
  solution2(N,S),
  println(s=S),
  fail,
  
  nl.

go2 => true.

% Figure 4.10: Program 1 for eight queens
% solution( BoardPosition) if BoardPosition is a list of non-attacking queens
solution([]) ?=> true.
solution([$(X/Y) | Others] ) =>           % First queen at X/Y, other queens at Others
    solution( Others),                  % Find solution for all other queens
    member( Y, [1,2,3,4,5,6,7,8] ),     % Choose Y coordinate of first queen
    noattack( $(X/Y), Others).             % First queen does not attack others

% hakank: General solution
solution2(_,[]) ?=> true.
solution2(N,[$(X/Y) | Others] ) =>           % First queen at X/Y, other queens at Others
    solution2(N, Others),                  % Find solution for all other queens
    member( Y, 1..N),     % Choose Y coordinate of first queen
    noattack( $(X/Y), Others).             % First queen does not attack others


noattack(_, []) ?=> true.               % Nothing to attack
noattack(XY, [$(X1/Y1)|Others] ) =>
    XY = $(X/Y),
    Y =\= Y1,                           % Different Y-coordinates
    Y1 - Y =\= X1 - X,                  % Different upward diagonals
    Y1 - Y =\= X - X1,                  % Different downward diagonals
    noattack( XY, Others).

% A solution template
template(Template) => 
  Template = $[(1/Y1),(2/Y2),(3/Y3),(4/Y4),(5/Y5),(6/Y6),(7/Y7),(8/Y8)].

% hakank: General solution template
template2(N) = $[(I/Y) : I in 1..N].
template3(N,T) => 
  template3(N,[],T).
template3(0,T1,T2) ?=> T1=T2.
template3(N,T1,T2) ?=>
   N > 0,
   N1 = N-1,
   template3(N1,[$(N/Y)] ++ T1,T2).