/* 

  Dudeney's Bishop Placement problem 2 in Picat.

  From Martin Chlond Integer Programming Puzzles:

  http://www.chlond.demon.co.uk/puzzles/puzzles2.html, puzzle nr. 8 
  Description  : Dudeney's bishop placement problem II
  Source       : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
  """
  8. What is the greatest number of bishops that can be placed on the chessboard 
  without any bishop attacking another? (Dudeney)
  """

  This model was inspired by the XPress Mosel model created by Martin Chlond.
  http://www.chlond.demon.co.uk/puzzles/sol2s8.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.1s
import cp. % 3.7s
% import mip. % > 1min

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) = 1 if square (i,j) is 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])  
      ) #=< 99*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(),
  % maximise number of bishops
  solve($[max(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.