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