/* 

  N-queens (from Markus Triska's Prolog code) in Picat v3.

  Here are the three n-queens implementations that Markus Triska 
  showed in 
  "N-Queens in Prolog"
  https://www.youtube.com/watch?v=l_tbL9RjFdo&t=2s

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

*/

import cp.
import v3_utils.

main => go.

% slow
go ?=> 
  N = 4,
  bp.length(Qs,N),
  maplist($between(1,N),Qs),
  n_queens(N,Qs),
  println(qs=Qs),
  fail,
  nl.

go => true.

% a little faster
go2 ?=>
  n_queens3(N1,[2,4,1,3]),
  println(n1=N1),
  n_queens3(N2,[2,4,C,D]),
  println([n2=N2,c=C,d=D]),
  nl.

go2 => true.

% faster
go3 ?=>
  N = 100,
  n_queens3(N, Qs),
  println(qs=Qs),
  if N < 12 then
    fail
  end,
  
  nl.

go3 => true.


n_queens(N, Qs) =>
  bp.length(Qs, N),
  Qs :: 1..N,
  safe_queens(Qs).

% version 3
n_queens3(N, Qs) =>
  bp.length(Qs, N),
  Qs :: 1..N,
  safe_queens(Qs),
  solve($[ffc],Qs).

safe_queens([]) ?=> true.
safe_queens([Q|Qs]) => 
  safe_queens_(Qs,Q,1),
  safe_queens(Qs).

safe_queens_([],_,_) ?=> true.
safe_queens_([Q|Qs],Q0,D0) =>
  Q #!= Q0,
  abs(Q0-Q) #!= D0,
  D #= D0 +1,
  safe_queens_(Qs,Q0,D).