% 
% Cihan Altay's Touching Numbers puzzle in MiniZinc.
%
% Problem and XPress Mosel model from 
% Martin J.Chlond "The Traveling Space Telescope Problem"
% http://archive.ite.journal.informs.org/Vol3No1/Chlond/index.php
% 
% XPress Mosel model:
% http://archive.ite.journal.informs.org/Vol3No1/Chlond/altayxp.html
% 
% More info about the puzzle:
% http://www.mathpuzzle.com/0123456789.htm


% Note: This model implements the formulation which are in the paper,
%       i.e. where the arrays is from 0..9 instead of 1..100
%
% This MiniZinc model created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

% mip:
% 320
% [0, 9, 8, 3, 4, 2, 7, 1, 6, 5]
%
% 0 0 0 0 0 0 0 1 0 0
% 0 0 0 0 0 0 0 0 0 0
% 0 1 0 0 0 0 0 0 0 0
% 0 0 0 0 1 0 0 0 0 0
% 0 0 0 0 0 0 0 0 0 1
% 0 0 0 1 0 0 0 0 0 0
% 0 0 1 0 0 0 0 0 0 0
% 0 0 0 0 0 1 0 0 0 0
% 0 0 0 0 0 0 1 0 0 0
% 0 0 0 0 0 0 0 0 1 0



int: Size = 9;

% N(i,j) = number of squares touching if digit (i-1) is to
%          the immediate left of digit (j-1)
array[0..Size, 0..Size] of int: N = array2d(0..Size, 0..Size, 
[0,2,4,3,3,4,5,2,5,4,
 1,0,1,1,0,1,1,0,1,1,
 4,2,0,3,3,4,4,2,4,4,
 5,2,4,0,3,4,5,2,5,4,
 5,2,4,3,0,4,5,2,5,4,
 4,1,4,3,2,0,4,1,4,3,
 4,1,4,3,2,3,0,1,4,3,
 5,2,4,3,3,4,5,0,5,4,
 5,2,4,3,3,4,5,2,0,4,
 5,2,4,3,3,4,5,2,5,0]);
            

% X(i,j) = 1 if digit (i-1) is to the immediate left of digit (j-1)
%          0 otherwise
array[0..Size, 0..Size] of var 0..1: X;
array[0..Size] of var 0..Size: Z; % variables to avoid circular sets 

% Maximize score
var int: Maxscore = sum(i, j in 0..Size) ((i+j-1)*N[i,j]*X[i,j]);

solve :: int_search([X[i,j] | i,j in 0..Size], "first_fail", "indomain_max", "complete") maximize Maxscore;
% solve maximize Maxscore;


constraint
  sum(Z) >= 1
  /\

  % Each digit to the immediate left of no more than one other
  forall(i in 0..Size) (
    sum(j in 0..Size) (X[i,j]) <= 1 
  )

  /\  % Each digit to the immediate right of no more than one other
  forall(j in 0..Size) ( 
     sum(i in 0..Size) (X[i,j]) <= 1
  )
  
  /\                                                             
  % No circular sets
  forall(i in 0..Size, j in 0..Size) (
      Z[i] - Z[j] + (Size+1)*X[i,j] <= Size
  )
  
  /\ % Exactly nine adjacencies required
  sum(i, j in 0..Size) (X[i,j]) = 9

;

output [
  show(Maxscore), "\n",
  show(Z), "\n",
] ++ [
  if j = 0 then "\n" else " " endif ++
    show(X[i,j])
  | i, j in 0..Size
];