% 
% Knight domination puzzle in MiniZinc.
% 
% 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)

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

%
% Model created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

int: rows = 8;
int: cols = 8;
  
array[1..rows+4,1..cols+4] of var 0..1: x;
var int: minnum = sum(i in 3..rows+2,j in 3..cols+2) (x[i,j]);

solve :: int_search([x[i,j] | i in 1..rows+4,j in 1..cols+4], "first_fail", "indomain", "complete") minimize minnum;

constraint 
 % Every real square threatened 
 forall(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
  )
  /\ % Dummy squares not occupied 
  sum(i in 1..2,j in 1..cols+4) (x[i,j])+
  sum(i in rows+3..rows+4,j in 1..cols+4) (x[i,j]) +
  sum(j in 1..2,i in 3..rows+2) (x[i,j]) +
  sum(j in rows+3..rows+4,i in 3..rows+2) (x[i,j]) = 0

;

output [
  if i = 3 /\ j = 3 then 
   "\nminnum: " ++ show(minnum)
  else "" endif ++
  if j = 3 then "\n" else " " endif ++
  show(x[i, j])  
  | i in 3..rows+2, j in 3..cols+2
];