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