/* 

  Nqueens problem in Picat.
  
  From Bratko: Prolog Programming for AI, 4th edition, page 11ff
  Third approach.

  This is faster than approach 1, and _much_ faster than Approach 2 (permutation).
  N=12 for 
    Approach 1 (nqueens_bratko1.pi): 4.3s
    Approach 2 (nqueens_bratko2.pi): >many minutes
    Approach 3 (this program): 
        - Bratko's generalization in solution2/1: 3.7s
        - My generalization using Picat lists in solution3/1: 12.9s

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import util.
% import cp.


main => go.


go ?=>
  solution(Queens),
  println(q=Queens),
  fail,
  nl.

go => true.

go2 =>
  Map = get_global_map(),
  Map.put(count,0),
  N = 12,
  solution2(N,Queens),
  Map.put(count,Map.get(count)+1),
  println([Queens,Map.get(count)]),
  fail,
  nl.

go3 =>
  Map = get_global_map(),
  Map.put(count,0),
  N = 12,
  solution3(N,Queens),
  Map.put(count,Map.get(count)+1),
  println([Queens,Map.get(count)]),
  fail,
  nl.


% Figure 4.14   Program 3 for the eight queens problem.

% solution( Ylist): 
%   Ylist is a list of Y-coordinates of eight non-attacking queens

solution(Ylist) =>
  sol( Ylist,                                    % Y-coordinates of queens
       [1,2,3,4,5,6,7,8],                        % Domain for X-coordinates
       [1,2,3,4,5,6,7,8],                        % Domain for Y-coordinates
       [-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7],   % Upward diagonals
       [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] ). % Downward diagonals 

sol( Y, X, _Dy, _Du, _Dv) ?=> Y = [], X = [].
sol(YYlist , XDX1, Dy, Du, Dv)  =>
  YYlist = [Y | Ylist],
  XDX1 = [X | Dx1],
  del( Y, Dy, Dy1),                 % Choose a Y-coordinate
  U is X-Y,                         % Corresponding upward diagonal
  del( U, Du, Du1),                 % Remove it
  V is X+Y,                         % Corresponding downward diagonal
  del( V, Dv, Dv1),                 % Remove it
  sol( Ylist, Dx1, Dy1, Du1, Dv1).  % Use remaining values 

del(Item, ItemList, List) ?=> 
  ItemList = [Item | List].

del(Item, FirstList, FirstList1)  =>
   FirstList = [First | List],
   FirstList1 = [First | List1],
   del(Item, List, List1).


% general solution (page 114)
gen(N1,N2,N3) ?=> N1 = N2, N1 = N,N3=[N].
gen(N1,N2,N1List) =>
  N1List=[N1|List],
  N1 < N2,
  M is N1 + 1,
  gen(M,N2,List).

solution2(N,S) =>
  gen(1,N,Dxy),
  Nu1 is 1-N, Nu2 is N-1,
  gen(Nu1,Nu2,Du),
  Nv2 is N+N,
  gen(2,Nv2,Dv),
  sol(S,Dxy,Dxy,Du,Dv).
  
% My version using Picat lists instead
solution3(N,S) => 
  L = 1..N,
  L2 = [I : I in -N-1..N-1],
  L3 = [I : I in 2..N*N],  
  sol(S,
    L,
    L,
    L2,
    L3).