/* 

  n-queens (plain backtracking version) in Picat.

  Inspired by the Java code
  http://sadakurapati.wordpress.com/2013/12/10/n-queens-backtracking-algorithm/

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

*/


import options.

% call as
%   time picat nqueens_backtracking.pi n=8 print=1 sols=0
%   time picat nqueens_backtracking.pi n=10 print=0 sols=0
%   time picat nqueens_backtracking.pi n=7
% 
main(Args) => 
  Opt = options(Args,[n=8,print=1,sols=0]),
  println(opt=Opt),
  queens(Opt.get(n),Opt.get(sols),Opt.get(print),Count),
  println(count=Count),
  nl.

main => go.



go =>
  N = 8,
  Sols = 0,
  Print = 1,
  queens(N,Sols,Print,Count),
  println(count=Count),
  nl.


queens(N,Sols,Print,Count) =>
  Board = new_array(N),
  get_global_map().put(count,0),
  placeQueenOnBoard(1, Board,Sols,Print),
  Count = get_global_map().get(count),
  nl.


placeQueenOnBoard(Qi, Board,Sols,Print) =>
   N = Board.length,
   % base case
   if Qi == N+1 then
     % a valid configuration found.
     if Print > 0 then println(Board) end,
     Count := get_global_map().get(count) + 1,
     get_global_map().put(count,Count),
     if Sols > 0, Count >= Sols then
       halt
     end
   else
     % try to put the ith Queen (Qi) in all of the columns
     foreach(Column in 1..N) 
       if isSafePlace(Column, Qi, Board) == true then
          Board[Qi] := Column,
          % then place remaining queens
          placeQueenOnBoard(Qi+1, Board,Sols,Print)
          /**
           * backtracking. It is not required in this as we only look previously
           * placed queens in isSafePlace method and it doesnot care what values
           * are available in next positions.
           */
          % Board[Qi] := -1
       end
     end
   end.

% check if the column is safe place to put Qi (ith Queen)
isSafePlace(Column, Qi, Board) = Ret =>
  Ret1 = true,
  % check for all previously placed queens
  foreach (I in 1..Qi-1)
      % the ith Queen(previous) is in same column
      if (Board[I] == Column) then 
        Ret1 := false
      end,
      % the ith Queen is in diagonal
      % (r1, c1) - (r2, c1). if |r1-r2| == |c1-c2| then they are in diagonal
      if (abs(Board[I] - Column) == abs(I - Qi)) then
        Ret1 := false
      end
  end,
  Ret = Ret1.