/*

  Discrete tomography in Comet.

  Problem from http://eclipse.crosscoreop.com/examples/tomo.ecl.txt
  """
  This is a little "tomography" problem, taken from an old issue
  of Scientific American.
 
  A matrix which contains zeroes and ones gets "x-rayed" vertically and
  horizontally, giving the total number of ones in each row and column.
  The problem is to reconstruct the contents of the matrix from this
  information. Sample run:
 
 ?- go.
     0 0 7 1 6 3 4 5 2 7 0 0
  0                         
  0                         
  8      * * * * * * * *    
  2      *             *    
  6      *   * * * *   *    
  4      *   *     *   *    
  5      *   *   * *   *    
  3      *   *         *    
  7      *   * * * * * *    
  0                         
  0                         
 
 
  Eclipse solution by Joachim Schimpf, IC-Parc
  """


  This Comet model was created by Hakan Kjellerstrand (hakank@bonetmail.com)
  Also, see my Comet page: http://www.hakank.org/comet 

 */

import cotfd;
int t0 = System.getCPUTime();


/*
 These following three examples are from the ECLiPSe program cited above.
*/

// The above stated problem
int r = 11; // number of rows
int c = 12; // number of columns
int row_sums[1..r] = [0,0,8,2,6,4,5,3,7,0,0];
int col_sums[1..c] = [0,0,7,1,6,3,4,5,2,7,0,0];


/*
int r = 5;
int c = 13;
int row_sums[1..r] = [10,4,8,5,6];
int col_sums[1..c] = [5,3,4,0,5,0,5,2,2,0,1,5,1];
*/

/*
// This give three slightly different solutions.
int r = 3;
int c = 11;
int row_sums[1..r] = [11,5,4];
int col_sums[1..c] = [3,2,3,1,1,1,1,2,3,2,1];
*/


Solver<CP> m(); 
var<CP>{int} x[1..r, 1..c](m, 0..1);


Integer num_solutions(0);
exploreall<m> {

  // the rows
  forall(i in 1..r)
    m.post(row_sums[i] == sum(j in 1..c) x[i,j]);

  // the columns
  forall(j in 1..c)
    m.post(col_sums[j] == sum(i in 1..r) x[i,j]);


} using {
      
  label(m);

  num_solutions := num_solutions + 1;
      
  forall(i in 1..r) {
    forall(j in 1..c) {
      cout << x[i,j] == 1 ? "*" : " ";
    }
    cout << endl;
  }

  cout << endl;
    

}

cout << "\nnum_solutions: " << num_solutions << endl;
    
int t1 = System.getCPUTime();
cout << "time:      " << (t1-t0) << endl;
cout << "#choices = " << m.getNChoice() << endl;
cout << "#fail    = " << m.getNFail() << endl;
cout << "#propag  = " << m.getNPropag() << endl;