/*
  Coins grid in Comet
  
  
  Problem from 
  Tony Hurlimann: "A coin puzzle - SVOR-contest 2007"
  http://www.svor.ch/competitions/competition2007/AsroContestSolution.pdf
 
  """
  In a quadratic grid (or a larger chessboard) with 31x31 cells, one should
   place coins in such a way that the following conditions are fulfilled:
     1. In each row exactly 14 coins must be placed.
     2. In each column exactly 14 coins must be placed.
     3. The sum of the quadratic horizontal distance from the main 
        diagonal of all cells containing a coin must be as 
        small as possible.
     4. In each cell at most one coin can be placed.

  The description says to place 14x31 = 434 coins on the chessboard 
  each row containing 14
  coins and each column also containing 14 coins.
  """
 
  Compare with the following models:
  * LPL:
    http://diuflx71.unifr.ch/lpl/GetModel?name=/puzzles/coin
  
  * MiniZinc: http://www.hakank.org/minizinc/coins_grid.mzn

  * Gecode/R: http://www.hakank.org/gecode_r/coins_grid.rb

  * JaCoP: http://www.hakank.org/JaCoP/CoinsGrid.java
 
  * Choco: http:// www.hakank.org/choco/CoinsGrid.java 



  This model use the linear programming MIP solver, it is much faster than 
  the Comet FD (finite domain constraint programming) solver (and other 
  finite domain solvers I've tested) 
  for this problem.

  Running all problems for n = 31 and c in 1..n takes about 3 seconds.
 

  Comet model created by Hakan Kjellerstrand, hakank@bonetmail.com
  See also my Comet page: http://www.hakank.org/comet/

 */

import cotln;
int n = 31; // the grid size
int c = 24; // number of coins per row and column.

forall(c in 1..n) {

  cout << "c: " << c << endl;
  // int t0 = System.getCPUTime();

  Solver<MIP> m("lp_solve");

  var<MIP>{int} x[i in 1..n, j in 1..n](m, 0..1); // the coin grid
  var<MIP>{int} z(m,0..10000000);

  minimize<m> z subject to {
    // rows
    forall(i in 1..n) 
      m.post(sum(j in 1..n) (x[i,j]) == c);

    // columns
    forall(j in 1..n) 
      m.post(sum(i in 1..n) (x[i,j]) == c);
    
    // quadratic horizonal distance
    m.post(z == sum(i in 1..n, j in 1..n) x[i,j]*(abs(i-j))*(abs(i-j)));
    
  }


  if (m.isFeasible()) {
    cout << "z: " << z.getValue() << endl;
    forall(i in 1..n) {
      forall(j in 1..n) {
        cout << x[i,j].getValue() << " ";
      }
      cout << endl;
    }
  } else {
    cout << "Not feasible!" << endl;
  }
  
  // int t1 = System.getCPUTime();
  // cout << "time:      " << (t1-t0) / 1000.0 << endl;
  // cout << "#choices = " << m.getNChoice() << endl;
  // cout << "#fail    = " << m.getNFail() << endl;
  

} // end forall c