/* 

  Schuh's queen placement problem in Picat.

  From Martin Chlond Integer Programming Puzzles:
  http://www.chlond.demon.co.uk/puzzles/puzzles2.html, puzzle nr. 10.
  Description  : Schuh's queen placement problem
  Source       : Schuh, F., (1943), Wonderlijke Problemen;
                 Leerzam Tijdverdrijf Door Puzzle en Speel, W.J. Thieme & Cie, Zutphen.
  """
  Place eight queens on a chessboard in such a way that none of the queens is attacking another queen.

  (Schuh)
  """

  This model was inspired by the XPress Mosel model created by Martin Chlond.
  http://www.chlond.demon.co.uk/puzzles/sol2s10.html


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

*/

% import sat. % 6.1s
import cp. % 0.008s
% import mip. % 0.13s

main => time2(go).

go =>
  Size = 8,

  % X[I,J] = 1 if square occupied, 0 otherwise
  X = new_array(Size,Size),
  X :: 0..1,
  % A[I,J] = 1 if square attacked, 0 otherwise
  A = new_array(Size,Size),
  A :: 0..1, 

  NumQ #= sum([X[I,J] : I in 1..Size, J in 1..Size]),
  NumQ #=< Size,

  % a(i,j) = 1 if square (i,j) attacked
  foreach(I in 1..Size, J in 1..Size) 
        sum([X[M,M-I+J] : M in 1..Size, M != I, M-I+J >= 1, M-I+J <= Size])  +
        sum([X[M,I+J-M] : M in 1..Size, M != I, I+J-M >= 1, I+J-M <= Size])  +
        sum([X[M,J] : M in 1..Size, M != I])  + 
        sum([X[I,N] : N in 1..Size, N != J])  #=< 99*A[I,J],

        % each square either attacked or occupied
        A[I,J]+X[I,J] #= 1        
  end,

  
  solve($[ff,max(NumQ)], A ++ X),  

  println(numQ=NumQ),
  println("X:"),
  print_mat(X),
  printf("Queens positions: %w\n", [[J : J in 1..Size, X[I,J] == 1] : I in 1..Size].flatten()),
  println("A:"),
  print_mat(A),
  
  nl.


print_mat(X) =>
  foreach(Row in X) 
    println(Row.to_list())
  end.