/**
 *
 * Young tableaux in JaCoP.
 *
 * 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
 * """  
 * 
 *
 *
 *
 * 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 YoungTableuax {

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

    public void increasing(IntVar[] v) {
        for(int j = 1; j < n; j++) {
            store.impose(new XgteqY(v[j], v[j-1]));
        }
    }

    public void model(int n_tmp) {

        store = new Store();

        n = n_tmp;

        x = new IntVar[n][n];
        x_a = new IntVar[n*n];
        p = new IntVar[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] = new IntVar(store, "p_" + i, 0, n+1);
            for(int j = 0; j < n; j++) {
                x[i][j]= new IntVar(store, "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.
        for(int i = 1; i <= n; i++) {
            store.impose(new Count(x_a, new IntVar(store, 1, 1), i));
        }

        // x[0][0] = 1
        store.impose(new XeqY(x[0][0], new IntVar(store, 1, 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++) {
                store.impose(new XgteqY(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++) {
            IntVar[] p_bin = new IntVar[n];
            for(int j = 0; j < n; j++) {
                p_bin[j] = new IntVar(store, 0, 1);
            }
            // sum all entries where x[i][j] <= n
            for(int j = 0; j < n; j++) {
                store.impose(new IfThenElse(
                                            new XlteqC(x[i][j], n), 
                                            new XeqC(p_bin[j],1),
                                            new XeqC(p_bin[j],0)
                                            )
                             );
            }
            store.impose(new Sum(p_bin, p[i]));
        }

        store.impose(new Sum(p, new IntVar(store, n, n)));
        // increasing(p);


        //
        // prepare for search and output
        //
        ArrayList<IntVar> allVars = new ArrayList<IntVar>();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                allVars.add(x[i][j]);
            }
        }
        
        // put p last
        for(int i = 0; i < n; i++) {
            allVars.add(p[i]);
        }

        //
        // The search
        //
        SelectChoicePoint select = new SimpleSelect (allVars.toArray(new IntVar[1]),
                                                           null, // new MostConstrainedStatic (), 
                                                           new IndomainMin ());
        
        Search label = new DepthFirstSearch ();

        label.getSolutionListener().searchAll(true);
        label.getSolutionListener().recordSolutions(true);

        boolean result = label.labeling(store, select);
    
        System.out.println("store: " + store);

        String n_plus_1 = (n+1)+"";
        if(result) {
            int numSolutions = label.getSolutionListener().solutionsNo();
            System.out.println("Number of Solutions: " + numSolutions);
            System.out.println("\nAll solutions: \n");
            for(int s = 1; s <= numSolutions; s++) {                
                Domain [] res = label.getSolutionListener().getSolution(s);

                // Print the tableaux
                System.out.println("\nTableaux:");
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < n; j++) {
                        String r = res[n*i+j].toString();
                        if (n_plus_1.equals(r)) {
                            System.out.print("_" + " ");                        
                        } else {
                            System.out.print(r + " ");
                        }
                    }
                    System.out.println();
                }
                // print the partition
                System.out.println("Partition: ");
                for(int j = n*n; j < n*n+n; j++) {
                    System.out.print(res[j] + " ");
                }
                System.out.println("\n");
                
            }
            

            /*
            System.out.println("\nPartition for last solution:");
            for(int i = 0; i < n; i++) {
                System.out.print(p[i].value() + " ");
            }
            System.out.println();
            */

            System.out.println("Number of Solutions: " + numSolutions);

        }


    }


    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);

    }
}