/* 

  Discrete tomography problem with n colors in Picat.

  Generalization of 2-colors problem (discrete_tomography.pi).
  
  This model 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 are changed each time the page is loaded



  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.

main => go.

go =>
  problem(1,NumColors,C,ColSums,R,RowSums),
  tomography(NumColors,C,ColSums,R,RowSums, X),

  foreach(Row in X)
    println(Row.to_list)
  end,
  nl,
  fail,
  
  nl.


go2 =>
  problem(2,NumColors,C,ColSums,R,RowSums),
  tomography(NumColors,C,ColSums,R,RowSums, X),

  foreach(Row in X)
    println(Row.to_list)
  end,
  nl,
  fail,
  
  nl.

tomography(NumColors,C,ColSums,R,RowSums, X) =>
  X = new_array(R,C),
  X :: 0..NumColors,

  % Rows
  foreach(I in 1..R) 
     foreach(K in 1..NumColors) 
       RowSums[K,I] #= sum([X[I,J] #= K : J in 1..C])
     end
  end,
  % Cols
  foreach(J in 1..C)
    foreach(K in 1..NumColors) 
      ColSums[K,J] #= sum([ X[I,J] #= K : I in 1..R])
    end
  end,

  solve(X).


% Three colors
% This problem has 5 solutions.
problem(1,NumColors,C,ColSums,R,RowSums) => 
  NumColors = 3,
  C = 5,
  ColSums = [[0,2,1,2,0],
             [2,0,0,0,2],
             [1,0,2,0,1]],
  R = 5,
  RowSums = [[0,2,1,2,0],
             [2,0,0,0,2],
             [1,0,2,0,1]].

% The two atom problem
% A lot of solutions.
problem(2,NumColors,C,ColSums,R,RowSums) => 
  NumColors = 2, % row 1: blue, row 2:red
  C = 10,
  ColSums = [[3,3,5,4,2,4,4,2,3,4], 
             [3,4,2,3,3,3,3,6,2,4]],
  R = 10,
  RowSums = [[3,3,4,3,4,3,4,4,4,2], 
             [2,3,5,3,6,2,2,2,2,6]].