/* 

  Kraitchik's queen placement problem in Picat.

  From Martin Chlond Integer Programming Puzzles:
  http://www.chlond.demon.co.uk/puzzles/puzzles2.html, puzzle nr. 9. 
  Description  : Kraitchik's queen placement problem
  Source       : Kraitchik, M., (1942), Mathematical Recreations, W.W. Norton and Company, Inc.
  """
  How many queens are needed, and in what position, so that every unoccupied square of the chessboard is
  under direct attack from some queen?

  (Kraitchik)
  """
  This model was inspired by the XPress Mosel model created by Martin Chlond.
  http://www.chlond.demon.co.uk/puzzles/sol2s9.html


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

*/


import mip. % 0.95s
% import cp. % 11.9s
% import sat. % 31.7s


main => go.

go =>
  Size = 8,

  % decision variables

  % x(i,j) = 1 if occupied, 0 otherwise
  X = new_array(Size, Size),
  X :: 0..1, 

  % a(i,j) = 1 if attacked, 0 otherwise
  A = new_array(Size, Size),
  A :: 0..1,

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

  % a[i,j] = 0 if square (i,j) not 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]) + 
     sum([X[I,N] : N in 1..Size, N != J])  #>= A[I,J]
  end,

  % each square either attacked or occupied
  foreach(I in 1..Size,J in 1..Size)
     A[I,J]+X[I,J] #= 1
  end,

  solve($[ff,split, min(NumQ)], X ++ A), 
  
  println(numQ=NumQ),
  print_matrix("X:", X),
  print_matrix("A:", A),
  
  nl.

print_matrix(Name,M) =>
  println(Name),
  foreach(Row in M)
    println(Row.to_list())
  end,
  nl.