Generated on Sat Oct 20 2018 12:43:45 for Gecode by doxygen 1.8.13
kakuro.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Contributing authors:
7  * Mikael Lagerkvist <lagerkvist@gecode.org>
8  *
9  * Copyright:
10  * Christian Schulte, 2007
11  * Mikael Lagerkivst, 2007
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/driver.hh>
39 #include <gecode/int.hh>
40 #include <gecode/minimodel.hh>
41 
42 using namespace Gecode;
43 
44 namespace {
45 
66 
67  // Easy, Author: Casty
68  const int k0[] = {
69  // Dimension w x h
70  12,10,
71  // Vertical constraints
72  2, 0, 5,16, 3, 0, 2, 4, 5, 0, 3, 6, 6, 0, 2, 4,
73  7, 0, 5,15, 10, 0, 3, 6, 11, 0, 3, 7, 1, 1, 3, 7,
74  9, 1, 5,16, 4, 2, 2, 5, 8, 2, 2, 3, 3, 3, 5,16,
75  6, 3, 3, 8, 5, 4, 5,15, 10, 4, 5,15, 4, 5, 2, 3,
76  8, 5, 2, 4, 11, 5, 3, 7, 1, 6, 3, 6, 2, 6, 3, 7,
77  7, 6, 3, 7, 6, 7, 2, 3, 9, 7, 2, 4, -1,
78  // Horizontal constraints
79  1, 1, 2, 7, 4, 1, 3, 9, 9, 1, 2, 4, 0, 2, 3, 7,
80  4, 2, 3, 7, 8, 2, 3, 6, 0, 3, 2, 3, 3, 3, 2, 4,
81  6, 3, 5,16, 0, 4, 4,10, 5, 4, 4,10, 1, 5, 2,10,
82  4, 5, 3, 6, 8, 5, 2, 5, 2, 6, 4,10, 7, 6, 4,12,
83  0, 7, 5,16, 6, 7, 2, 4, 9, 7, 2, 4, 0, 8, 3, 7,
84  4, 8, 3, 8, 8, 8, 3, 6, 0, 9, 2, 3, 4, 9, 3, 7,
85  8, 9, 2, 3, -1
86  };
87 
88  // Easy, Author: Ogawa Minori
89  const int k1[] = {
90  // Dimension w x h
91  12,10,
92  // Vertical constraints
93  1, 0, 2, 4, 2, 0, 5,15, 5, 0, 5,18, 6, 0, 2,12,
94  7, 0, 3, 8, 10, 0, 3,24, 11, 0, 3,23, 3, 1, 2, 7,
95  9, 1, 3,24, 4, 2, 5,16, 8, 2, 5,35, 1, 3, 2,12,
96  6, 3, 3,17, 7, 4, 5,34, 10, 4, 5,34, 11, 4, 2,16,
97  3, 5, 3, 6, 1, 6, 3, 7, 2, 6, 3, 6, 5, 6, 3,23,
98  9, 6, 2,10, 6, 7, 2,14, 11, 7, 2,10, -1,
99  // Horizontal constraints
100  0, 1, 2, 3, 4, 1, 3,15, 9, 1, 2,16, 0, 2, 3, 6,
101  4, 2, 3, 7, 8, 2, 3,24, 1, 3, 4,11, 6, 3, 5,34,
102  0, 4, 2,14, 3, 4, 3,23, 7, 4, 2,14, 0, 5, 2, 7,
103  3, 5, 5,15, 9, 5, 2,17, 2, 6, 2, 6, 5, 6, 3,23,
104  9, 6, 2,13, 0, 7, 5,16, 6, 7, 4,30, 0, 8, 3, 6,
105  4, 8, 3,23, 8, 8, 3, 7, 0, 9, 2, 4, 4, 9, 3,24,
106  9, 9, 2,17, -1
107  };
108 
109  // Easy, Author: SAKAMOTO, Nobuyuki
110  const int k2[] = {
111  // Dimension w x h
112  12,10,
113  // Vertical constraints
114  2, 0, 5,15, 3, 0, 2, 3, 7, 0, 3, 7, 8, 0, 4,23,
115  9, 0, 2,12, 10, 0, 3,20, 11, 0, 3, 9, 4, 1, 3, 7,
116  5, 1, 4,10, 1, 2, 3, 6, 6, 2, 5,15, 9, 3, 2,16,
117  3, 4, 2, 3, 7, 4, 4,13, 10, 4, 5,35, 11, 4, 3,23,
118  4, 5, 4,11, 8, 5, 3,23, 1, 6, 3,23, 2, 6, 3,14,
119  5, 6, 3,11, 3, 7, 2,13, 9, 7, 2,17, -1,
120  // Horizontal constraints
121  1, 1, 2, 4, 6, 1, 5,15, 1, 2, 4,11, 6, 2, 5,34,
122  0, 3, 2, 3, 3, 3, 5,15, 9, 3, 2,10, 0, 4, 2, 4,
123  3, 4, 3, 6, 7, 4, 2,17, 0, 5, 3, 7, 4, 5, 3, 8,
124  8, 5, 3,18, 2, 6, 2, 3, 5, 6, 3,11, 9, 6, 2,16,
125  0, 7, 2,16, 3, 7, 5,16, 9, 7, 2,17, 0, 8, 5,16,
126  6, 8, 4,30, 0, 9, 5,35, 8, 9, 2,17, -1
127  };
128 
129  // Easy, Author: country mushroom
130  const int k3[] = {
131  // Dimension w x h
132  12,10,
133  // Vertical constraints
134  3, 0, 3, 7, 4, 0, 6,21, 7, 0, 4,29, 8, 0, 2,17,
135  10, 0, 4,29, 11, 0, 3,23, 2, 1, 3, 6, 6, 1, 2,16,
136  9, 1, 4,14, 1, 2, 2, 4, 5, 2, 2, 3, 8, 3, 6,22,
137  3, 4, 4,10, 2, 5, 4,11, 5, 5, 4,10, 7, 5, 2,10,
138  10, 5, 3,24, 11, 5, 2,16, 1, 6, 3, 7, 6, 6, 2, 9,
139  9, 6, 3,23, 4, 7, 2, 4, -1,
140  // Horizontal constraints
141  2, 1, 2, 4, 6, 1, 2,17, 9, 1, 2,16, 1, 2, 3, 6,
142  5, 2, 6,39, 0, 3, 7,28, 8, 3, 3,24, 0, 4, 2, 3,
143  3, 4, 2, 3, 6, 4, 4,20, 2, 5, 2, 9, 7, 5, 2, 4,
144  1, 6, 4,10, 6, 6, 2, 3, 9, 6, 2,16, 0, 7, 3, 6,
145  4, 7, 7,42, 0, 8, 6,21, 7, 8, 3,21, 0, 9, 2, 4,
146  3, 9, 2, 3, 7, 9, 2,16, -1
147  };
148 
149  // Medium, Author: Komieda
150  const int k4[] = {
151  // Dimension w x h
152  20,12,
153  // Vertical constraints
154  3, 0, 3,21, 4, 0, 2, 4, 5, 0, 4,11, 8, 0, 2, 8,
155  9, 0, 3, 7, 11, 0, 2, 3, 12, 0, 3, 6, 15, 0, 6,39,
156  16, 0, 2, 3, 17, 0, 3,23, 2, 1, 5,15, 6, 1, 4,10,
157  10, 1, 4,11, 14, 1, 4,11, 18, 1, 3, 6, 1, 2, 3,24,
158  7, 2, 4,14, 13, 2, 2,10, 19, 2, 2,16, 4, 3, 5,18,
159  8, 3, 4,10, 11, 3, 4,12, 16, 3, 5,33, 3, 4, 3,23,
160  9, 4, 4,29, 12, 4, 4,30, 17, 4, 3,18, 5, 5, 6,38,
161  13, 5, 4,29, 18, 5, 5,15, 6, 6, 4,25, 10, 6, 4,12,
162  14, 6, 4,28, 19, 6, 3,21, 1, 7, 2, 4, 2, 7, 3, 7,
163  7, 7, 2, 7, 15, 7, 4,11, 3, 8, 3,19, 8, 8, 3,24,
164  11, 8, 3, 7, 17, 8, 3, 6, 4, 9, 2,16, 9, 9, 2,16,
165  12, 9, 2,17, 16, 9, 2, 5, -1,
166  // Horizontal constraints
167  2, 1, 3, 7, 7, 1, 2, 4, 10, 1, 2, 4, 14, 1, 3,19,
168  1, 2, 5,18, 7, 2, 5,15, 13, 2, 5,16, 0, 3, 3,21,
169  4, 3, 3, 6, 8, 3, 2, 3, 11, 3, 4,11, 16, 3, 3,20,
170  0, 4, 2,14, 3, 4, 5,15, 9, 4, 2, 3, 12, 4, 4,29,
171  17, 4, 2, 8, 0, 5, 4,27, 5, 5, 7,42, 13, 5, 4,12,
172  1, 6, 4,12, 6, 6, 3, 8, 10, 6, 3,20, 14, 6, 4,29,
173  2, 7, 4,28, 7, 7, 7,28, 15, 7, 4,28, 0, 8, 2, 3,
174  3, 8, 4,11, 8, 8, 2,10, 11, 8, 5,35, 17, 8, 2,10,
175  0, 9, 3, 6, 4, 9, 4,30, 9, 9, 2, 3, 12, 9, 3,19,
176  16, 9, 3, 7, 1,10, 5,34, 7,10, 5,34, 13,10, 5,17,
177  2,11, 3,23, 7,11, 2,17, 10,11, 2,10, 14,11, 3, 6,
178  -1
179  };
180 
181  // Medium, Author: crimson
182  const int k5[] = {
183  // Dimension w x h
184  20,12,
185  // Vertical constraints
186  1, 0, 2, 3, 2, 0, 5,33, 4, 0, 2, 8, 5, 0, 4,14,
187  7, 0, 5,15, 8, 0, 3,19, 9, 0, 2,12, 11, 0, 4,11,
188  12, 0, 2, 4, 13, 0, 5,16, 15, 0, 4,11, 16, 0, 2,17,
189  18, 0, 5,34, 19, 0, 2,17, 3, 1, 2, 3, 10, 1, 9,45,
190  17, 1, 2,16, 6, 2, 3,20, 14, 2, 3,12, 1, 3, 2,13,
191  4, 3, 5,33, 9, 3, 3,20, 16, 3, 5,21, 19, 3, 2, 8,
192  3, 4, 3,11, 8, 4, 3,11, 12, 4, 3, 7, 17, 4, 3, 8,
193  11, 5, 3,23, 1, 6, 2,11, 2, 6, 5,15, 6, 6, 3,23,
194  7, 6, 5,27, 13, 6, 5,30, 14, 6, 3, 7, 18, 6, 5,15,
195  19, 6, 2, 3, 5, 7, 4,26, 9, 7, 4,27, 15, 7, 4,27,
196  3, 8, 2, 7, 12, 8, 3,24, 17, 8, 2,17, 1, 9, 2, 5,
197  4, 9, 2, 9, 8, 9, 2, 3, 11, 9, 2,16, 16, 9, 2,16,
198  19, 9, 2,10, -1,
199  // Horizontal constraints
200  0, 1, 2, 4, 3, 1, 2, 7, 6, 1, 3, 7, 10, 1, 3, 7,
201  14, 1, 2,11, 17, 1, 2,16, 0, 2, 5,16, 6, 2, 7,42,
202  14, 2, 5,35, 1, 3, 2,10, 4, 3, 4,15, 9, 3, 2, 6,
203  12, 3, 3, 7, 16, 3, 2,13, 0, 4, 2,17, 3, 4, 4,29,
204  8, 4, 3,19, 12, 4, 4,11, 17, 4, 2, 9, 0, 5, 4,29,
205  5, 5, 5,33, 11, 5, 3, 6, 15, 5, 4,29, 2, 6, 2, 4,
206  7, 6, 5,16, 15, 6, 2, 4, 0, 7, 4,12, 5, 7, 3,10,
207  9, 7, 5,18, 15, 7, 4,12, 0, 8, 2,13, 3, 8, 4,29,
208  8, 8, 3,24, 12, 8, 4,23, 17, 8, 2, 5, 1, 9, 2, 6,
209  4, 9, 3,24, 8, 9, 2, 4, 11, 9, 4,28, 16, 9, 2,11,
210  0,10, 5,15, 6,10, 7,41, 14,10, 5,34, 0,11, 2, 3,
211  3,11, 2,17, 6,11, 3,14, 10,11, 3,23, 14,11, 2,11,
212  17,11, 2, 4, -1
213  };
214 
215  // Hard, Author: Yuichi Saito
216  const int k6[] = {
217  // Dimension w x h
218  20,12,
219  // Vertical constraints
220  1, 0, 2, 6, 2, 0, 2,16, 4, 0, 3,10, 5, 0, 2,12,
221  9, 0, 7,28, 10, 0, 2,12, 11, 0, 3,24, 15, 0, 3,10,
222  16, 0, 2,17, 17, 0, 6,22, 3, 1, 3,18, 6, 1, 4,10,
223  8, 1, 2, 8, 12, 1, 2,10, 13, 1, 3,18, 18, 1, 3,12,
224  7, 2, 4,11, 14, 2, 3, 7, 19, 2, 2, 7, 1, 3, 2, 8,
225  2, 3, 3, 7, 5, 3, 4,25, 10, 3, 2, 4, 16, 3, 4,15,
226  4, 4, 4,11, 11, 4, 7,42, 12, 4, 2,17, 15, 4, 4,26,
227  3, 5, 6,22, 8, 5, 2,16, 13, 5, 4,30, 18, 5, 3,24,
228  6, 6, 3, 7, 10, 6, 2, 4, 14, 6, 4,29, 19, 6, 2,14,
229  1, 7, 2,16, 2, 7, 3,11, 7, 7, 3,24, 17, 7, 3,21,
230  5, 8, 3,23, 8, 8, 2,12, 9, 8, 3,20, 12, 8, 2,17,
231  16, 8, 3, 6, 4, 9, 2, 9, 10, 9, 2,16, 15, 9, 2, 9,
232  18, 9, 2, 3, 19, 9, 2,12, -1,
233  // Horizontal constraints
234  0, 1, 2,10, 3, 1, 2, 5, 8, 1, 3,23, 14, 1, 3,11,
235  0, 2, 6,38, 7, 2, 6,39, 14, 2, 4,30, 2, 3, 2,10,
236  5, 3, 4,11, 10, 3, 5,18, 16, 3, 3, 7, 0, 4, 3, 7,
237  4, 4, 3, 7, 8, 4, 2, 6, 12, 4, 2, 8, 15, 4, 4,11,
238  0, 5, 2, 8, 3, 5, 4,14, 8, 5, 4,24, 13, 5, 4,10,
239  1, 6, 4,13, 6, 6, 3,14, 10, 6, 3,19, 14, 6, 4,29,
240  2, 7, 4,15, 7, 7, 4,14, 12, 7, 4,29, 17, 7, 2,16,
241  0, 8, 4,29, 5, 8, 2,13, 9, 8, 2, 8, 12, 8, 3,23,
242  16, 8, 3,22, 0, 9, 3,10, 4, 9, 5,32, 10, 9, 4,29,
243  15, 9, 2,10, 1,10, 4,14, 6,10, 6,39, 13,10, 6,22,
244  2,11, 3,21, 8,11, 3,23, 14,11, 2, 6, 17,11, 2,11,
245  -1
246  };
247 
248  // Hard, Author: mimic
249  const int k7[] = {
250  // Dimension w x h
251  22,14,
252  // Vertical constraints
253  1, 0, 3,23, 2, 0, 4,29, 3, 0, 2,16, 7, 0, 2, 7,
254  8, 0, 2,10, 9, 0, 5,30, 13, 0, 7,41, 14, 0, 2,16,
255  15, 0, 4,29, 17, 0, 2, 3, 18, 0, 6,21, 20, 0, 3, 7,
256  21, 0, 2, 4, 4, 1, 5,35, 6, 1, 2, 4, 10, 1, 2,17,
257  12, 1, 3,24, 19, 1, 9,45, 5, 2, 3,23, 11, 2, 9,45,
258  16, 2, 4,21, 3, 3, 9,45, 7, 3, 5,15, 8, 3, 4,10,
259  14, 3, 2,10, 17, 3, 2, 3, 6, 4, 2, 4, 10, 4, 4,30,
260  20, 4, 4,11, 2, 5, 4,13, 12, 5, 4,30, 15, 5, 5,35,
261  21, 5, 2, 4, 1, 6, 2, 4, 9, 6, 7,41, 14, 6, 4,29,
262  4, 7, 6,38, 6, 7, 4,11, 16, 7, 2,16, 18, 7, 5,15,
263  5, 8, 2, 9, 8, 8, 2,17, 13, 8, 5,16, 17, 8, 3, 7,
264  7, 9, 4,20, 10, 9, 3,23, 20, 9, 4,12, 2,10, 3,23,
265  12,10, 2, 6, 16,10, 2, 4, 21,10, 3, 9, 1,11, 2,16,
266  5,11, 2,16, 8,11, 2,16, 14,11, 2, 6, 15,11, 2, 4,
267  19,11, 2, 4, -1,
268  // Horizontal constraints
269  0, 1, 3,23, 6, 1, 3, 8, 12, 1, 3,23, 16, 1, 2, 4,
270  19, 1, 2, 4, 0, 2, 4,30, 5, 2, 5,31, 11, 2, 4,29,
271  16, 2, 5,15, 0, 3, 2,16, 3, 3, 3,19, 8, 3, 5,32,
272  14, 3, 2,17, 17, 3, 3, 8, 1, 4, 4,29, 6, 4, 3, 9,
273  10, 4, 9,45, 2, 5, 9,45, 12, 5, 2,17, 15, 5, 5,16,
274  1, 6, 3,24, 5, 6, 3, 6, 9, 6, 4,30, 14, 6, 2,16,
275  17, 6, 4,11, 0, 7, 3, 7, 6, 7, 9,45, 18, 7, 3, 7,
276  0, 8, 4,11, 5, 8, 2, 4, 8, 8, 4,29, 13, 8, 3,23,
277  17, 8, 3, 7, 1, 9, 5,16, 7, 9, 2,17, 10, 9, 9,45,
278  2,10, 9,45, 12,10, 3,23, 16,10, 4,14, 1,11, 3,24,
279  5,11, 2, 6, 8,11, 5,16, 15,11, 3, 7, 19,11, 2, 8,
280  0,12, 5,35, 6,12, 4,30, 11,12, 5,15, 17,12, 4,11,
281  0,13, 2,17, 3,13, 2,16, 6,13, 3,24, 12,13, 3, 6,
282  18,13, 3, 7, -1
283  };
284 
285  // Hard, Author: OX
286  const int k8[] = {
287  // Dimension w x h
288  22,14,
289  // Vertical constraints
290  1, 0, 2, 4, 2, 0, 5,15, 5, 0, 5,16, 6, 0, 2,10,
291  7, 0, 3,18, 8, 0, 4,29, 10, 0, 5,16, 11, 0, 2, 6,
292  13, 0, 2, 8, 14, 0, 5,16, 15, 0, 6,38, 18, 0, 5,15,
293  19, 0, 2, 8, 20, 0, 3, 7, 21, 0, 3, 8, 3, 1, 9,45,
294  16, 1, 2, 4, 4, 2, 2, 3, 9, 2, 8,39, 17, 2, 2, 3,
295  1, 3, 2, 5, 6, 3, 6,22, 11, 3, 3,22, 13, 3, 8,38,
296  19, 3, 9,45, 7, 4, 2, 4, 12, 4, 3,24, 16, 4, 6,38,
297  20, 4, 3,24, 4, 5, 2,16, 8, 5, 2,14, 17, 5, 2,16,
298  21, 5, 2,11, 1, 6, 2, 4, 2, 6, 3, 8, 5, 6, 2, 7,
299  10, 6, 3,18, 14, 6, 2,16, 18, 6, 2,16, 7, 7, 6,22,
300  11, 7, 3, 7, 15, 7, 2,15, 4, 8, 5,35, 8, 8, 5,34,
301  12, 8, 5,34, 17, 8, 5,34, 20, 8, 5,34, 21, 8, 2, 3,
302  5, 9, 2,16, 14, 9, 4,12, 18, 9, 2, 7, 1,10, 3,23,
303  2,10, 3,21, 6,10, 2, 9, 15,10, 3,20, 3,11, 2,17,
304  9,11, 2, 4, 11,11, 2, 4, 16,11, 2,10, 21,11, 2,16,
305  -1,
306  // Horizontal constraints
307  0, 1, 2, 6, 4, 1, 4,30, 9, 1, 2, 6, 12, 1, 3,10,
308  17, 1, 4,12, 0, 2, 3, 8, 4, 2, 4,11, 9, 2, 2, 4,
309  12, 2, 4,20, 17, 2, 4,11, 1, 3, 4,12, 6, 3, 4,28,
310  13, 3, 5,15, 19, 3, 2, 5, 0, 4, 6,22, 7, 4, 4,28,
311  12, 4, 3, 8, 16, 4, 3, 6, 0, 5, 3, 7, 4, 5, 3, 7,
312  8, 5, 8,40, 17, 5, 3,22, 2, 6, 2, 8, 5, 6, 4,12,
313  10, 6, 3,23, 14, 6, 3,22, 18, 6, 3,22, 0, 7, 6,38,
314  7, 7, 3,24, 11, 7, 3,23, 15, 7, 6,39, 0, 8, 3, 6,
315  4, 8, 3, 6, 8, 8, 3, 6, 12, 8, 4,29, 17, 8, 2,14,
316  1, 9, 3,18, 5, 9, 8,36, 14, 9, 3,22, 18, 9, 3,10,
317  2,10, 3,22, 6,10, 3,24, 10,10, 4,10, 15,10, 6,21,
318  0,11, 2,16, 3,11, 5,34, 11,11, 4,29, 16,11, 4,30,
319  0,12, 4,29, 5,12, 4,12, 10,12, 2,10, 13,12, 4,10,
320  18,12, 3,23, 0,13, 4,28, 6,13, 3, 7, 10,13, 2,11,
321  13,13, 4,28, 19,13, 2,13, -1
322  };
323 
324  // Hard, Author: TAKEI Daisuke
325  const int k9[] = {
326  // Dimension w x h
327  22,14,
328  // Vertical constraints
329  1, 0, 4,10, 2, 0, 4,24, 3, 0, 3, 7, 7, 0, 3, 8,
330  8, 0, 2,17, 9, 0, 3,13, 13, 0, 3,22, 14, 0, 2,12,
331  15, 0, 3,24, 19, 0, 3,19, 20, 0, 4,28, 21, 0, 4,14,
332  4, 1, 5,16, 6, 1, 5,17, 10, 1, 5,32, 12, 1, 5,34,
333  16, 1, 5,35, 18, 1, 5,31, 5, 2, 3, 9, 11, 2, 3, 7,
334  17, 2, 3, 7, 3, 4, 5,27, 7, 4, 5,16, 9, 4, 5,20,
335  13, 4, 5,30, 15, 4, 5,30, 19, 4, 5,26, 1, 5, 3,12,
336  2, 5, 3,20, 8, 5, 3,22, 14, 5, 3, 9, 20, 5, 3,10,
337  21, 5, 3,20, 4, 7, 5,31, 6, 7, 5,16, 10, 7, 5,17,
338  12, 7, 5,32, 16, 7, 5,19, 18, 7, 5,34, 5, 8, 3, 8,
339  11, 8, 3,24, 17, 8, 3,24, 1, 9, 4,10, 2, 9, 4,15,
340  20, 9, 4,30, 21, 9, 4,12, 3,10, 3,20, 7,10, 3, 6,
341  9,10, 3, 9, 13,10, 3, 6, 15,10, 3, 7, 19,10, 3,24,
342  8,11, 2, 8, 14,11, 2, 7, -1,
343  // Horizontal constraints
344  0, 1, 3, 7, 6, 1, 3,12, 12, 1, 3,23, 18, 1, 3,23,
345  0, 2, 4,11, 5, 2, 5,19, 11, 2, 5,33, 17, 2, 4,28,
346  0, 3, 7,28, 8, 3, 5,34, 14, 3, 7,29, 0, 4, 2,12,
347  3, 4, 3, 7, 9, 4, 3,16, 15, 4, 3,10, 19, 4, 2,10,
348  2, 5, 5,18, 8, 5, 5,20, 14, 5, 5,29, 0, 6, 4,24,
349  5, 6, 5,35, 11, 6, 5,23, 17, 6, 4,26, 0, 7, 3,23,
350  6, 7, 3, 9, 12, 7, 3,10, 18, 7, 3,23, 0, 8, 4,15,
351  5, 8, 5,19, 11, 8, 5,33, 17, 8, 4,10, 2, 9, 5,19,
352  8, 9, 5,35, 14, 9, 5,31, 0,10, 2, 4, 3,10, 3,10,
353  9,10, 3,18, 15,10, 3,24, 19,10, 2,12, 0,11, 7,41,
354  8,11, 5,23, 14,11, 7,36, 0,12, 4,14, 5,12, 5,17,
355  11,12, 5,15, 17,12, 4,26, 0,13, 3, 7, 6,13, 3, 7,
356  12,13, 3, 6, 18,13, 3,23, -1
357  };
359 
361  const int* examples[] = {
362  &k0[0], &k1[0], &k2[0], &k3[0], &k4[0],
363  &k5[0], &k6[0], &k7[0], &k8[0], &k9[0]
364  };
366  const unsigned int n_examples = sizeof(examples)/sizeof(const int*);
367 
368 
372  class DistinctLinear : public Space {
373  protected:
375  IntVarArray x;
376  public:
378  DistinctLinear(int n, int s) : x(*this,n,1,9) {
379  distinct(*this, x);
380  linear(*this, x, IRT_EQ, s);
381  branch(*this, x, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
382  }
384  DistinctLinear(DistinctLinear& s) : Space(s) {
385  x.update(*this, s.x);
386  }
388  virtual Space*
389  copy(void) {
390  return new DistinctLinear(*this);
391  }
393  IntArgs solution(void) const {
394  IntArgs s(x.size());
395  for (int i=0; i<x.size(); i++)
396  s[i]=x[i].val();
397  return s;
398  }
399  };
400 
404  TupleSet generate(int n, int c) {
405  // Setup search engine that enumerates all solutions
406  DistinctLinear* e = new DistinctLinear(n,c);
408  delete e;
409  TupleSet ts(n);
410  while (DistinctLinear* s = d.next()) {
411  ts.add(s->solution()); delete s;
412  }
413  ts.finalize();
414  return ts;
415  }
416 
420  class Cache {
421  private:
423  class Entry {
424  public:
425  int n;
426  int c;
427  TupleSet ts;
428  Entry* next;
429  };
430  Entry* cache;
431  public:
433  Cache(void) : cache(NULL) {}
435  TupleSet get(int n, int c) {
436  for (Entry* e = cache; e != NULL; e = e->next)
437  if ((e->n == n) && (e->c == c))
438  return e->ts;
439  {
440  Entry* e = new Entry;
441  e->n = n;
442  e->c = c;
443  e->ts = generate(n,c);
444  e->next = cache;
445  cache = e;
446  }
447  return cache->ts;
448  }
450  ~Cache(void) {
451  Entry* e = cache;
452  while (e != NULL) {
453  Entry* d = e;
454  e = e->next;
455  delete d;
456  }
457  }
458  };
459 
460 }
461 
462 
473 class Kakuro : public Script {
474 protected:
475  const int w;
476  const int h;
478 public:
480  enum {
483  };
486  if (x.min() == 0)
487  x = IntVar(*this,1,9);
488  return x;
489  }
491  void distinctlinear(Cache& dc, const IntVarArgs& x, int c,
492  const SizeOptions& opt) {
493  int n=x.size();
494  if (opt.model() == MODEL_DECOMPOSE) {
495  if (n < 8)
496  linear(*this, x, IRT_EQ, c, opt.ipl());
497  else if (n == 8)
498  rel(*this, x, IRT_NQ, 9*(9+1)/2 - c);
499  distinct(*this, x, opt.ipl());
500  } else {
501  switch (n) {
502  case 0:
503  return;
504  case 1:
505  rel(*this, x[0], IRT_EQ, c);
506  return;
507  case 8:
508  // Prune the single missing digit
509  rel(*this, x, IRT_NQ, 9*(9+1)/2 - c);
510  break;
511  case 9:
512  break;
513  default:
514  if (c == n*(n+1)/2) {
515  // sum has unique decomposition: 1 + ... + n
516  rel(*this, x, IRT_LQ, n);
517  } else if (c == n*(n+1)/2 + 1) {
518  // sum has unique decomposition: 1 + ... + n-1 + n+1
519  rel(*this, x, IRT_LQ, n+1);
520  rel(*this, x, IRT_NQ, n);
521  } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2) {
522  // sum has unique decomposition: (9-n+1) + (9-n+2) + ... + 9
523  rel(*this, x, IRT_GQ, 9-n+1);
524  } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2 + 1) {
525  // sum has unique decomposition: (9-n) + (9-n+2) + ... + 9
526  rel(*this, x, IRT_GQ, 9-n);
527  rel(*this, x, IRT_NQ, 9-n+1);
528  } else {
529  extensional(*this, x, dc.get(n,c));
530  return;
531  }
532  }
533  distinct(*this, x, opt.ipl());
534  }
535  }
538  : Script(opt),
539  w(examples[opt.size()][0]), h(examples[opt.size()][1]),
540  f(*this,w*h) {
541  IntVar black(*this,0,0);
542  // Initialize all fields as black (unused). Only if a field
543  // is actually used in a constraint, create a fresh variable
544  // for it (done via init).
545  for (int i=w*h; i--; )
546  f[i] = black;
547 
548  // Cache of already computed tuple sets
549  Cache cache;
550 
551  // Matrix for accessing board fields
552  Matrix<IntVarArray> b(f,w,h);
553  // Access to hints
554  const int* k = &examples[opt.size()][2];
555 
556  // Process vertical hints
557  while (*k >= 0) {
558  int x=*k++; int y=*k++; int n=*k++; int s=*k++;
559  IntVarArgs col(n);
560  for (int i=n; i--; )
561  col[i]=init(b(x,y+i+1));
562  distinctlinear(cache,col,s,opt);
563  }
564  k++;
565 
566  // Process horizontal hints
567  while (*k >= 0) {
568  int x=*k++; int y=*k++; int n=*k++; int s=*k++;
569  IntVarArgs row(n);
570  for (int i=n; i--; )
571  row[i]=init(b(x+i+1,y));
572  distinctlinear(cache,row,s,opt);
573  }
574  branch(*this, f, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
575  }
577  Kakuro(Kakuro& s) : Script(s), w(s.w), h(s.h) {
578  f.update(*this, s.f);
579  }
581  virtual Space*
582  copy(void) {
583  return new Kakuro(*this);
584  }
586  virtual void
587  print(std::ostream& os) const {
588  Matrix<IntVarArray> b(f,w,h);
589  for (int y=0; y<h; y++) {
590  os << '\t';
591  for (int x=0; x<w; x++)
592  if (b(x,y).min() == 0)
593  os << ". ";
594  else
595  os << b(x,y) << ' ';
596  os << std::endl;
597  }
598  }
599 };
600 
601 
605 int
606 main(int argc, char* argv[]) {
607  SizeOptions opt("Kakuro");
610  "decompose","decompose distinct and linear constraints");
612  "combine","combine distinct and linear constraints");
613  opt.ipl(IPL_DOM);
614  opt.parse(argc,argv);
615  if (opt.size() >= n_examples) {
616  std::cerr << "Error: size must be between 0 and "
617  << n_examples-1 << std::endl;
618  return 1;
619  }
620  Script::run<Kakuro,DFS,SizeOptions>(opt);
621  return 0;
622 }
623 
624 // STATISTICS: example-any
virtual Space * copy(void)
Perform copying during cloning.
Definition: kakuro.cpp:582
void size(unsigned int s)
Set default size.
Definition: options.hpp:586
Options for scripts with additional size parameter
Definition: driver.hh:675
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:155
const int h
Height of board.
Definition: kakuro.cpp:476
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1569
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:39
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:908
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:995
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:666
Less or equal ( )
Definition: int.hh:928
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:46
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
Integer variable array.
Definition: int.hh:763
void ipl(IntPropLevel i)
Set default integer propagation level.
Definition: options.hpp:216
Computation spaces.
Definition: core.hpp:1701
Greater or equal ( )
Definition: int.hh:930
Parametric base-class for scripts.
Definition: driver.hh:729
void decay(double d)
Set default decay factor.
Definition: options.hpp:238
Kakuro(const SizeOptions &opt)
The actual problem.
Definition: kakuro.cpp:537
Gecode::IntSet d(v, 7)
int main(int argc, char *argv[])
Main-function.
Definition: kakuro.cpp:606
Gecode::FloatVal c(-8, 8)
IntVarBranch INT_VAR_AFC_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count divided by domain size with decay factor d...
Definition: var.hpp:236
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Equality ( )
Definition: int.hh:926
Options opt
The options.
Definition: test.cpp:97
Gecode::IntArgs i({1, 2, 3, 4})
Combine distinct and linear constraint.
Definition: kakuro.cpp:482
void distinctlinear(Cache &dc, const IntVarArgs &x, int c, const SizeOptions &opt)
Post a distinct-linear constraint on variables x with sum c.
Definition: kakuro.cpp:491
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
unsigned int size(I &i)
Size of all ranges of range iterator i.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:46
IntVarArray f
Variables for fields of board.
Definition: kakuro.cpp:477
Passing integer variables.
Definition: int.hh:656
Passing integer arguments.
Definition: int.hh:628
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Example: Kakuro
Definition: kakuro.cpp:473
Class represeting a set of tuples.
Definition: int.hh:2190
IntVar init(IntVar &x)
Init the variable x if necessary.
Definition: kakuro.cpp:485
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
int min(void) const
Return minimum of domain.
Definition: int.hpp:62
virtual void print(std::ostream &os) const
Print solution.
Definition: kakuro.cpp:587
Integer variables.
Definition: int.hh:371
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
Post propagator for SetVar x
Definition: set.hh:767
Kakuro(Kakuro &s)
Constructor for cloning s.
Definition: kakuro.cpp:577
Matrix-interface for arrays.
Definition: minimodel.hh:2048
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.hpp:142
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition: val.hpp:75
Decompose constraints.
Definition: kakuro.cpp:481
void model(int v)
Set default model value.
Definition: options.hpp:177
Gecode toplevel namespace
TupleSet generate(int n, int c)
Generate tuple set for n distinct variables with sum c.
Definition: kakuro.cpp:404
Disequality ( )
Definition: int.hh:927
const int w
Width of board.
Definition: kakuro.cpp:475
Depth-first search engine.
Definition: search.hh:1036