/**
 *
 * Word square problem in JaCoP.
 *
 *  From http://en.wikipedia.org/wiki/Word_square
 *  """
 *  A word square is a special case of acrostic. It consists of a set of words,
 *  all having the same number of letters as the total number of words (the
 *  "order" of the square); when the words are written out in a square grid
 *  horizontally, the same set of words can be read vertically.
 *  """
 *
 *  Compare with the following models:
 *  - http://www.hakank.org/comet/word_square.co
 *  - http://www.hakank.org/gecode/word_square.cpp
 *  - http://www.hakank.org/choco/WordSquare.java
 *  - http://www.hakank.org/minizinc/crosswords.co
 *
 *
 * JaCoP model by Hakan Kjellerstrand (hakank@bonetmail.com)
 * http://www.hakank.org/JaCoP
 *
 */

/*

  One solution of order 5:

  Solution : [E0=15033, E1=14919, E2=8115, E3=6549, E4=3170]
  Nodes : 14
  Decisions : 9
  Wrong Decisions : 5
  Backtracks : 0
  Max Depth : 9

  Words:
  zymic
  yuans
  mason
  inone
  csnet
  
 */

import JaCoP.constraints.*;
import JaCoP.core.*;
import JaCoP.search.*;

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



public class WordSquare {

    Store store;
    
    String letters = "abcdefghijklmnopqrstuvwxyz";
    String[] letters_array;

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

    public void model(int word_length, int num_solutions) {

        store = new Store();

        //
        // Place all words from the dictionary in the words matrix
        //
        // Some trickery: We use the _transpose_ of this word matrix in the 
        // Element constraints below.
        // (Compare with http://www.hakank.org/JaCoP/CrossWord.java)
        //
        int dict_size = dict.size();
        System.out.println("Number of words: " + dict_size);
        int[][] words = new int[word_length][dict_size];
        Iterator it = dict.iterator();
        int k = 0;
        while (it.hasNext()) {
            String str = (String) it.next();
            for(int j = 0; j < word_length; j++) {
                words[j][k] = str.charAt(j);
            }
            k++;
        }
        
        //
        // variables for the positions
        //
        int num_positions = word_length;
        IntVar[] E = new IntVar[num_positions];
        for(int i = 0; i < num_positions; i++) {
            E[i] = new IntVar(store, "E" + i, 0, dict_size-1);
        }
        

        // 
        // The overlappings (crossings).
        // Note that we use a transposed word matrix for the Element.
        //
        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]
                IntVar tmp = new IntVar(store, "tmp" + i + " " + j, 0, dict_size);
                store.impose(new Element(E[i], words[j], tmp));
                store.impose(new Element(E[j], words[i], tmp));
            }
        }

        // All values in x should be different
        store.impose(new Alldifferent(E));

        SelectChoicePoint select = 
            new SimpleSelect(E,
                              new SmallestDomain(),
                              new IndomainMax ()
                              );

        Search label = new DepthFirstSearch ();
        label.getSolutionListener().searchAll(false);
        label.getSolutionListener().recordSolutions(true);

        // The actual search
        boolean result = label.labeling(store, select);
        
        int numSolutions = label.getSolutionListener().solutionsNo();
        System.out.println("numSolutions: " + numSolutions);

        if (result) {

            System.out.print("Crossword:");
            // label.printAllSolutions();

            System.out.println("numSolutions: " + numSolutions);

            System.out.println("Words:");
            for(int i = 0; i < word_length; i++) {
                System.out.println(dict.get(E[i].value()-1));
            }

        } else {

            System.out.println("No solutions.");

        } // end if result

    }


    public static void main(String args[]) {

        int word_len = 3;
        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-zA-Z]+$")) {
                        dict.add(str);
                    }
                }
            }

            inr.close();
           
            WordSquare m = new WordSquare();
            m.model(word_len, num_solutions);
            
        } catch (Exception e) {

            System.out.println(e);
            
        }

    } // end main

} // end class