/**
 *
 * Survo puzzle in JaCoP.
 *
 * http://en.wikipedia.org/wiki/Survo_Puzzle
 * """
 * Survo puzzle is a kind of logic puzzle presented (in April 2006) and studied 
 * by Seppo Mustonen. The name of the puzzle is associated to Mustonen's 
 * Survo system which is a general environment for statistical computing and 
 * related areas.
 * 
 * In a Survo puzzle the task is to fill an m * n table by integers 1,2,...,m*n so 
 * that each of these numbers appears only once and their row and column sums are 
 * equal to integers given on the bottom and the right side of the table. 
 * Often some of the integers are given readily in the table in order to 
 * guarantee uniqueness of the solution and/or for making the task easier.
 * """
 * 
 * See also
 * http://www.survo.fi/english/index.html
 * http://www.survo.fi/puzzles/index.html
 *
 * References:
 * - Mustonen, S. (2006b). "On certain cross sum puzzles"
 *   http://www.survo.fi/papers/puzzles.pdf 
 * - Mustonen, S. (2007b). "Enumeration of uniquely solvable open Survo puzzles." 
 *   http://www.survo.fi/papers/enum_survo_puzzles.pdf 
 * - Kimmo Vehkalahti: "Some comments on magic squares and Survo puzzles" 
 *   http://www.helsinki.fi/~kvehkala/Kimmo_Vehkalahti_Windsor.pdf
 *
 *
 * Compare with the MiniZinc model:
 * http://www.hakank.org/minizinc/survo_puzzle.mzn
 *
 * 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 SurvoPuzzle {


    Store store;
    int r;          // number of rows
    int c;          // number of column
    int[] rowsums;  // row sums
    int[] colsums;  // col sums
    int[][] matrix; // the clues matrix

    IntVar[][] x;      // the solution
    IntVar[] x_arr;    // x as an array, for alldifferent


    /**
     *
     *  model()
     *
     */
    public void model() {

        store = new Store();

        if (matrix == null) {

            System.out.println("Using the default problem.");

            /* Default problem:
             *
             * http://www.survo.fi/puzzles/280708.txt, the third puzzle
             * Survo puzzle 128/2008 (1700) #364-35846
             */
            int r_tmp = 3;
            int c_tmp = 6;
            int[] rowsums_tmp = {30, 86, 55};
            int[] colsums_tmp = {22, 11, 42, 32, 27, 37};
            int[][] matrix_tmp = {{0, 0,  0, 0, 0, 0},
                                  {0, 0, 18, 0, 0, 0},
                                  {0, 0,   0, 0, 0, 0}};

            r = r_tmp;
            c = c_tmp;
            rowsums = rowsums_tmp;
            colsums = colsums_tmp;
            matrix = matrix_tmp;

        }

        //
        // initiate structures and variables
        //
        x = new IntVar[r][c];
        x_arr = new IntVar[r*c];
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                x[i][j] = new IntVar(store, "x_" + i + "_" + j, 1, r*c);
                if (matrix[i][j] > 0) {
                    store.impose(new XeqC(x[i][j], matrix[i][j]));
                }
                x_arr[c*i+j] = new IntVar(store, "xa_" + i + "_" + j, 1, r*c);
                store.impose(new XeqY(x_arr[c*i+j],x[i][j])); 
            }
        }

        //
        // row sums
        //
        for(int i = 0; i < r; i++) {
            IntVar r_sum = new IntVar(store, "r_" + i, 1, r*c*r*c);
            store.impose(new Sum(x[i], r_sum));
            store.impose(new XeqC(r_sum, rowsums[i]));
        }


        //
        // column sums
        //
        for(int j = 0; j < c; j++) { 
            ArrayList<IntVar> cols = new ArrayList<IntVar>();
            for(int i = 0; i < r; i++) {
                cols.add(x[i][j]);
            }
            IntVar c_sum = new IntVar(store, "c_" + j, 1, r*c*r*c);
            store.impose(new Sum(cols, c_sum));
            store.impose(new XeqC(c_sum, colsums[j]));
        }

        // Alldifferent on the array version.
        store.impose(new Alldifferent(x_arr));

    }


    /**
     *
     * search()
     *
     */
    public void search() {

        SelectChoicePoint select = new SimpleMatrixSelect (x,
                                                     new MaxRegret(), 
                                                     new IndomainMiddle ()
                                                     );
        
        Search label = new DepthFirstSearch ();
        label.getSolutionListener().searchAll(true);
        label.getSolutionListener().recordSolutions(true);
        boolean result = label.labeling(store, select);
        
        // System.out.println("store: " + store);
        if(result) {
            int numSolutions = label.getSolutionListener().solutionsNo();
            System.out.println("Number of solutions: " + numSolutions);
            printMatrix(x, r, c);
        }

    }

    //
    // prints a variable matrix
    //
    public static 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

    
    /**
     *
     * readFile()
     *
     * Reads a Survo puzzle in the following format
     * 
     * % From http://www.survo.fi/puzzles/280708.txt
     * % Survo puzzle 128/2008 (1700) #364-35846
     * A  B  C  D  E  F
     * 1  *  *  *  *  *  * 30
     * 2  *  * 18  *  *  * 86
     * 3  *  *  *  *  *  * 55
     * 22 11 42 32 27 37
     *
     */
    public void readFile(String file) {

        System.out.println("readFile(" + file + ")");

        try {

            BufferedReader inr = new BufferedReader(new FileReader(file));
            String str;
            int lineCount = 0;
            ArrayList<ArrayList<Integer>> MatrixI = new ArrayList<ArrayList<Integer>>();
            while ((str = inr.readLine()) != null && str.length() > 0) {
                
                str = str.trim();
                
                // ignore comments
                // starting with either # or %
                if(str.startsWith("#") || str.startsWith("%")) {
                    continue;
                }

                str = str.replace("_", "");                                
                String row[] = str.split("\\s+");
                System.out.println(str);

                // first line: column names: Ignore but count them
                if (lineCount == 0) {
                    c = row.length;
                    colsums = new int[c];
                } else  {

                    // This is the last line: the column sums
                    if (row.length == c) {
                        colsums = new int[row.length];
                        for(int j = 0; j < row.length; j++) {
                            colsums[j] = Integer.parseInt(row[j]);
                        }
                        System.out.println();
                    } else {
                        // Otherwise:
                        // The problem matrix: index 1 .. row.length-1
                        // The row sums: index row.length
                        ArrayList<Integer> this_row = new ArrayList<Integer>();
                        for(int j = 0; j < row.length; j++) {
                            String s = row[j];
                            if (s.equals("*")) {
                                this_row.add(0);
                            } else {
                                this_row.add(Integer.parseInt(s));
                            }
                        }
                        MatrixI.add(this_row);
                    }
                   
                }
                
                lineCount++;

            } // end while

            inr.close();

            //
            // Now we know everything to be known:
            // Construct the problem matrix and column sums.
            //
            r = MatrixI.size();
            rowsums = new int[r];
            matrix = new int[r][c];
            for(int i = 0; i < r; i++) {
                ArrayList<Integer> this_row = MatrixI.get(i);
                for(int j = 1; j < c + 1 ; j++) {
                    matrix[i][j-1] = this_row.get(j);
                }
                rowsums[i] = this_row.get(c+1);
            }
            
            
        } catch (IOException e) {
            System.out.println(e);
        }
        
    } // end readFile


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

        String filename = "";
        if (args.length == 1) {
            filename = args[0];
            System.out.println("Using file " + filename);
        }

        SurvoPuzzle m = new SurvoPuzzle();
        if (filename.length() > 0) {
            m.readFile(filename);
        }
        m.model();
        m.search();

    } // end main


} // end class