Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.8.18
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
Post propagator for SetVar x
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition: tuple-set.hpp:142
@ IRT_GQ
Greater or equal ( )
Definition: int.hh:930
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
virtual Space * copy(void)
Perform copying during cloning.
Definition: kakuro.cpp:582
@ MODEL_DECOMPOSE
Decompose constraints.
Definition: kakuro.cpp:481
Passing integer variables.
Definition: int.hh:656
unsigned int size(I &i)
Size of all ranges of range iterator i.
void ipl(IntPropLevel i)
Set default integer propagation level.
Definition: options.hpp:216
IntVar init(IntVar &x)
Init the variable x if necessary.
Definition: kakuro.cpp:485
virtual void print(std::ostream &os) const
Print solution.
Definition: kakuro.cpp:587
Computation spaces.
Definition: core.hpp:1742
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
Depth-first search engine.
Definition: search.hh:1036
Integer variable array.
Definition: int.hh:763
Gecode toplevel namespace
TupleSet generate(int n, int c)
Generate tuple set for n distinct variables with sum c.
Definition: kakuro.cpp:404
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
Options opt
The options.
Definition: test.cpp:97
void finalize(void)
Finalize tuple set.
Definition: tuple-set.hpp:155
int main(int argc, char *argv[])
Main-function.
Definition: kakuro.cpp:606
Kakuro(const SizeOptions &opt)
The actual problem.
Definition: kakuro.cpp:537
Parametric base-class for scripts.
Definition: driver.hh:729
Example: Kakuro
Definition: kakuro.cpp:473
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:548
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Integer variables.
Definition: int.hh:371
Class represeting a set of tuples.
Definition: int.hh:2191
Matrix-interface for arrays.
Definition: minimodel.hh:2087
IntVarArray f
Variables for fields of board.
Definition: kakuro.cpp:477
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Gecode::IntSet d(v, 7)
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:116
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IRT_EQ
Equality ( )
Definition: int.hh:926
const int w
Width of board.
Definition: kakuro.cpp:475
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:46
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition: val.hpp:75
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
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
@ IRT_NQ
Disequality ( )
Definition: int.hh:927
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Gecode::FloatVal c(-8, 8)
void model(int v)
Set default model value.
Definition: options.hpp:177
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
@ MODEL_COMBINE
Combine distinct and linear constraint.
Definition: kakuro.cpp:482
Passing integer arguments.
Definition: int.hh:628
Gecode::IntArgs i({1, 2, 3, 4})
Kakuro(Kakuro &s)
Constructor for cloning s.
Definition: kakuro.cpp:577
const int h
Height of board.
Definition: kakuro.cpp:476
@ IRT_LQ
Less or equal ( )
Definition: int.hh:928
Options for scripts with additional size parameter
Definition: driver.hh:675