/* 

  N-Queens problem in "pure" logic programming in Picat.

  Well, it's not really a "true" LP program since it use foreach/1 but
  it's only permutation/2 and !=/2.

  Inspired by the Prolog version from
  L. Sterling and E. Shapiro: "The Art of Prolog" (chapter 14)

  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 =>
  foreach(N in 2..10)
    time(All=findall(_, queens_lp(N,_X))),
    println([N=All.length])
  end,
  nl.

% first solution
go2 => 
  foreach(N in 2..20)
    time(queens_lp(N,X)) -> 
       println(N=X)   
    ;
      true
  end,
  nl.

% Prolog version
go3 => 
  queen_allw(8),
  nl.

go4 => 
  foreach(N in 2..20)
    println(n=N),
    ( time(queen_all(N))  ; true )
  end,
  nl.


% "Pure" LP
queens_lp(N,X) =>
   X = new_list(N),
   permutation(X,1..N),
   foreach(I in 1..N, J in I+1..N) 
      X[I]-I != X[J]-J,
      X[I]+I != X[J]+J
   end.


%
% Prolog version from
% L. Sterling and E. Shapiro: "The Art of Prolog" (chapter 14)
%
queen_all(N) ?=>
  queens(N, Q),
%  write(q=Q), nl,
  fail.
queen_all(_) => true.

% write the solutions
queen_allw(N) ?=>
  queens(N, Q),
  write(q=Q), nl,
  fail.
queen_allw(_) => true.


queens(N, Qs) =>
  range(1, N, Ns),
  queens(Ns, [], Qs).

queens(UnplacedQs, SafeQs, Qs) ?=>
  select(Q, UnplacedQs, UnplacedQs1),
  not attack(Q, SafeQs),
  queens(UnplacedQs1, [Q|SafeQs], Qs).
queens([], Qs, Qs1) => Qs = Qs1.

attack(X, Xs) =>
  attack(X, 1, Xs).

attack(X, N, [Y|_Ys]) ?=>
  X is Y + N.
attack(X, N, [Y|_Ys]) ?=>
  X is Y - N.
attack(X, N, [_Y|Ys]) =>
  N1 is N + 1,
  attack(X, N1, Ys).

range(M, N, NMs) ?=>
  [M|Ns] = NMs,
  M < N, 
  M1 is M + 1, 
  range(M1, N, Ns).
range(N, N1, L) => 
  N=N1, 
  L = [N].