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