/* 

  Dudeney's Bishop Placement problem 1 in Picat.

  From Martin Chlond Integer Programming Puzzles:

  http://www.chlond.demon.co.uk/puzzles/puzzles1.htm2, puzzle nr. 7
  Description  : Dudeney's bishop placement problem I
  Source       : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
  """
  7. Place as few bishops as possible on an ordinary chessboard so that every 
  square of the board shall be either occupied or attacked. (Dudeney)
  """

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


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

*/


% import sat. % 13.9s
import mip. % 0.17s
% import cp.

main => go.

go => 

   Size = 8,
 
   X = new_array(Size,Size), % x(i,j) = 1 if square (I,J) occupied, 0 otherwise
   X :: 0..1, 
   A = new_array(Size,Size), % a(i,j) = 1 if square (I,J) attacked, 0 otherwise
   A :: 0..1,

   SumX #= 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])  
      ) #>= A[I,J] 
   end,

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

  Vars = X.to_list() ++ [SumX] ++ A.to_list(),
  % minimize number of bishops
  solve($[min(SumX),report(print_sol(X,A,SumX)),ffc,split],Vars),


  print_sol(X,A,SumX),

  nl.


print_sol(X,A,SumX) => 
  println(sumX=SumX),
  println("X:"),
  foreach(Row in X) println(Row.to_list()) end,
  println("A:"),
  foreach(Row in A) println(Row.to_list()) end,
  nl.