/**
 *
 * Quasigroup Completion problem in JaCoP.
 *
 * See 
 * Carla P. Gomes and David Shmoys:
 * "Completing Quasigroups or Latin Squares: Structured Graph Coloring Problem"
 *
 *
 * See also
 * Ivars Peterson "Completing Latin Squares"
 * http://www.maa.org/mathland/mathtrek_5_8_00.html
 * """
 * Using only the numbers 1, 2, 3, and 4, arrange four sets of these numbers into 
 * a four-by-four array so that no column or row contains the same two numbers. 
 * The result is known as a Latin square.
 * ...
 * The so-called quasigroup completion problem concerns a table that is correctly 
 * but only partially filled in. The question is whether the remaining blanks in 
 * the table can be filled in to obtain a complete Latin square (or a proper 
 * quasigroup multiplication table).
 * """
 * 
 * Also compare with the MiniZinc model
 *   http://www.hakank.org/minizinc/quasigroup_completion.mzn
 * (more problems at http://www.hakank.org/minizinc/ )
 * 
 *
 * 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 QuasigroupCompletion {

    Store store;
    int n;
    IntVar[][] x;
    
    int[][] matrix;

    //
    // k_all_different (make x a latin square)
    //
    public void k_all_different(Store store, IntVar[][] y, int n) {

        for(int i = 0; i < n; i++) {
            ArrayList<IntVar> col = new ArrayList<IntVar>();
            for(int j = 0; j < n; j++) {
                store.impose( new Alldifferent(y[i])); // rows
                col.add(y[j][i]);
            }
            store.impose( new Alldifferent(col)); // columns
        }

    } // end k_all_different


    public void model() {

        store = new Store();
        
        /* // _many_ solution!
        int[][] matrix = {{0,0,0,1,0,0,0,0,0,0},
                          {0,0,1,0,0,0,0,0,0,0},
                          {0,1,0,0,0,2,0,0,0,0},
                          {1,0,0,0,2,0,0,0,0,0},
                          {0,0,0,2,1,0,0,0,0,0},
                          {0,0,2,0,0,1,0,0,0,0},
                          {0,0,0,0,0,0,1,0,0,0},
                          {0,0,0,0,0,0,0,1,0,2},
                          {0,0,0,0,0,0,0,0,2,0},
                          {0,0,0,0,0,0,0,2,0,0}};
        */

        
        if (matrix == null) {
            /* Example from Ruben Martins and Inès Lynce
               Breaking Local Symmetries in Quasigroup Completion Problems, page 3
               The solution is unique:
               1 3 2 5 4
               2 5 4 1 3
               4 1 3 2 5
               5 4 1 3 2
               3 2 5 4 1
            */
            n = 5;
            int[][] matrixX = {{1, 0, 0, 0, 4},
                              {0, 5, 0, 0, 0},
                              {4, 0, 0, 2, 0},
                              {0, 4, 0, 0, 0},
                              {0, 0, 5, 0, 1}};

            matrix = matrixX;
        }
 

        //
        // create variable matrix
        //
        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, 1, n);
                if (matrix[i][j] > 0) {
                    store.impose(new XeqC(x[i][j], matrix[i][j]));
                }
            }
        }

        //
        // and do a quasigroup completion
        //
        k_all_different(store, x, n);


    } // end model


    public void search() {

        SelectChoicePoint select = 
            new SimpleMatrixSelect (x,
                              new SmallestDomain(),
                              new IndomainMin ()
                              );

        Search label = new DepthFirstSearch ();
        // if (n <= 5) {
            label.getSolutionListener().searchAll(true);
        //} else {
            // System.out.println("n > 5. Does not search for all solutions.");
            // label.getSolutionListener().searchAll(false);
        // }
        label.getSolutionListener().recordSolutions(true);

        boolean result = label.labeling(store, select); 

        //
        // output
        //
        if (result) {
            int numSolutions = label.getSolutionListener().solutionsNo();
            System.out.println("Number of solutions: " + numSolutions);
            // if (numSolutions <= 100) {
                HakankUtil.printAllSolutions(label);
            // } else {
            //    System.out.println("Too many solutions to print...");
            // }
            
            System.out.println("\nLast solution\n");
            printMatrix(x, n, n);
            System.out.println("\nNumber of solutions: " + numSolutions);
        }  else {
            System.out.println("No solution.");
        }



    } // end search

    /**
     *
     * Reads a Quasigroup completion file.
     * File format:
     *  # a comment which is ignored
     *  % a comment which also is ignored
     *  number of rows (n)
     *  <
     *    row number of space separated entries
     *  >
     * 
     * "." or "0" means unknown, integer 1..n means known value
     * 
     * Example
     *   5
     *    1 . . . 4
     *   . 5 . . .
     *   4 . . 2 .
     *   . 4 . . .
     *   . . 5 . 1
     *
     */
    public void readFile(String file) {

        System.out.println("readFile(" + file + ")");
        int lineCount = 0;
        
        try {

            BufferedReader inr = new BufferedReader(new FileReader(file));
            String str;
            while ((str = inr.readLine()) != null && str.length() > 0) {

                str = str.trim();

                // ignore comments
                if(str.startsWith("#") || str.startsWith("%")) {
                    continue;
                }

                System.out.println(str);
                if (lineCount == 0) {
                    n = Integer.parseInt(str); // number of rows
                    matrix = new int[n][n];
                } else {
                    // the problem matrix
                    String row[] = str.split(" ");
                    for(int i = 0; i < n; i++) {
                        String s = row[i];
                        if (s.equals(".")) {
                            matrix[lineCount-1][i] = 0;
                        } else {
                            matrix[lineCount-1][i] = Integer.parseInt(s);
                        }
                    }
                }

                lineCount++;

            } // end while

            inr.close();

        } catch (IOException e) {
            System.out.println(e);
        }

    } // end readFile
    

    //
    // 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


    //
    // main
    //
    public static void main(String args[]) {

        String file = "";
        QuasigroupCompletion m = new QuasigroupCompletion();
        if (args.length > 0) {
            file = args[0];
            m.readFile(file);
        }

        m.model();
        m.search();

    } // end main

} // end class