Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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.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
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 };
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:
376 public:
378 DistinctLinear(int n, int s) : x(*this,n,1,9) {
379 distinct(*this, x);
380 linear(*this, x, IRT_EQ, s);
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
473class Kakuro : public Script {
474protected:
475 const int w;
476 const int h;
478public:
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 }
537 Kakuro(const SizeOptions& opt)
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
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 {
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
605int
606main(int argc, char* argv[]) {
607 SizeOptions opt("Kakuro");
608 opt.model(Kakuro::MODEL_COMBINE);
609 opt.model(Kakuro::MODEL_DECOMPOSE,
610 "decompose","decompose distinct and linear constraints");
611 opt.model(Kakuro::MODEL_COMBINE,
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 }
621 return 0;
622}
623
624// STATISTICS: example-any
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int n
Number of negative literals for node type.
Node * x
Pointer to corresponding Boolean expression node.
Depth-first search engine.
Definition search.hh:1036
Parametric base-class for scripts.
Definition driver.hh:729
static void run(const Options &opt, Script *s=NULL)
Definition script.hpp:290
Passing integer arguments.
Definition int.hh:628
Passing integer variables.
Definition int.hh:656
Integer variable array.
Definition int.hh:763
Integer variables.
Definition int.hh:371
Matrix-interface for arrays.
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1742
Class represeting a set of tuples.
Definition int.hh:2191
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
void finalize(void)
Finalize tuple set.
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1013
Example: Kakuro
Definition kakuro.cpp:473
IntVar init(IntVar &x)
Init the variable x if necessary.
Definition kakuro.cpp:485
int main(int argc, char *argv[])
Main-function.
Definition kakuro.cpp:606
const int w
Width of board.
Definition kakuro.cpp:475
IntVarArray f
Variables for fields of board.
Definition kakuro.cpp:477
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
Kakuro(Kakuro &s)
Constructor for cloning s.
Definition kakuro.cpp:577
virtual Space * copy(void)
Perform copying during cloning.
Definition kakuro.cpp:582
virtual void print(std::ostream &os) const
Print solution.
Definition kakuro.cpp:587
Kakuro(const SizeOptions &opt)
The actual problem.
Definition kakuro.cpp:537
const int * examples[]
Array of all examples.
Definition kakuro.cpp:361
const int h
Height of board.
Definition kakuro.cpp:476
@ MODEL_COMBINE
Combine distinct and linear constraint.
Definition kakuro.cpp:482
@ MODEL_DECOMPOSE
Decompose constraints.
Definition kakuro.cpp:481
TupleSet generate(int n, int c)
Generate tuple set for n distinct variables with sum c.
Definition kakuro.cpp:404
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
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.
Definition branch.cpp:39
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, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IRT_EQ
Equality ( )
Definition int.hh:926
@ IRT_NQ
Disequality ( )
Definition int.hh:927
@ IRT_GQ
Greater or equal ( )
Definition int.hh:930
@ IRT_LQ
Less or equal ( )
Definition int.hh:928
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
Gecode toplevel namespace
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=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
Definition var.hpp:236
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
Post propagator for SetVar x
Definition set.hh:767
Gecode::FloatVal c(-8, 8)
Gecode::IntSet d(v, 7)