Generated on for Gecode by doxygen 1.17.0
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.dev>
5 *
6 * Contributing authors:
7 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
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.dev
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
42using namespace Gecode;
43
44namespace {
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 };
358
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 };
365
366 const unsigned int n_examples = sizeof(examples)/sizeof(const int*);
367
368
370 class DistinctLinear : public Space {
371 protected:
373 IntVarArray x;
374 public:
376 DistinctLinear(int n, int s) : x(*this,n,1,9) {
377 distinct(*this, x);
378 linear(*this, x, IRT_EQ, s);
379 branch(*this, x, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
380 }
382 DistinctLinear(DistinctLinear& s) : Space(s) {
383 x.update(*this, s.x);
384 }
386 virtual Space*
387 copy(void) {
388 return new DistinctLinear(*this);
389 }
391 IntArgs solution(void) const {
392 IntArgs s(x.size());
393 for (int i=0; i<x.size(); i++)
394 s[i]=x[i].val();
395 return s;
396 }
397 };
398
400 TupleSet generate(int n, int c) {
401 // Setup search engine that enumerates all solutions
402 DistinctLinear* e = new DistinctLinear(n,c);
403 DFS<DistinctLinear> d(e);
404 delete e;
405 TupleSet ts(n);
406 while (DistinctLinear* s = d.next()) {
407 ts.add(s->solution()); delete s;
408 }
409 ts.finalize(EPK_AUTO);
410 return ts;
411 }
412
414 class Cache {
415 private:
417 class Entry {
418 public:
419 int n;
420 int c;
421 TupleSet ts;
422 Entry* next;
423 };
424 Entry* cache;
425 public:
427 Cache(void) : cache(nullptr) {}
429 TupleSet get(int n, int c) {
430 for (Entry* e = cache; e != nullptr; e = e->next)
431 if ((e->n == n) && (e->c == c))
432 return e->ts;
433 {
434 Entry* e = new Entry;
435 e->n = n;
436 e->c = c;
437 e->ts = generate(n,c);
438 e->next = cache;
439 cache = e;
440 }
441 return cache->ts;
442 }
444 ~Cache(void) {
445 Entry* e = cache;
446 while (e != nullptr) {
447 Entry* d = e;
448 e = e->next;
449 delete d;
450 }
451 }
452 };
453
454}
455
456
467class Kakuro : public Script {
468protected:
469 const int w;
470 const int h;
471 IntVarArray f;
472public:
474 enum {
475 MODEL_DECOMPOSE,
476 MODEL_COMBINE,
477 };
479 IntVar init(IntVar& x) {
480 if (x.min() == 0)
481 x = IntVar(*this,1,9);
482 return x;
483 }
484
485 void distinctlinear(Cache& dc, const IntVarArgs& x, int c,
486 const SizeOptions& opt) {
487 int n=x.size();
488 if (opt.model() == MODEL_DECOMPOSE) {
489 if (n < 8)
490 linear(*this, x, IRT_EQ, c, opt.ipl());
491 else if (n == 8)
492 rel(*this, x, IRT_NQ, 9*(9+1)/2 - c);
493 distinct(*this, x, opt.ipl());
494 } else {
495 switch (n) {
496 case 0:
497 return;
498 case 1:
499 rel(*this, x[0], IRT_EQ, c);
500 return;
501 case 8:
502 // Prune the single missing digit
503 rel(*this, x, IRT_NQ, 9*(9+1)/2 - c);
504 break;
505 case 9:
506 break;
507 default:
508 if (c == n*(n+1)/2) {
509 // sum has unique decomposition: 1 + ... + n
510 rel(*this, x, IRT_LQ, n);
511 } else if (c == n*(n+1)/2 + 1) {
512 // sum has unique decomposition: 1 + ... + n-1 + n+1
513 rel(*this, x, IRT_LQ, n+1);
514 rel(*this, x, IRT_NQ, n);
515 } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2) {
516 // sum has unique decomposition: (9-n+1) + (9-n+2) + ... + 9
517 rel(*this, x, IRT_GQ, 9-n+1);
518 } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2 + 1) {
519 // sum has unique decomposition: (9-n) + (9-n+2) + ... + 9
520 rel(*this, x, IRT_GQ, 9-n);
521 rel(*this, x, IRT_NQ, 9-n+1);
522 } else {
523 extensional(*this, x, dc.get(n,c));
524 return;
525 }
526 }
527 distinct(*this, x, opt.ipl());
528 }
529 }
530
531 Kakuro(const SizeOptions& opt)
532 : Script(opt),
533 w(examples[opt.size()][0]), h(examples[opt.size()][1]),
534 f(*this,w*h) {
535 IntVar black(*this,0,0);
536 // Initialize all fields as black (unused). Only if a field
537 // is actually used in a constraint, create a fresh variable
538 // for it (done via init).
539 for (int i=w*h; i--; )
540 f[i] = black;
541
542 // Cache of already computed tuple sets
543 Cache cache;
544
545 // Matrix for accessing board fields
546 Matrix<IntVarArray> b(f,w,h);
547 // Access to hints
548 const int* k = &examples[opt.size()][2];
549
550 // Process vertical hints
551 while (*k >= 0) {
552 int x=*k++; int y=*k++; int n=*k++; int s=*k++;
553 IntVarArgs col(n);
554 for (int i=n; i--; )
555 col[i]=init(b(x,y+i+1));
556 distinctlinear(cache,col,s,opt);
557 }
558 k++;
559
560 // Process horizontal hints
561 while (*k >= 0) {
562 int x=*k++; int y=*k++; int n=*k++; int s=*k++;
563 IntVarArgs row(n);
564 for (int i=n; i--; )
565 row[i]=init(b(x+i+1,y));
566 distinctlinear(cache,row,s,opt);
567 }
568 branch(*this, f, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
569 }
570
571 Kakuro(Kakuro& s) : Script(s), w(s.w), h(s.h) {
572 f.update(*this, s.f);
573 }
574
575 virtual Space*
576 copy(void) {
577 return new Kakuro(*this);
578 }
579
580 virtual void
581 print(std::ostream& os) const {
582 Matrix<IntVarArray> b(f,w,h);
583 for (int y=0; y<h; y++) {
584 os << '\t';
585 for (int x=0; x<w; x++)
586 if (b(x,y).min() == 0)
587 os << ". ";
588 else
589 os << b(x,y) << ' ';
590 os << std::endl;
591 }
592 }
593};
594
595
599int
600main(int argc, char* argv[]) {
601 SizeOptions opt("Kakuro");
602 opt.model(Kakuro::MODEL_COMBINE);
603 opt.model(Kakuro::MODEL_DECOMPOSE,
604 "decompose","decompose distinct and linear constraints");
605 opt.model(Kakuro::MODEL_COMBINE,
606 "combine","combine distinct and linear constraints");
607 opt.ipl(IPL_DOM);
608 opt.parse(argc,argv);
609 if (opt.size() >= n_examples) {
610 std::cerr << "Error: size must be between 0 and "
611 << n_examples-1 << std::endl;
612 return 1;
613 }
614 Script::run<Kakuro,DFS,SizeOptions>(opt);
615 return 0;
616}
617
618// STATISTICS: example-any
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1597
Gecode::DFS
Depth-first search engine.
Definition search.hh:1080
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >::run
static void run(const Options &opt, Script *s=nullptr)
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:652
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:680
Gecode::IntVarArray
Integer variable array.
Definition int.hh:791
Gecode::IntVar
Integer variables.
Definition int.hh:389
Gecode::IntVar::min
int min(void) const
Return minimum of domain.
Definition int.hpp:62
Gecode::Matrix
Matrix-interface for arrays.
Definition minimodel.hh:2208
Gecode::Search::Base::next
virtual T * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition base.hpp:46
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:723
Gecode::Space
Computation spaces.
Definition core.hpp:1775
Gecode::TupleSet
Class representing a set of tuples.
Definition int.hh:2382
Gecode::TupleSet::add
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition tuple-set.hpp:164
Gecode::TupleSet::finalize
void finalize(void)
Finalize tuple set with dense support data.
Definition tuple-set.hpp:177
Gecode::VarArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:936
Gecode::VarArray::update
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1023
Kakuro::init
IntVar init(IntVar &x)
Init the variable x if necessary.
Definition kakuro.cpp:479
Kakuro::k5
const int k5[]
Array of all examples.
Definition kakuro.cpp:182
Kakuro::main
int main(int argc, char *argv[])
Main-function.
Definition kakuro.cpp:600
Kakuro::n_examples
const unsigned int n_examples
Number of examples.
Definition kakuro.cpp:366
Kakuro::k3
const int k3[]
Array of all examples.
Definition kakuro.cpp:130
Kakuro::w
const int w
Width of board.
Definition kakuro.cpp:469
Kakuro::f
IntVarArray f
Variables for fields of board.
Definition kakuro.cpp:471
Kakuro::k9
const int k9[]
Array of all examples.
Definition kakuro.cpp:325
Kakuro::distinctlinear
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:485
Kakuro::Kakuro
Kakuro(Kakuro &s)
Constructor for cloning s.
Definition kakuro.cpp:571
Kakuro::copy
virtual Space * copy(void)
Perform copying during cloning.
Definition kakuro.cpp:576
Kakuro::k2
const int k2[]
Array of all examples.
Definition kakuro.cpp:110
Kakuro::print
virtual void print(std::ostream &os) const
Print solution.
Definition kakuro.cpp:581
Kakuro::Kakuro
Kakuro(const SizeOptions &opt)
The actual problem.
Definition kakuro.cpp:531
Kakuro::examples
const int * examples[]
Array of all examples.
Definition kakuro.cpp:361
Kakuro::k8
const int k8[]
Array of all examples.
Definition kakuro.cpp:286
Kakuro::k7
const int k7[]
Array of all examples.
Definition kakuro.cpp:249
Kakuro::h
const int h
Height of board.
Definition kakuro.cpp:470
Kakuro::k6
const int k6[]
Array of all examples.
Definition kakuro.cpp:216
Kakuro::k0
const int k0[]
Array of all examples.
Definition kakuro.cpp:68
Kakuro::generate
TupleSet generate(int n, int c)
Generate tuple set for n distinct variables with sum c.
Definition kakuro.cpp:400
Kakuro::k4
const int k4[]
Array of all examples.
Definition kakuro.cpp:150
Kakuro::k1
const int k1[]
Array of all examples.
Definition kakuro.cpp:89
Kakuro::MODEL_COMBINE
@ MODEL_COMBINE
Combine distinct and linear constraint.
Definition kakuro.cpp:476
Kakuro::MODEL_DECOMPOSE
@ MODEL_DECOMPOSE
Decompose constraints.
Definition kakuro.cpp:475
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Gecode::Script
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:849
Gecode::branch
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Gecode::linear
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Gecode::extensional
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:960
Gecode::IRT_NQ
@ IRT_NQ
Disequality ( ).
Definition int.hh:961
Gecode::IRT_GQ
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:964
Gecode::IRT_LQ
@ IRT_LQ
Less or equal ( ).
Definition int.hh:962
Gecode::IPL_DOM
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:1013
Gecode
Gecode toplevel namespace
Gecode::INT_VAL_SPLIT_MIN
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition val.hpp:75
Gecode::INT_VAR_AFC_SIZE_MAX
IntVarBranch INT_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
Definition var.hpp:236
Gecode::distinct
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Gecode::INT_VAR_NONE
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96