/* 

  Knight domination puzzle in Picat.

  From Martin Chlond Integer Programming Puzzles:
  http://www.chlond.demon.co.uk/puzzles/puzzles1.html, puzzle nr. 8. 
  Description  : Knight domination puzzle - all squares threatened
  Source       : M Kraitchik - Mathematical Recreations (P256)
  """
  Place as few knights as possible on a chessboard in such a way that each square is controlled by at
  least one Knight, including the squares on which there is a Knight. How would the formulation differ if
  occupied squares were not to be under attack? 

  (Schuh)
  """
  This model was inspired by the XPress Mosel model created by Martin Chlond.
  http://www.chlond.demon.co.uk/puzzles/sol1s8.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.06s
% import sat. % 0.7s
% import cp. % much slower

main => go.


go =>

  Rows = 8,
  Cols = 8,
  
  % decision variables
  X = new_array(Rows+4,Cols+4),  
  X :: 0..1,

  MinNum #= sum([ X[I,J] : I in 3..Rows+2,J in 3..Cols+2]),


  % Every real square threatened 
  foreach(I in 3..Rows+2, J in 3..Cols+2)
    X[I-2,J-1]+X[I-1,J-2]+X[I+1,J-2]+X[I+2,J-1]+
    X[I+2,J+1]+X[I+1,J+2]+X[I-1,J+2]+X[I-2,J+1] #>= 1
  end,

  % Dummy squares not occupied 
  sum([X[I,J] : I in 1..2,J in 1..Cols+4]) +
  sum([X[I,J] : I in Rows+3..Rows+4,J in 1..Cols+4]) +
  sum([X[I,J] : J in 1..2,I in 3..Rows+2]) +
  sum([X[I,J] : J in Rows+3..Rows+4,I in 3..Rows+2]) #= 0,

  solve($[min,split, min(MinNum),report(printf("MinNum: %d\n",MinNum))], X),

  println(minNum=MinNum),
  foreach(I in 1..Rows) 
     foreach(J in 1..Cols)
        printf("%2d ", X[I,J])
     end,
     nl
  end,
  
  nl.