/**
 *
 * Word square problem in Choco v2.
 *
 * This model creates a word square, i.e. a square matrix with 
 * different words. 
 *
 * It is based on the simple cross word model
 * http://www.hakank.org/choco/CrossWord.java
 *
 *
 * Compare with the following models:
 * - Comet : http://www.hakank.org/comet/word_square.co
 * - Gecode: http://www.hakank.org/gecode/word_square.gcc
 *
 *
 * 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.solver.*;
import choco.cp.solver.CPSolver;
import choco.cp.solver.constraints.*;
import choco.cp.solver.constraints.integer.*;
import choco.kernel.model.*;
import choco.kernel.model.constraints.*;
import choco.kernel.model.variables.*;
import choco.kernel.model.variables.integer.*;
import choco.kernel.model.variables.set.*;
import choco.kernel.solver.*;

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

/*

 Two solution for word length 7:

 Words:
 aphasia
 peasant
 habitat
 asinine
 satires
 inanest
 attests

 Words:
 lasagna
 aspires
 spireas
 airfare
 greater
 nearest
 asserts

*/


public class WordSquare {

    Model M;
    
    IntegerVariable E[];
    int N = 5;

    static ArrayList<String> dict = new ArrayList<String>(); // the word from the dictionary

    public void model(int word_length, int num_solutions) {

        M = new CPModel();

        //
        // place all words from the dictionary in the words matrix
        //
        int dict_size = dict.size();
        System.out.println("Number of words: " + dict_size);
        int[][] words = new int[dict_size][word_length];
        Iterator it = dict.iterator();
        int K = 0;
        while (it.hasNext()) {
            String str = (String) it.next();
            for(int J = 0; J < word_length; J++) {
                words[K][J] = str.charAt(J);
            }
            K++;
        }
        

        //
        // The variables: which word is selected
        //
        int num_e = word_length; // * 2;
        E = new IntegerVariable[num_e];
        for(int I = 0; I < num_e; I++) {
            E[I] = makeIntVar("E"+I, 0, dict_size);
        }

        // redundance constraint, but makes it faster
        M.addConstraint("cp:clique", allDifferent(E));

        //
        // constants for the nth constraint below
        //
        IntegerVariable [] C = new IntegerVariable[dict_size];
        for (int I = 0; I < word_length; I++) {
            C[I] = makeIntVar("C"+I, I,I);
        }

        // 
        // The overlappings (crossings)
        // 
        for(int I = 0; I < word_length ; I++) {
            for(int J = 0; J < word_length ; J++) {
                // Comet: words[E[i], j] ==  words[E[j],i]
                IntegerVariable tmp = makeIntVar("tmp" + I + " " + J, 0, dict_size);
                M.addConstraint(nth(E[I], C[J], words, tmp));
                M.addConstraint(nth(E[J], C[I], words, tmp));
            }
        }

        CPSolver S = new CPSolver();

        S.read(M);

        S.monitorTimeLimit(true);
        S.monitorBackTrackLimit(true);
        S.monitorNodeLimit(true);
        S.monitorFailLimit(true);

        S.solve();
        S.printRuntimeStatistics();

        // System.out.println(S.pretty());

        System.out.println("getNbSolutions: " + S.getNbSolutions());

        if(S.isFeasible()) {

            int counter = 0;
            do {

                System.out.println("Words:");
                for(int I = 0; I < num_e; I++) {                    
                    int e_tmp = S.getVar(E[I]).getVal();
                    System.out.println(dict.get(e_tmp));
                }

                System.out.println("\n");                

                counter++;

                if (num_solutions > 0 && counter >= num_solutions) {
                    break;
                }


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

        } else {

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

        }

    }


    /**
     * main
     *
     * java WordSquare word_len
     * java WordSquare word_len num_solutions
     * java WordSquare word_len num_solutions word_list
     *
     */
    public static void main(String args[]) {


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

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

        String dict_file = "/usr/share/dict/words";
        if (args.length > 2) {
            dict_file = args[2];
        }

        // Read the dictionary
        System.out.println("Reading the dictionary " + dict_file);
        try {
            BufferedReader inr = new BufferedReader(new FileReader(dict_file));
            String str;
            while ((str = inr.readLine()) != null) {
                str = str.trim();
                if (str.length() == word_len) {
                    if (str.matches("^[a-z]+$")) {
                        dict.add(str);
                        // System.out.println(str);
                    }
                }
            }

            inr.close();
           
            WordSquare m = new WordSquare();
            m.model(word_len, num_solutions);

        } catch (Exception e) {

            System.out.println(e);

        }

    } // end main

} // end class