/* 

  Equal Vision puzzle in Picat.

  From Martin Chlond Integer Programming Puzzles:
  http://www.chlond.demon.co.uk/puzzles/puzzles3.html, puzzle nr. 12.  
  Description  : Equal Vision
  Source       : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling
  """
  12. Equal Vision
  Each watchman looks in all directions (horizontal, vertical and diagonal). On the board below, each
  watchman has five vacant cells under his gaze. A watchman can see beyond another watchman.
  What is the maximum number of watchmen that can be placed so that each sees six empty cells?
  What if each watchman must see seven empty cells? 

  (Poniachek)
  """

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


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

*/


import cp.


main => go.


go =>
  Size = 4,
  Cvis = 6,

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

  % n(i,j) = number of vacant cells visible to watchman on cell {i,j}
  N = new_array(Size,Size),
  N :: 0..20,

  SumX #= sum(X.vars()),

  % minimise vacant cells
  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,M] : M in 1..Size, M != J]) #= N[I,J]
  end,

  foreach(I in 1..Size, J in 1..Size)
     N[I,J] #>= Cvis-99*X[I,J]
  end,

  foreach(I in 1..Size, J in 1..Size)
      N[I,J] #<= Cvis+99*X[I,J]
  end,

  solve($[min(SumX)], X ++ N),

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