this repo has no description
dekker.one
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
46 /** \name %Kakuro specifications
47 *
48 * Each specification starts with two integers for width and height,
49 * followed by entries for vertical constraints, an integer -1
50 * (signalling the end of the vertical constraints), entries
51 * for the horizontal constraints, and, finally, an integer -1.
52 *
53 * Each entry consists of four integers:
54 * - the x-coordinate of the hint
55 * - the y-coordinate of the hint
56 * - the number of fields in the respective direction
57 * - the sum of the fields
58 *
59 * The example are taken from the website of Nikoli (from the free
60 * section). Thanks to Nikoli for their great puzzles and their
61 * brilliant website: www.nikoli.com.
62 *
63 * \relates Kakuro
64 */
65 //@{
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
360 /// Array of all examples
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 /// Number of examples
366 const unsigned int n_examples = sizeof(examples)/sizeof(const int*);
367
368
369 /** \brief Class for solutions of a distinct-linear constraint problem.
370 * \relates Kakuro
371 */
372 class DistinctLinear : public Space {
373 protected:
374 /// The variables
375 IntVarArray x;
376 public:
377 /// The actual problem
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 }
383 /// Constructor for cloning \a s
384 DistinctLinear(DistinctLinear& s) : Space(s) {
385 x.update(*this, s.x);
386 }
387 /// Perform copying during cloning
388 virtual Space*
389 copy(void) {
390 return new DistinctLinear(*this);
391 }
392 /// Return a solution
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
401 /** \brief Generate tuple set for \a n distinct variables with sum \a c
402 * \relates Kakuro
403 */
404 TupleSet generate(int n, int c) {
405 // Setup search engine that enumerates all solutions
406 DistinctLinear* e = new DistinctLinear(n,c);
407 DFS<DistinctLinear> d(e);
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
417 /** \brief Class to remember already computed specifications
418 * \relates Kakuro
419 */
420 class Cache {
421 private:
422 /// Cache entry
423 class Entry {
424 public:
425 int n; ///< Number of variables
426 int c; ///< Sum of variables
427 TupleSet ts; ///< The previously computed tuple set
428 Entry* next; ///< The next cache entry
429 };
430 Entry* cache; ///< Where all entries start
431 public:
432 /// Initialize cache as empty
433 Cache(void) : cache(nullptr) {}
434 /// Return possibly cached Data for \a n distinct variables with sum \a c
435 TupleSet get(int n, int c) {
436 for (Entry* e = cache; e != nullptr; 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 }
449 /// Delete cache entries
450 ~Cache(void) {
451 Entry* e = cache;
452 while (e != nullptr) {
453 Entry* d = e;
454 e = e->next;
455 delete d;
456 }
457 }
458 };
459
460}
461
462
463/**
464 * \brief %Example: %Kakuro
465 *
466 * Another puzzle in the style of Sudoku.
467 *
468 * Note that "Modeling and Programming with Gecode" uses this example
469 * as a case study.
470 *
471 * \ingroup Example
472 */
473class Kakuro : public Script {
474protected:
475 const int w; ///< Width of board
476 const int h; ///< Height of board
477 IntVarArray f; ///< Variables for fields of board
478public:
479 /// Model variants
480 enum {
481 MODEL_DECOMPOSE,///< Decompose constraints
482 MODEL_COMBINE, ///< Combine distinct and linear constraint
483 };
484 /// Init the variable \a x if necessary
485 IntVar init(IntVar& x) {
486 if (x.min() == 0)
487 x = IntVar(*this,1,9);
488 return x;
489 }
490 /// Post a distinct-linear constraint on variables \a x with sum \a c
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 }
536 /// The actual problem
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
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 }
576 /// Constructor for cloning \a s
577 Kakuro(Kakuro& s) : Script(s), w(s.w), h(s.h) {
578 f.update(*this, s.f);
579 }
580 /// Perform copying during cloning
581 virtual Space*
582 copy(void) {
583 return new Kakuro(*this);
584 }
585 /// Print solution
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
602/** \brief Main-function
603 * \relates Kakuro
604 */
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 }
620 Script::run<Kakuro,DFS,SizeOptions>(opt);
621 return 0;
622}
623
624// STATISTICS: example-any