/**
 *
 * Coin Grid problem in choco v2.
 *
 * Problem from 

 * Tony Hürlimann: "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.
 * """
 *
 * Cf the LPL model:
 * http://diuflx71.unifr.ch/lpl/GetModel?name=/puzzles/coin
 * 
 *
 * Also, compare with my MiniZinc model:
 * http://www.hakank.org/minizinc/coins_grid.mzn
 * The constraint programming MiniZinc solvers (Gecode/fz, MiniZinc/flatzinc are all 
 * very slow. However the linear programming solver eplex for ECLiPSe is fast.
 *
 * and JaCoP model
 * http://www.hakank.org/JaCoP/CoinsGrid.java
 *
 *
 * choco model by Hakan Kjellerstrand (hakank@bonetmail.com)
 * Also see http://www.hakank.org/choco
 *
 */
import static choco.Choco.*;
import choco.cp.model.CPModel;
import choco.cp.model.CPModel.*;
import choco.cp.solver.CPSolver;
import choco.cp.solver.CPSolver.*;
import choco.cp.solver.constraints.*;
import choco.cp.solver.*;
import choco.kernel.model.variables.integer.*;
import choco.kernel.*;
import choco.kernel.solver.*;
import choco.kernel.model.*;
import choco.kernel.model.variables.*;
import choco.kernel.model.constraints.*;
import choco.kernel.model.variables.set.*;
import choco.cp.solver.search.integer.varselector.*;
import choco.cp.solver.search.integer.valiterator.*;
import choco.cp.solver.search.integer.valselector.*;
import choco.cp.solver.search.integer.branching.*;
import choco.cp.solver.search.*;

import java.io.*;
import java.util.*;
import java.text.*;

public class CoinsGrid {

    Model model;
    Solver s;

    IntegerVariable[][] x;

    int n;
    int c;

    public void model(int nn, int cc) {
        n = nn;
        c = cc;

        model = new CPModel();

        // original problem: n = 31, c = 14
        IntegerVariable v_c = makeIntVar("c", c, c);

        x = new IntegerVariable[n][n];
        for(int i = 0; i < n; i++) {
            x[i] = makeIntVarArray("x_" + i, n, 0, 1);
        }

        
        for(int i = 0; i < n; i++) {
            ArrayList<IntegerVariable> col = new ArrayList<IntegerVariable>();
            for(int j = 0; j < n; j++) {
                model.addConstraint(eq(sum(x[i]), v_c));
                col.add(x[j][i]);
            }
            model.addConstraint(eq(sum(col.toArray(new IntegerVariable[1])), v_c));
        }


        /* 
         * to minimize: quadratic horizonal distance, i.e.
         *    sum over x[i][j]*(abs(i-j))*(abs(i-j)) 
         *
         * z should be 13668 for n = 31 and c = 14
         *
         */
        IntegerVariable z = makeIntVar("z", 0, 10000);
        IntegerVariable[] z_array = new IntegerVariable[n*n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {

                int abs_i_j = Math.abs(i-j)*Math.abs(i-j);
                z_array[i*n + j] = makeIntVar("z_" + i +"_" + j, 0, 10000);
                model.addConstraint(eq(mult(x[i][j], abs_i_j), z_array[i*n + j]));
                
            }
        }
        model.addConstraint(eq(sum(z_array), z));


        s = new CPSolver();
        s.read(model);

        s.monitorTimeLimit(true);
        s.monitorBackTrackLimit(true);
        s.monitorNodeLimit(true);
        s.monitorFailLimit(true);

        // variable selector
        s.setVarIntSelector(new MinDomain(s)); // the best? 
        // s.setVarIntSelector(new DomOverDeg(s)); // not so bad
        // s.setVarIntSelector(new DomOverDynDeg(s)); // worse than DomOverDeg
        // s.setVarIntSelector(new MostConstrained(s)); // worse than DomOverDeg
        // s.setVarIntSelector(new RandomIntVarSelector(s)); // not good
        // s.setVarIntSelector(new MinDomain(s, s.getVar(x))); // strange results
        // s.setVarIntSelector(new LexIntVarSelector(
        //                                                new MinDomain(s),
        //                                                new DomOverDeg(s)));  // not good


        // value interator
        s.setValIntIterator(new DecreasingDomain()); // good
        // s.setValIntIterator(new IncreasingDomain()); // worse than DecreasingDomain

        // value selector
        // s.setValIntSelector(new MinVal());
        // s.setValIntSelector(new MaxVal());
        // s.setValIntSelector(new MidVal());
        // s.setValIntSelector(new RandomIntValSelector()); // not bad...


        s.solve();
        s.printRuntimeStatistics();

        if (s.isFeasible()) {
   
            System.out.println("z: " + s.getVar(z).getVal());
            
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    System.out.print(s.getVar(x[i][j]).getVal()+ " ");
                }
                System.out.println();
            }
            
            // printMatrix(x, n, n);

        } else {
            System.out.println("No solution.");
        }


    }

    //
    // prints a variable matrix
    //
    void printMatrix(IntegerVariable[][] y, int rows, int cols) {

        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                System.out.print(s.getVar(y[i][j]).getVal()+ " ");
            }
            System.out.println();
        }

    } // end printMatrix


    public static void main(String args[]) {

        // original problem: 
        // int tmp_n = 31
        // tmp_c = 14

        // defaults to a small problem
        int tmp_n = 8;
        int tmp_c = 3;
        if (args.length == 2) {
            tmp_n = Integer.parseInt(args[0]);
            tmp_c = Integer.parseInt(args[1]);
        }

        System.out.println("Using n = " + tmp_n + " c = " + tmp_c);
        CoinsGrid m = new CoinsGrid();
        m.model(tmp_n, tmp_c);

    }
}