/* 

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

  Note: This is much slower (for N=12) than approach #1.

  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.


%  Figure 4.12  Program 2 for the eight queens problem.

% solution( Queens): 
%   Queens is a list of Y-coordinates of eight non-attacking queens
solution( Queens)  =>
   permutation2( [1,2,3,4,5,6,7,8], Queens),
   safe( Queens).

% Generalized version
solution2(N, Queens)  =>
   % permutation( 1..N, Queens), % built-in Picat predicate
   permutation2( 1..N, Queens), % built-in Picat predicate
   safe( Queens).


permutation2([],PermList) ?=> PermList = [].
permutation2([Head|Tail], PermList) =>
   permutation2( Tail, PermTail),
   del( Head, PermList, PermTail).   % Insert Head in permuted Tail 

% del( Item, List, NewList): deleting Item from List gives NewList
del( Item, ItemList, List) ?=> 
  ItemList = [Item | List].

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

% safe( Queens): 
%   Queens is a list of Y-coordinates of non-attacking queens

safe([] ) ?=> true.
safe([Queen|Others]) =>
   safe( Others),
   noattack( Queen, Others, 1).

noattack( _, [], _) ?=> true.
noattack( Y, [Y1 | Ylist], Xdist) =>
   Y1-Y =\= Xdist,
   Y-Y1 =\= Xdist,
   Dist1 is Xdist + 1,
   noattack( Y, Ylist, Dist1).