/* 

  Queens (11x11) problem in Picat.

  Port of Trealla's Prolog code samples/queens11.pl
  https://github.com/infradig/trealla/blob/master/samples/queens11.pl
  """
  % Find all solutions of an 11 by 11 board.
  % The \+ with the fail is a trick to make it find all solutions.
  """

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

*/

import v3_utils.

main => go.

% 0.151s
go ?=>
  test,
  
  nl.
go => true.

% 0.137s
go2 ?=>
  testq,
  
  nl.
go2 => true.


% From https://github.com/infradig/trealla/blob/master/samples/queens11.pl

% Find all solutions of an 11 by 11 board.
% The \+ with the fail is a trick to make it find all solutions.


test :- queens(11,Qs), write(Qs), nl, fail.
test.

testq :- queens(11,_Qs), fail.
testq.

queens(N,Qs) :- rangeList(1,N,Ns), queens3(Ns,[],Qs).

queens3(UnplacedQs,SafeQs,Qs) :-
    selectq(Q,UnplacedQs,UnplacedQs1),
    \+ attack(Q,SafeQs),
    queens3(UnplacedQs1,[Q|SafeQs],Qs).
queens3([],Qs,Qs).

attack(X,Xs) :- attack3(X,1,Xs).

attack3(X,N,[Y|_]) :- (X =:= Y+N) ; (X =:= Y-N).
attack3(X,N,[_|Ys]) :- N1 is N+1, attack3(X,N1,Ys).

rangeList(M,N,[M]) :- M >= N, !.
rangeList(M,N,[M|Tail]) :- M1 is M+1, rangeList(M1,N,Tail).

selectq(X,[X|Xs],Xs).
selectq(X,[Y|Ys],[Y|Zs]) :- selectq(X,Ys,Zs).