/**
 *
 * Coin Grid problem in JaCoP.
 *
 * 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.
 *
 *
 *
 * JaCoP model by Hakan Kjellerstrand (hakank@bonetmail.com)
 * http://www.hakank.org/JaCoP
 *
 */
import JaCoP.constraints.*;
import JaCoP.core.*;
import JaCoP.search.*;

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

public class CoinsGrid {

    Store store;
    IntVar[][] x;

    int n;
    int c;

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

        store = new Store();

        // original problem: n = 31, c = 14
        IntVar v_c = new IntVar(store, "c", c, c);

        x = new IntVar[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                x[i][j] = new IntVar(store, "x" + i + "_" + j, 0, 1);
            }
        }

        
        // sum rows = c
        // sum cols = c
        for(int i = 0; i < n; i++) {
            ArrayList<IntVar> col = new ArrayList<IntVar>();
            for(int j = 0; j < n; j++) {
                store.impose( new Sum(x[i], v_c)); // rows
                col.add(x[j][i]);
            }
            store.impose( new Sum(col, v_c)); // columns
        }


        /* 
         * 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
         *
         */
        IntVar z = new IntVar(store, "z", 0, 10000);
        IntVar[] z_array = new IntVar[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] = new IntVar(store, "z_" + i +"_" + j, 0, 10000);
                store.impose(new XmulCeqZ(x[i][j], abs_i_j, z_array[i*n + j]));
            }
        }
        store.impose(new Sum(z_array, z));


        //
        // The search
        //
        // SimpleSelect(variables, ComparatorVariable varSelect Indomain indomain)
        SelectChoicePoint select = new SimpleSelect (z_array,
                                                     new MostConstrainedStatic(), 
                                                     // new MaxRegret()
                                                     new IndomainMiddle() // better than IndomainMin
                                                     // new IndomainMin ()
                                                     );

        Search label = new DepthFirstSearch ();
        boolean result = label.labeling(store, select, z); // minimize z
    
        System.out.println("store: " + store);
        if(result) {
            System.out.println("z: " + z);
            printMatrix(x, n, n);
        }


    }

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

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

    } // end printMatrix


    public static void main(String args[]) {

        // default to a small problem
        int tmp_n = 8; // 31 ;
        int tmp_c = 3; // 14;
        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);

    }
}