/**
 *
 * Young tableaux in choco v2.
 *
 * See 
 * http://mathworld.wolfram.com/YoungTableau.html
 * and
 * http://en.wikipedia.org/wiki/Young_tableau
 * """
 * The partitions of 4 are
 *  {4}, {3,1}, {2,2}, {2,1,1}, {1,1,1,1}
 *
 * And the corresponding standard Young tableaux are:
 *
 * 1.   1 2 3 4
 *
 * 2.   1 2 3         1 2 4    1 3 4
 *      4             3        2
 *
 * 3.   1 2           1 3
 *      3 4           2 4
 *
 * 4    1 2           1 3      1 4 
 *      3             2        2 
 *      4             4        3
 *
 * 5.   1
 *      2
 *      3
 *      4
 * """  
 * 
 *
 * Compare with other models:
 *   Minizinc: http://www.hakank.org/minizinc/young_tableaux.mzn
 *   JaCoP: http://www.hakank.org/JaCoP/YoungTableaux.java
 *
 * choco model by Hakan Kjellerstrand (hakank@bonetmail.com)
 * 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.constraints.global.matching.*;
import choco.cp.solver.constraints.global.matching.GlobalCardinality.*;
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.kernel.model.variables.integer.*;


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

public class YoungTableuax {

    Model m;
    CPSolver s;

    int n;
    IntegerVariable[][] x; // matrix
    IntegerVariable[] x_a; // x as an array, for Count
    IntegerVariable[] p; // partition structure.

    IntegerVariable[] gcc_count; // Instead of global constraint count

    public void increasing(IntegerVariable[] v) {
        for(int j = 1; j < n; j++) {
            m.addConstraint(geq(v[j], v[j-1]));
        }
    }

    public void model(int n_tmp) {

        m = new CPModel();

        n = n_tmp;

        x = new IntegerVariable[n][n];
        x_a = new IntegerVariable[n*n];
        p = new IntegerVariable[n];   // the partition structure.

        // Initialize the variables.
        //
        // Value n+1 in x will be replaced with "_" in the output.
        // This representation simplifies the "increasing" constraints below.
        for(int i = 0; i < n; i++) {
            p[i] = makeIntVar("p_" + i, 0, n+1);
            for(int j = 0; j < n; j++) {
                x[i][j]= makeIntVar("x_" + i + "_" + j, 1, n+1);
                x_a[n*i + j]= x[i][j];
            }
        }
        
        // 1..n is used exactly once in the whole matrix. 
        // n+1, however will be used n^2 - n times.
        // Note: choco don't have the global constraint count, so we use
        // globalCardinality.
        /*
        IntegerVariable one = makeConstantVar("one", 1);
        for(int i = 0; i < n; i++) {
            //m.addConstraint(count(i, x_a, 1)); // we want something like this ...
            m.addConstraint(occurrence(1, one, x_a[i])); 
        } 
        */

        int[] gcc_low = new int[n+1];
        int[] gcc_up = new int[n+1];
        for(int i = 0; i <= n; i++) {
            gcc_low[i] = 1;
            gcc_up[i] = 1;
        }
        gcc_low[n] = n*n-n;
        gcc_up[n] = n*n-n;
        m.addConstraint(globalCardinality(x_a, gcc_low, gcc_up, 1));


        // x[0][0] = 1
        m.addConstraint(eq(x[0][0], 1));

        //
        // increasing row wise
        //
        for(int i = 0; i < n; i++) {
            increasing(x[i]);
        }

        //
        // increasing column wise
        //
        for(int j = 0; j < n; j++) {
            for(int i = 1; i < n; i++) {
                m.addConstraint(geq(x[i][j], x[i-1][j]));
            }
        }

        // calculate the partition structure:
        // for each row: sum number of entries where x[i][j] between 1.. n
        // i.e. ignore those that is n+1
        for(int i = 0; i < n; i++) {
            IntegerVariable[] p_bin = new IntegerVariable[n];
            for(int j = 0; j < n; j++) {
                p_bin[j] = makeIntVar("p_bin" + j, 0, 1);
            }
            // sum all entries where x[i][j] <= n
            for(int j = 0; j < n; j++) {
                m.addConstraint(ifThenElse(
                                            leq(x[i][j], n), 
                                            eq(p_bin[j],1),
                                            eq(p_bin[j],0)
                                            )
                             );

            }
            m.addConstraint(eq(sum(p_bin), p[i]));
        }

        m.addConstraint(eq(sum(p), n));


        //
        // The search
        //
        s = new CPSolver();
        s.read(m);

        /*
        s.setVarIntSelector(new MinDomain(s));
        s.setValIntIterator(new IncreasingDomain());
        s.setValIntSelector(new RandomIntValSelector());
        */

        s.monitorTimeLimit(true);
        s.monitorBackTrackLimit(true);
        s.monitorNodeLimit(true);
        s.monitorFailLimit(true);
       
        s.solve();
        s.printRuntimeStatistics(); 
    
        if(s.isFeasible()) {
            do {
                
                // Tableaux
                System.out.println("\nTableaux:");
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < n; j++) {
                        int r = s.getVar(x[i][j]).getVal();
                        if (r == n+1) {
                            System.out.print("_" + " ");                        
                        } else {
                            System.out.print(r + " ");
                        }
                    }
                    System.out.println();
                }
                
                // Partition
                System.out.println("Partition: ");
                for(int i = 0; i < n; i++) {
                    System.out.print(s.getVar(p[i]).getVal() + " ");
                }
                System.out.println("\n");

            } while (s.nextSolution() == Boolean.TRUE);

            
            System.out.println("nbSol: " + s.getNbSolutions());            

        } else {
            System.out.println("Problem is not feasible.");
        }


    } // end model


    public static void main(String args[]) {

        int n_tmp = 4;
        if (args.length == 1) {
            n_tmp = Integer.parseInt(args[0]);
        }

        YoungTableuax m = new YoungTableuax();
        m.model(n_tmp);

    }
}

