/** * * Cross word problem in Choco v2 * * * * 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 * * * Note: This version adds some extra requirements after * some comments by Stephane Mangon * - allDifferent on E * - ensure that the length of the word is of * correct length * * * Also compare with my other 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 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.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.*; public class CrossWord2 { Model M; String letters = "abcdefghijklmnopqrstuvwxyz"; String[] letters_array; IntegerVariable E[]; int N = 5; public void model() { /** * * 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 * */ M = new CPModel(); letters.trim(); letters_array = letters.split(""); // int X = -2; // block // int U = -1; // unknown // the letters 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; // // these are the words to use // int max_word_length = 5; int[][] AX = {{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 // {h, i, k, e, s}, // HIKES // Extra: experimental {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 // Extra: Calculate the real word lengths int num_words = AX.length; int[] real_word_length = new int[num_words]; for(int I = 0; I < num_words; I++) { int len = 0; for(int J = 0; J < N; J++) { if (AX[I][J] > zero) { len++; } } real_word_length[I] = len; } // // constants, i.e. offset in the words // IntegerVariable [] W = new IntegerVariable[max_word_length]; for (int I = 0; I < max_word_length; I++) { W[I] = makeIntVar("W"+I, I,I); } int num_e = 8; E = new IntegerVariable[num_e]; for(int I = 0; I < num_e; I++) { E[I] = makeIntVar("E"+I, 0, 15); } // Extra: added after a suggestion by Stephane Mangon M.addConstraint(allDifferent(E)); // constraints // // The overlapping (crossings) // int num_overlapping = 12; int[][] overlapping = { {0,2, 1,0}, // s AX[E[0], 2] = AX[E[1], 0] {0,4, 2,0}, // s etc {3,1, 1,2}, // i {3,2, 4,0}, // k {3,3, 2,2}, // e {6,0, 1,3}, // l {6,1, 4,1}, // e {6,2, 2,3}, // e {7,0, 5,1}, // l {7,2, 1,4}, // s {7,3, 4,2}, // e {7,4, 2,4} // r }; for(int I = 0; I < num_overlapping; I++) { IntegerVariable tmp = makeIntVar("tmp" + I, 1, 26); M.addConstraint(nth(E[overlapping[I][0]], W[overlapping[I][1]], AX, tmp)); M.addConstraint(nth(E[overlapping[I][2]], W[overlapping[I][3]], AX, tmp)); } // Extra: length of the words to fill in int[] len_of_wanted = { 5, // word E0 5, // word E1 5, // word E2 4, // word E3 4, // word E4 3, // word E5 3, // word E6 5 // word E7 }; // Extra: Ensure that the selected word can fit the grid, i.e. <= N // (added after a question/suggestion by Stephane Mangon) for(int K = 0; K < num_e; K++) { IntegerVariable len1 = makeIntVar("len1_" + K, len_of_wanted[K], len_of_wanted[K]); M.addConstraint(nth(E[K], real_word_length, len1)); } CPSolver S = new CPSolver(); S.read(M); S.monitorFailLimit(true); S.solve(); S.printRuntimeStatistics(); // System.out.println(S.pretty()); System.out.println("getNbSolutions: " + S.getNbSolutions()); if(S.isFeasible()) { do { for(int I = 0; I < num_e; I++) { int e_tmp = S.getVar(E[I]).getVal(); System.out.print("E" + I + ": " + e_tmp + ": "); for(int J = 0; J < max_word_length; J++) { System.out.print(letters_array[AX[e_tmp][J]]); } System.out.print(" ("); for(int J = 0; J < max_word_length; J++) { System.out.print(AX[e_tmp][J] + " "); } System.out.println(")"); } System.out.println("\n"); } while (S.nextSolution() == Boolean.TRUE); } else { System.out.println("Problem is not feasible."); } } // // main // public static void main(String args[]) { CrossWord2 m = new CrossWord2(); m.model(); } }