/*
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.