/* 

  queens benchmark in Picat.

  From 
  http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/15_stdy/06_bench/09_programs/07_queens/01_queens.p.html

  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,go2.

/**
 * Prolog code for the 9x9-queens benchmark.
 *
 * Originally conceived in by Max Bezzel for the 8x8 checker board.
 * Used by Edsger Dijkstra to illustrate the
 * depth-first backtracking search algorithm.
 *
 * Copyright 2010, XLOG Technologies GmbH, Switzerland
 * Jekejeke Prolog 0.8.3 (a fast and small prolog interpreter)
 */

nodiag([], _, _) => true.
nodiag([N|L], B, D) =>
      D != N - B,
      D != B - N,
      D1 = D + 1,
      nodiag(L, B, D1).

qdelete(L, A1, A2, L2) ?=> A1=A2,L2=L.
qdelete([H|T], X, A, AR) =>
      AR = [A|R],
      qdelete(T, X, H, R).

search([], _, Q) => Q=[].
search([H|T], History, QM) =>
      QM=[Q|M],
      qdelete(T, Q, H, L1),
      nodiag(History, Q, 1),
      search(L1, [Q|History], M).

index(-)
dataqueens([1,2,3,4,5,6,7,8,9]).

queens =>
   dataqueens(X),
   search(X,[],Y),
   writeln(Y).

queens2 =>
   dataqueens(X),
   search(X,[],_Y).


go => queens.

go2 => queens2.

go3 =>
   All=findall(Y, $search(1..8,[],Y)),
   writeln(All.length),
   nl.


go4 => 
   dataqueens(X),
   All=findall(Y, $search(X,[],Y)),
   writeln(All),
   nl.

go5 => 
   foreach(N in 6..30)
      time(search(1..N,[],Y)),
      writeln([N,Y])
   end,
   nl.

go6 => 
   foreach(_I in 1..10006)
      call(go)
   end.