1 // Copyright 2011 Hakan Kjellerstrand hakank@gmail.com 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 package com.google.ortools.contrib; 14 15 import com.google.ortools.Loader; 16 import com.google.ortools.constraintsolver.DecisionBuilder; 17 import com.google.ortools.constraintsolver.IntVar; 18 import com.google.ortools.constraintsolver.Solver; 19 import java.io.*; 20 import java.text.*; 21 import java.util.*; 22 23 public class Crossword { 24 /** Solving a simple crossword. See http://www.hakank.org/google_or_tools/crossword2.py */ solve()25 private static void solve() { 26 Solver solver = new Solver("Crossword"); 27 28 // 29 // data 30 // 31 String[] alpha = {"_", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", 32 "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"}; 33 34 int a = 1; 35 int b = 2; 36 int c = 3; 37 int d = 4; 38 int e = 5; 39 int f = 6; 40 int g = 7; 41 int h = 8; 42 int i = 9; 43 int j = 10; 44 int k = 11; 45 int l = 12; 46 int m = 13; 47 int n = 14; 48 int o = 15; 49 int p = 16; 50 int q = 17; 51 int r = 18; 52 int s = 19; 53 int t = 20; 54 int u = 21; 55 int v = 22; 56 int w = 23; 57 int x = 24; 58 int y = 25; 59 int z = 26; 60 61 int num_words = 15; 62 int word_len = 5; 63 64 int[][] AA = {{h, o, s, e, s}, // HOSES 65 {l, a, s, e, r}, // LASER 66 {s, a, i, l, s}, // SAILS 67 {s, h, e, e, t}, // SHEET 68 {s, t, e, e, r}, // STEER 69 {h, e, e, l, 0}, // HEEL 70 {h, i, k, e, 0}, // HIKE 71 {k, e, e, l, 0}, // KEEL 72 {k, n, o, t, 0}, // KNOT 73 {l, i, n, e, 0}, // LINE 74 {a, f, t, 0, 0}, // AFT 75 {a, l, e, 0, 0}, // ALE 76 {e, e, l, 0, 0}, // EEL 77 {l, e, e, 0, 0}, // LEE 78 {t, i, e, 0, 0}}; // TIE 79 80 int num_overlapping = 12; 81 int[][] overlapping = {{0, 2, 1, 0}, // s 82 {0, 4, 2, 0}, // s 83 {3, 1, 1, 2}, // i 84 {3, 2, 4, 0}, // k 85 {3, 3, 2, 2}, // e 86 {6, 0, 1, 3}, // l 87 {6, 1, 4, 1}, // e 88 {6, 2, 2, 3}, // e 89 {7, 0, 5, 1}, // l 90 {7, 2, 1, 4}, // s 91 {7, 3, 4, 2}, // e 92 {7, 4, 2, 4}}; // r 93 94 int N = 8; 95 96 // 97 // variables 98 // 99 IntVar[][] A = new IntVar[num_words][word_len]; 100 IntVar[] A_flat = new IntVar[num_words * word_len]; 101 // for labeling on A and E 102 IntVar[] all = new IntVar[(num_words * word_len) + N]; 103 104 for (int I = 0; I < num_words; I++) { 105 for (int J = 0; J < word_len; J++) { 106 A[I][J] = solver.makeIntVar(0, 26, "A[" + I + "," + J + "]"); 107 A_flat[I * word_len + J] = A[I][J]; 108 all[I * word_len + J] = A[I][J]; 109 } 110 } 111 112 IntVar[] E = solver.makeIntVarArray(N, 0, num_words, "E"); 113 for (int I = 0; I < N; I++) { 114 all[num_words * word_len + I] = E[I]; 115 } 116 117 // 118 // constraints 119 // 120 solver.addConstraint(solver.makeAllDifferent(E)); 121 122 for (int I = 0; I < num_words; I++) { 123 for (int J = 0; J < word_len; J++) { 124 solver.addConstraint(solver.makeEquality(A[I][J], AA[I][J])); 125 } 126 } 127 128 for (int I = 0; I < num_overlapping; I++) { 129 solver.addConstraint(solver.makeEquality( 130 solver 131 .makeElement(A_flat, 132 solver 133 .makeSum( 134 solver.makeProd(E[overlapping[I][0]], word_len).var(), overlapping[I][1]) 135 .var()) 136 .var(), 137 solver 138 .makeElement(A_flat, 139 solver 140 .makeSum( 141 solver.makeProd(E[overlapping[I][2]], word_len).var(), overlapping[I][3]) 142 .var()) 143 .var())); 144 } 145 146 // 147 // search 148 // 149 DecisionBuilder db = solver.makePhase(all, solver.INT_VAR_DEFAULT, solver.INT_VALUE_DEFAULT); 150 151 solver.newSearch(db); 152 153 // 154 // output 155 // 156 while (solver.nextSolution()) { 157 System.out.println("E:"); 158 for (int ee = 0; ee < N; ee++) { 159 int e_val = (int) E[ee].value(); 160 System.out.print(ee + ": (" + e_val + ") "); 161 for (int ii = 0; ii < word_len; ii++) { 162 System.out.print(alpha[(int) A[ee][ii].value()]); 163 } 164 System.out.println(); 165 } 166 167 System.out.println(); 168 } 169 170 solver.endSearch(); 171 172 // Statistics 173 System.out.println(); 174 System.out.println("Solutions: " + solver.solutions()); 175 System.out.println("Failures: " + solver.failures()); 176 System.out.println("Branches: " + solver.branches()); 177 System.out.println("Wall time: " + solver.wallTime() + "ms"); 178 } 179 main(String[] args)180 public static void main(String[] args) throws Exception { 181 Loader.loadNativeLibraries(); 182 Crossword.solve(); 183 } 184 } 185