% 
% Discrete tomography problem with n colors in Minizinc.
% Generalization of 2-colors problem.
% 
% This solutions just use one matrix and codes the different colors
% with different numbers 1..num_colors.
% 
% From
% http://www.lix.polytechnique.fr/~durr/Xray/Complexity/
% """
% Can you toggle the cell-colors by mouse-clicks such that all numbers are zero? 
% The computational complexity of this problem (is it possible to solve the 
% problem efficiently or is it NP-complete) is open since 1997.
% 
% In this problem there are two colors (not counting white indicating an empty 
% cell). However for a single color the problem is easy [5] and can be solved in 
% time O(n log n), where n is the side length of the grid. And for three or 
% more colors the problem is NP-complete [2] . (Previously it was known to be 
% hard for six colors or more [4] .) 
% """
% Note: The problems is changed each time the page is loaded

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

int: r; % number of rows
int: c; % number of columns
int: num_colors;
array[1..num_colors,1..r] of int: row_sums;
array[1..num_colors,1..c] of int: col_sums;

array[1..r, 1..c] of var 0..num_colors: x; % decision variable

% solve :: int_search([x[i,j] | i in 1..r, j in 1..c], "first_fail", "indomain_min", "complete") satisfy;
solve satisfy;

constraint
     % the rows
     forall(i in 1..r) (
       forall(k in 1..num_colors) ( 
          % count how many k's there are.
          % (Since it use bool2int it makes the problem 
          % unaccessable to explex: undef procedure int_eq_reif.)
          row_sums[k,i] = sum(j in 1..c) (bool2int(x[i,j] = k))
       )
     )
     /\ % the cols
     forall(j in 1..c) (
       forall(k in 1..num_colors) ( 
          col_sums[k,j] = sum(i in 1..r) (bool2int(x[i,j] = k))
       )
     )
;

output 
[
    if j = 1 then "\n" else " " endif ++
       show(x[i,j])
    | i in 1..r, j in 1..c
 ]
;


%
% data
% 


% The two atom problem
num_colors = 2; % row 1:blue, row 2:red
c = 10;
col_sums = [|3,3,5,4,2,4,4,2,3,4, 
            |3,4,2,3,3,3,3,6,2,4|]; 
r = 10;
row_sums = [|3,3,4,3,4,3,4,4,4,2, 
            |2,3,5,3,6,2,2,2,2,6|];


% three colors:
% This problem has 5 solutions.
% num_colors = 3;
% c = 5;
% col_sums = [|0,2,1,2,0,
%             |2,0,0,0,2,
%             |1,0,2,0,1|];
% r = 5;
% row_sums = [|0,2,1,2,0,
%             |2,0,0,0,2,
%             |1,0,2,0,1|];


% one dimensional problems (checking)
% the spiral:
% num_colors = 1;
% r = 11;
% c = 12;
% row_sums = [0,0,8,2,6,4,5,3,7,0,0];
% col_sums = [0,0,7,1,6,3,4,5,2,7,0,0];

% 
% the "h" (or chair)
% num_colors = 1;
% r = 14;
% c = 14;
% row_sums = [0,2,2, 2, 2,2,8,8,4,4,4,4,4,0];
% col_sums = [0,0,0,12,12,2,2,2,2,7,7,0,0,0];