/**
 *
 * Cross word problem in JaCoP
 *
 * This is a standard example for constraint logic programming. See e.g.
 *
 * http://www.cis.temple.edu/~ingargio/cis587/readings/constraints.html
 * """
 * We are to complete the puzzle
 *
 *      1   2   3   4   5
 *    +---+---+---+---+---+       Given the list of words:
 *  1 | 1 |   | 2 |   | 3 |             AFT     LASER
 *    +---+---+---+---+---+             ALE     LEE
 *  2 | # | # |   | # |   |             EEL     LINE
 *    +---+---+---+---+---+             HEEL    SAILS
 *  3 | # | 4 |   | 5 |   |             HIKE    SHEET
 *    +---+---+---+---+---+             HOSES   STEER
 *  4 | 6 | # | 7 |   |   |             KEEL    TIE
 *    +---+---+---+---+---+             KNOT
 *  5 | 8 |   |   |   |   |
 *    +---+---+---+---+---+
 *  6 |   | # | # |   | # |       The numbers 1,2,3,4,5,6,7,8 in the crossword
 *    +---+---+---+---+---+       puzzle correspond to the words
 *                                that will start at those locations.
 * """
 * 
 * The model was inspired by Sebastian Brand's Array Constraint cross 
 * word example:
 * http://www.cs.mu.oz.au/~sbrand/project/ac/
 * http://www.cs.mu.oz.au/~sbrand/project/ac/examples.pl
 *
 * Also compare with the following models:
 * - MiniZinc: http://www.hakank.org/minizinc/crossword.mzn
 * - Comet: http://www.hakank.org/comet/crossword.co
 * - Gecode: http://www.hakank.org/gecode/crossword.cpp
 * - Choco: http://www.hakank.org/choco/CrossWord.java
 *
 *
 * JaCoP model by Hakan Kjellerstrand (hakank@bonetmail.com)
 * http://www.hakank.org/JaCoP
 *
 */

/*

  Solution:
  E0: 1 laser
  E1: 3 sheet
  E2: 5 heel
  E3: 7 keel
  E4: 8 knot
  E5: 12 eel
  E6: 14 tie
  E7: 2 sails
  
*/

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

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

public class CrossWord {

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

    public void model() {

        store = new Store();
        letters.trim();
        letters_array = letters.split("");

        int a = 1 ; int b =  2; int c =  3; int d =  4; int e =  5; 
        int f = 6 ; int g =  7; int h =  8; int i =  9; int j = 10; 
        int k = 11; int l = 12; int m = 13; int n = 14; 
        int o = 15; int p = 16; int q = 17; int r = 18; 
        int s = 19; int t = 20; int u = 21; int v = 22; 
        int w = 23; int x = 24; int y = 25; int z = 26; 
        
        int zero = 0; 


        //
        // The words that may be used
        //
        int num_words = 15;
        int word_len  = 5;
        int[][] words = 
            {
                {h, o, s, e, s},        //  HOSES
                {l, a, s, e, r},        //  LASER
                {s, a, i, l, s},        //  SAILS
                {s, h, e, e, t},        //  SHEET
                {s, t, e, e, r},        //  STEER
                {h, e, e, l, zero},     //  HEEL
                {h, i, k, e, zero},     //  HIKE
                {k, e, e, l, zero},     //  KEEL
                {k, n, o, t, zero},     //  KNOT
                {l, i, n, e, zero},     //  LINE
                {a, f, t, zero, zero},  //  AFT
                {a, l, e, zero, zero},  //  ALE
                {e, e, l, zero, zero},  //  EEL
                {l, e, e, zero, zero},  //  LEE
                {t, i, e, zero, zero} //  TIE
            };
        
        //
        // Some trickery: 
        // We use the _transpose_ of the AX matrix in the 
        // Element constraints below.
        //
        int[][] words_t = new int[word_len][num_words];
        for(int I = 0; I < word_len; I++) {
            for(int J = 0; J < num_words; J++) {
                words_t[I][J] = words[J][I];
            }
        }

        int num_overlapping = 12;
        int[][] overlapping =
        {
            {0,2,   1,0}, 
            {0,4,   2,0}, 
            
            {3,1,   1,2}, 
            {3,2,   4,0}, 
            {3,3,   2,2}, 
            
            {6,0,   1,3}, 
            {6,1,   4,1}, 
            {6,2,   2,3}, 
            
            {7,0,   5,1}, 
            {7,2,   1,4}, 
            {7,3,   4,2}, 
            {7,4,   2,4}  
        };
 
        //
        // variables for the positions
        //
        int num_positions = 8;
        IntVar[] E = new IntVar[num_positions];
        for(int I = 0; I < num_positions; I++) {
            E[I] = new IntVar(store, "E" + I, 0, num_words-1);
        }
        
        //
        // TMP is temporary variables to connect letters in each word
        //
        for (int I = 0; I < num_overlapping; I++) {
            IntVar tmp = new IntVar(store, "TMP" + I, 0, num_words*word_len);

            store.impose(new Element(E[overlapping[I][0]], words_t[overlapping[I][1]], tmp));
            store.impose(new Element(E[overlapping[I][2]], words_t[overlapping[I][3]], tmp));
        }


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

        Search label = new DepthFirstSearch ();
        label.getSolutionListener().searchAll(true);
        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);
            for(int I = 0; I < num_positions; I++) {
                int e_val = E[I].value();
                System.out.print("E" + I + ": " +  e_val + " ");
                for(int J = 0; J < word_len; J++) {
                    System.out.print(letters_array[words[e_val][J]]);
                }
                System.out.println();
            }

        } else {

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

        } // end if result

    }


    public static void main(String args[]) {

      CrossWord m = new CrossWord();
      m.model();

    }
}