Generated on for Gecode by doxygen 1.17.0
nonogram.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2005
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36#include <gecode/minimodel.hh>
37
38
39using namespace Gecode;
40
41namespace {
42
44 extern const int* specs[];
46 extern const unsigned int n_examples;
47
48}
49
67class Nonogram : public Script {
68protected:
70 const int* spec;
72 BoolVarArray b;
73
75 int width(void) const {
76 return spec[0];
77 }
78
79 int height(void) const {
80 return spec[1];
81 }
82
84 DFA line(int& spos) {
85 REG r0(0), r1(1);
86 REG border = *r0;
87 REG between = +r0;
88 int hints = spec[spos++];
89 REG r = border;
90 if (hints > 0) {
91 r += r1(spec[spos],spec[spos]);
92 spos++;
93 for (int i=hints-1; i--; spos++)
94 r += between + r1(spec[spos],spec[spos]);
95 }
96 return r + border;
97 }
98
99public:
100 // Branching variants
101 enum {
102 BRANCH_NONE,
103 BRANCH_AFC,
104 };
105
107 Nonogram(const SizeOptions& opt)
108 : Script(opt), spec(specs[opt.size()]), b(*this,width()*height(),0,1) {
109 Matrix<BoolVarArray> m(b, width(), height());
110
111 {
112 int spos = 2;
113 // Post constraints for columns
114 for (int w=0; w<width(); w++)
115 extensional(*this, m.col(w), line(spos));
116 // Post constraints for rows
117 for (int h=0; h<height(); h++)
118 extensional(*this, m.row(h), line(spos));
119 }
120
121
122
123 switch (opt.branching()) {
124 case BRANCH_NONE:
125 {
126 /*
127 * The following branches either by columns or rows, depending on
128 * whether there are more hints relative to the height or width
129 * for columns or rows.
130 *
131 * This idea is due to Pascal Van Hentenryck and has been suggested
132 * to us by Hakan Kjellerstrand.
133 */
134
135 // Number of hints for columns
136 int cols = 0;
137 // Number of hints for rows
138 int rows = 0;
139 int spos = 2;
140 for (int w=0; w<width(); w++) {
141 int hint = spec[spos++];
142 cols += hint; spos += hint;
143 }
144 for (int h=0; h<height(); h++) {
145 int hint = spec[spos++];
146 rows += hint; spos += hint;
147 }
148
149 if (rows*width() > cols*height()) {
150 for (int w=0; w<width(); w++)
151 branch(*this, m.col(w), BOOL_VAR_NONE(), BOOL_VAL_MAX());
152 } else {
153 for (int h=0; h<height(); h++)
154 branch(*this, m.row(h), BOOL_VAR_NONE(), BOOL_VAL_MAX());
155 }
156 }
157 break;
158 case BRANCH_AFC:
159 /*
160 * The following just uses the AFC for branching. This is
161 * equivalent to SIZE/AFC in this case since the variables are
162 * binary.
163 */
164 branch(*this, b, BOOL_VAR_AFC_MAX(opt.decay()), BOOL_VAL_MAX());
165 break;
166 }
167 }
168
170 Nonogram(Nonogram& s) : Script(s), spec(s.spec) {
171 b.update(*this, s.b);
172 }
173
175 virtual Space*
176 copy(void) {
177 return new Nonogram(*this);
178 }
179
181 virtual void
182 print(std::ostream& os) const {
183 Matrix<BoolVarArray> m(b, width(), height());
184 for (int h = 0; h < height(); ++h) {
185 os << '\t';
186 for (int w = 0; w < width(); ++w)
187 os << ((m(w,h).val() == 1) ? '#' : ' ');
188 os << std::endl;
189 }
190 os << std::endl;
191 }
192};
193
194
198int
199main(int argc, char* argv[]) {
200 SizeOptions opt("Nonogram");
201 opt.size(8);
202 opt.branching(Nonogram::BRANCH_AFC);
203 opt.branching(Nonogram::BRANCH_NONE, "none",
204 "Branch on rows/columns in order");
205 opt.branching(Nonogram::BRANCH_AFC, "afc",
206 "Use AFC for branching");
207 opt.parse(argc,argv);
208 if (opt.size() >= n_examples) {
209 std::cerr << "Error: size must be between 0 and "
210 << n_examples-1 << std::endl;
211 return 1;
212 }
213 Script::run<Nonogram,DFS,SizeOptions>(opt);
214 return 0;
215}
216
217namespace {
218
230
231const int heart[] =
232 { 9, 9,
233 // Column constraints.
234 1, 3,
235 2, 2, 3,
236 2, 2, 2,
237 2, 2, 2,
238 2, 2, 2,
239 2, 2, 2,
240 2, 2, 2,
241 2, 2, 3,
242 1, 3,
243 // Row constraints
244 2, 2, 2,
245 2, 4, 4,
246 3, 1, 3, 1,
247 3, 2, 1, 2,
248 2, 1, 1,
249 2, 2, 2,
250 2, 2, 2,
251 1, 3,
252 1, 1
253 };
254
256const int bear[] =
257 { 13, 8,
258 // Column constraints
259 1, 2,
260 2, 2, 1,
261 2, 3, 2,
262 1, 6,
263 2, 1, 4,
264 1, 3,
265 1, 4,
266 1, 4,
267 1, 4,
268 1, 5,
269 1, 4,
270 2, 1, 3,
271 1, 2,
272 // Row constraints
273 1, 1,
274 1, 2,
275 2, 4, 4,
276 1, 12,
277 1, 8,
278 1, 9,
279 2, 3, 4,
280 2, 2, 2
281 };
282
284const int crocodile[] =
285 { 15, 9,
286 // Column constraints
287 1, 3,
288 1, 4,
289 2, 2, 2,
290 2, 3, 1,
291 2, 2, 3,
292 2, 3, 2,
293 2, 2, 3,
294 2, 4, 2,
295 2, 3, 2,
296 1, 6,
297 2, 1, 3,
298 2, 1, 3,
299 2, 1, 4,
300 1, 5,
301 1, 5,
302 // Row constraints
303 1, 3,
304 3, 2, 3, 2,
305 2, 10, 3,
306 1, 15,
307 5, 1, 1, 1, 1, 6,
308 2, 1, 7,
309 2, 1, 4,
310 2, 1, 4,
311 1, 4
312 };
313
315const int unknown[] =
316 { 10, 10,
317 // Column constraints
318 1, 3,
319 2, 2, 1,
320 2, 2, 2,
321 2, 2, 1,
322 3, 1, 2, 1,
323 2, 1, 1,
324 3, 1, 4, 1,
325 3, 1, 1, 2,
326 2, 3, 1,
327 1, 4,
328 // Row constraints
329 1, 3,
330 2, 2, 1,
331 2, 1, 1,
332 2, 1, 4,
333 4, 1, 1, 1, 1,
334 4, 2, 1, 1, 1,
335 3, 2, 1, 1,
336 2, 1, 2,
337 2, 2, 3,
338 1, 3
339 };
340
342const int pinwheel[] =
343 { 6, 6,
344 // Column constraints
345 2, 1, 2,
346 1, 1,
347 1, 2,
348 1, 2,
349 1, 1,
350 2, 2, 1,
351 // Row constraints
352 2, 2, 1,
353 1, 1,
354 1, 2,
355 1, 2,
356 1, 1,
357 2, 1, 2
358 };
359
361const int difficult[] =
362 { 15, 15,
363 // Column constraints
364 1, 3,
365 1, 2,
366 1, 2,
367 1, 1,
368 1, 2,
369 1, 3,
370 1, 2,
371 1, 4,
372 1, 3,
373 1, 4,
374 2, 2, 1,
375 2, 1, 1,
376 2, 1, 1,
377 2, 1, 1,
378 1, 3,
379 // Row constraints
380 1, 3,
381 2, 1, 1,
382 2, 1, 1,
383 2, 1, 1,
384 2, 1, 2,
385 1, 5,
386 1, 1,
387 1, 2,
388 1, 1,
389 1, 1,
390 2, 1, 2,
391 2, 1, 2,
392 2, 2, 1,
393 2, 2, 2,
394 1, 3
395 };
396
398const int non_unique[] =
399 { 11, 15,
400 // Column constraints
401 1, 5,
402 3, 1, 2, 4,
403 3, 2, 1, 3,
404 4, 2, 2, 1, 1,
405 4, 1, 1, 1, 1,
406 2, 1, 5,
407 5, 2, 1, 1, 3, 2,
408 5, 2, 1, 1, 1, 1,
409 3, 1, 4, 1,
410 2, 1, 1,
411 1, 1,
412 // Row constraints
413 2, 2, 2,
414 2, 2, 2,
415 1, 4,
416 2, 1, 1,
417 2, 1, 1,
418 4, 1, 1, 1, 1,
419 2, 1, 1,
420 2, 1, 4,
421 3, 1, 1, 1,
422 3, 1, 1, 4,
423 2, 1, 3,
424 2, 1, 2,
425 1, 5,
426 2, 2, 2,
427 2, 3, 3
428 };
429
435 const int dragonfly[] =
436 { 20, 20,
437 // Column constraints.
438 4, 1, 1, 1, 2,
439 5, 3, 1, 2, 1, 1,
440 5, 1, 4, 2, 1, 1,
441 4, 1, 3, 2, 4,
442 4, 1, 4, 6, 1,
443 3, 1, 11, 1,
444 4, 5, 1, 6, 2,
445 1, 14,
446 2, 7, 2,
447 2, 7, 2,
448 3, 6, 1, 1,
449 2, 9, 2,
450 4, 3, 1, 1, 1,
451 3, 3, 1, 3,
452 3, 2, 1, 3,
453 3, 2, 1, 5,
454 3, 3, 2, 2,
455 3, 3, 3, 2,
456 3, 2, 3, 2,
457 2, 2, 6,
458 // Row constraints
459 2, 7, 1,
460 3, 1, 1, 2,
461 3, 2, 1, 2,
462 3, 1, 2, 2,
463 3, 4, 2, 3,
464 3, 3, 1, 4,
465 3, 3, 1, 3,
466 3, 2, 1, 4,
467 2, 2, 9,
468 3, 2, 1, 5,
469 2, 2, 7,
470 1, 14,
471 2, 8, 2,
472 3, 6, 2, 2,
473 4, 2, 8, 1, 3,
474 4, 1, 5, 5, 2,
475 5, 1, 3, 2, 4, 1,
476 5, 3, 1, 2, 4, 1,
477 5, 1, 1, 3, 1, 3,
478 4, 2, 1, 1, 2
479 };
480
482 const int castle[] = {
483 60, 35,
484 // Column constraints
485 7, 2,3,1,5,1,7,1,
486 7, 2,4,2,3,2,3,5,
487 8, 2,6,3,1,1,5,1,5,
488 10, 2,4,2,1,1,1,4,1,1,2,
489 7, 2,8,2,1,5,2,5,
490 7, 3,1,6,2,5,1,5,
491 9, 3,3,3,1,1,6,1,1,1,
492 9, 3,2,2,2,2,8,1,1,3,
493 7, 1,4,4,3,7,1,1,
494 7, 1,2,2,2,3,7,9,
495 8, 1,2,3,1,1,5,2,2,
496 7, 2,2,3,1,1,6,1,
497 6, 1,3,1,5,4,1,
498 8, 1,3,1,1,6,1,3,1,
499 8, 3,3,4,5,1,4,2,1,
500 6, 2,3,3,9,7,1,
501 8, 2,3,2,2,1,1,3,5,
502 8, 4,2,1,1,1,1,2,3,
503 7, 4,2,2,1,4,3,2,
504 4, 4,3,16,2,
505 5, 1,2,5,7,1,
506 6, 4,3,2,2,7,1,
507 5, 2,3,1,10,1,
508 6, 2,4,2,1,4,1,
509 5, 1,6,7,3,1,
510 4, 3,11,3,1,
511 5, 7,1,11,2,1,
512 7, 2,2,2,2,2,2,2,
513 7, 3,1,1,1,1,2,1,
514 7, 2,2,2,2,1,1,1,
515 7, 1,1,1,1,2,1,2,
516 8, 2,2,2,2,1,1,1,1,
517 5, 4,1,1,2,2,
518 5, 5,2,17,2,1,
519 6, 9,2,3,1,4,2,
520 6, 9,4,2,1,1,1,
521 5, 5,4,2,1,4,
522 7, 11,1,2,1,4,1,2,
523 5, 3,4,2,4,4,
524 8, 2,1,4,1,2,1,5,2,
525 5, 8,4,1,1,2,
526 5, 1,1,3,2,3,
527 6, 1,3,1,8,1,6,
528 4, 2,1,7,14,
529 7, 1,2,4,4,1,2,3,
530 10, 1,1,4,2,1,1,1,1,1,4,
531 6, 3,5,3,1,1,4,
532 6, 2,4,2,2,1,2,
533 5, 4,2,3,8,4,
534 5, 4,15,2,2,4,
535 6, 4,1,10,2,1,2,
536 6, 2,12,6,1,2,4,
537 7, 3,1,3,1,3,3,4,
538 6, 3,1,2,3,4,1,
539 7, 5,2,2,2,3,3,3,
540 9, 1,2,2,2,2,4,1,1,3,
541 7, 2,1,4,2,7,1,1,
542 6, 5,2,2,3,6,3,
543 7, 3,3,2,2,3,2,3,
544 7, 4,1,2,1,1,2,1,
545
546 // Row constraints
547 4, 12,1,1,1,
548 5, 8,6,3,1,3,
549 6, 5,8,4,3,1,5,
550 8, 7,3,4,1,3,5,1,7,
551 13, 2,2,4,9,1,5,1,1,1,1,1,1,1,
552 8, 4,5,10,2,1,8,7,1,
553 7, 5,1,3,3,16,1,2,
554 8, 8,5,1,2,4,9,1,3,
555 12, 4,5,3,14,1,1,1,1,4,1,1,3,
556 19, 3,3,2,2,2,4,1,1,1,1,1,1,1,1,3,1,1,3,2,
557 11, 8,2,7,2,1,1,2,1,1,3,3,
558 13, 1,5,9,12,2,1,1,3,1,1,2,2,1,
559 17, 3,2,2,1,1,1,1,4,1,1,1,3,3,1,1,2,2,
560 12, 5,2,2,2,2,1,5,2,1,1,2,5,
561 12, 3,5,9,2,1,1,6,3,1,3,2,3,
562 12, 1,4,1,1,1,4,1,5,5,3,3,3,
563 10, 4,1,1,1,1,3,4,6,6,3,
564 12, 3,1,3,1,1,3,3,1,1,4,6,1,
565 11, 3,1,5,1,1,3,1,1,9,4,1,
566 14, 2,1,1,7,1,4,1,1,1,1,1,1,3,5,
567 11, 9,2,1,3,1,1,1,1,4,2,1,
568 10, 1,14,1,1,2,2,2,10,1,2,
569 10, 1,9,2,1,2,6,1,5,3,2,
570 12, 1,9,9,1,2,2,3,1,1,4,3,1,
571 10, 10,1,3,4,1,3,2,1,2,8,
572 9, 9,1,3,5,1,1,1,2,7,
573 12, 4,5,1,2,5,1,3,1,1,2,1,3,
574 14, 1,1,1,1,2,6,2,3,2,1,1,2,3,1,
575 11, 1,6,1,5,7,1,3,3,2,4,3,
576 10, 1,2,1,2,9,1,5,2,6,2,
577 8, 10,2,2,13,1,3,3,1,
578 11, 2,2,1,6,2,3,3,2,2,2,1,
579 12, 2,2,1,1,12,2,2,9,2,2,2,2,
580 9, 5,1,2,4,1,5,11,2,2,
581 3, 15,6,18,
582 };
583
589 const int p200[] =
590 { 25, 25,
591 // Column constraints
592 4, 1,1,2,2,
593 3, 5,5,7,
594 4, 5,2,2,9,
595 4, 3,2,3,9,
596 5, 1,1,3,2,7,
597 3, 3,1,5,
598 5, 7,1,1,1,3,
599 6, 1,2,1,1,2,1,
600 3, 4,2,4,
601 4, 1,2,2,2,
602 3, 4,6,2,
603 4, 1,2,2,1,
604 4, 3,3,2,1,
605 3, 4,1,15,
606 6, 1,1,1,3,1,1,
607 6, 2,1,1,2,2,3,
608 4, 1,4,4,1,
609 4, 1,4,3,2,
610 4, 1,1,2,2,
611 5, 7,2,3,1,1,
612 5, 2,1,1,1,5,
613 3, 1,2,5,
614 4, 1,1,1,3,
615 3, 4,2,1,
616 1, 3,
617 // Row constraints
618 3, 2,2,3,
619 5, 4,1,1,1,4,
620 5, 4,1,2,1,1,
621 7, 4,1,1,1,1,1,1,
622 6, 2,1,1,2,3,5,
623 6, 1,1,1,1,2,1,
624 5, 3,1,5,1,2,
625 6, 3,2,2,1,2,2,
626 7, 2,1,4,1,1,1,1,
627 6, 2,2,1,2,1,2,
628 6, 1,1,1,3,2,3,
629 5, 1,1,2,7,3,
630 5, 1,2,2,1,5,
631 5, 3,2,2,1,2,
632 4, 3,2,1,2,
633 3, 5,1,2,
634 4, 2,2,1,2,
635 4, 4,2,1,2,
636 4, 6,2,3,2,
637 4, 7,4,3,2,
638 3, 7,4,4,
639 3, 7,1,4,
640 3, 6,1,4,
641 3, 4,2,2,
642 2, 2,1
643 };
644
645 // The following instances are from the http://webpbn.com site and
646 // are all designed by Jan Wolter.
647 // See also the survey at http://webpbn.com/survey/
648
650 const int webpbn436[]=
651 { 40, 35,
652 // Column constraints
653 1, 1,
654 2, 3, 2,
655 3, 2, 3, 3,
656 3, 3, 3, 3,
657 4, 3, 3, 3, 3,
658 4, 4, 2, 2, 2,
659 4, 3, 3, 2, 3,
660 4, 3, 2, 2, 2,
661 3, 3, 2, 6,
662 2, 2, 9,
663 3, 2, 3, 3,
664 5, 4, 4, 3, 2, 4,
665 5, 7, 2, 5, 2, 6,
666 6, 12, 2, 3, 2, 3, 2,
667 6, 3, 1, 2, 2, 2, 3,
668 6, 2, 2, 3, 2, 2, 2,
669 6, 6, 2, 6, 2, 2, 2,
670 5, 12, 4, 3, 2, 2,
671 4, 12, 2, 2, 2,
672 3, 2, 6, 2,
673 4, 2, 6, 5, 2,
674 4, 10, 9, 2, 2,
675 5, 12, 3, 3, 2, 2,
676 7, 6, 2, 2, 2, 2, 2, 2,
677 6, 2, 2, 3, 2, 2, 2,
678 6, 4, 3, 2, 2, 2, 3,
679 6, 7, 3, 3, 2, 3, 2,
680 5, 5, 3, 5, 2, 6,
681 5, 4, 3, 3, 3, 4,
682 3, 3, 5, 3,
683 2, 3, 9,
684 3, 4, 2, 6,
685 4, 4, 2, 2, 2,
686 4, 4, 2, 2, 3,
687 4, 3, 2, 2, 3,
688 3, 3, 3, 3,
689 3, 3, 3, 3,
690 3, 4, 3, 3,
691 3, 2, 3, 3,
692 2, 2, 1,
693 // Row constraints
694 2, 2, 2,
695 3, 2, 3, 2,
696 4, 3, 3, 3, 2,
697 4, 3, 3, 3, 3,
698 6, 2, 3, 3, 3, 3, 2,
699 6, 3, 3, 3, 3, 3, 3,
700 6, 4, 2, 3, 2, 2, 4,
701 7, 4, 2, 2, 2, 2, 3, 1,
702 7, 3, 1, 2, 2, 2, 3, 3,
703 7, 3, 2, 2, 2, 2, 2, 4,
704 5, 3, 2, 15, 2, 4,
705 3, 5, 19, 4,
706 4, 6, 4, 3, 3,
707 3, 6, 4, 4,
708 4, 2, 4, 6, 2,
709 6, 2, 2, 3, 3, 3, 2,
710 6, 9, 2, 2, 2, 3, 9,
711 7, 10, 2, 2, 2, 2, 2, 10,
712 9, 4, 2, 3, 3, 2, 2, 3, 2, 5,
713 5, 2, 5, 2, 4, 2,
714 5, 5, 3, 2, 2, 5,
715 5, 6, 3, 2, 3, 7,
716 4, 6, 8, 9, 7,
717 4, 4, 8, 7, 5,
718 1, 4,
719 1, 2,
720 1, 2,
721 1, 14,
722 1, 16,
723 2, 3, 3,
724 2, 2, 2,
725 2, 2, 2,
726 2, 4, 4,
727 1, 16,
728 1, 12,
729 };
730
732 const int webpbn21[]=
733 { 14, 25,
734 // Column constraints
735 1, 2,
736 2, 4, 6,
737 4, 9, 4, 4, 2,
738 4, 1, 6, 2, 6,
739 3, 1, 5, 2,
740 2, 1, 6,
741 2, 1, 5,
742 2, 1, 4,
743 2, 1, 4,
744 3, 1, 4, 2,
745 3, 1, 4, 6,
746 5, 1, 6, 4, 4, 2,
747 3, 9, 2, 6,
748 2, 4, 2,
749 // Row constraints
750 1, 9,
751 2, 1, 1,
752 3, 1, 1, 1,
753 3, 1, 3, 1,
754 1, 13,
755 1, 13,
756 1, 13,
757 1, 13,
758 2, 2, 2,
759 2, 2, 2,
760 0,
761 2, 2, 2,
762 2, 2, 2,
763 2, 2, 2,
764 2, 2, 2,
765 2, 2, 2,
766 2, 2, 2,
767 2, 2, 2,
768 2, 2, 2,
769 2, 2, 2,
770 2, 2, 2,
771 2, 2, 2,
772 2, 2, 2,
773 2, 2, 2,
774 2, 2, 2,
775 };
776
778const int webpbn27[]=
779 { 27, 23,
780 // Column constraints
781 2, 4, 12,
782 3, 6, 1, 1,
783 3, 8, 1, 1,
784 5, 3, 2, 2, 1, 1,
785 6, 2, 1, 1, 2, 1, 6,
786 4, 1, 1, 1, 1,
787 6, 3, 1, 1, 2, 1, 1,
788 5, 3, 2, 3, 1, 1,
789 3, 10, 1, 1,
790 5, 4, 2, 2, 1, 1,
791 6, 3, 1, 1, 2, 1, 1,
792 4, 2, 1, 1, 1,
793 6, 3, 1, 1, 2, 1, 1,
794 5, 3, 2, 3, 1, 6,
795 3, 10, 1, 1,
796 5, 4, 2, 2, 1, 1,
797 6, 3, 1, 1, 2, 1, 1,
798 4, 1, 1, 1, 9,
799 6, 2, 1, 1, 2, 1, 1,
800 5, 2, 2, 3, 1, 3,
801 3, 8, 1, 5,
802 3, 6, 1, 1,
803 3, 4, 9, 1,
804 2, 1, 1,
805 2, 2, 1,
806 2, 1, 1,
807 1, 4,
808 // Row constraints
809 1, 11,
810 1, 17,
811 4, 3, 5, 5, 3,
812 4, 2, 2, 2, 1,
813 7, 2, 1, 3, 1, 3, 1, 4,
814 4, 3, 3, 3, 3,
815 7, 5, 1, 3, 1, 3, 1, 3,
816 4, 3, 2, 2, 4,
817 4, 5, 5, 5, 5,
818 1, 23,
819 0,
820 1, 23,
821 2, 1, 1,
822 2, 1, 1,
823 3, 1, 2, 1,
824 4, 1, 1, 1, 1,
825 4, 1, 1, 1, 1,
826 5, 1, 10, 1, 2, 1,
827 7, 1, 1, 1, 1, 1, 1, 3,
828 8, 1, 1, 1, 1, 1, 1, 1, 1,
829 7, 1, 1, 1, 1, 1, 1, 1,
830 6, 1, 1, 1, 1, 2, 2,
831 3, 5, 5, 3,
832 };
833
835 const int webpbn1[]=
836 { 5, 10,
837 // Column constraints
838 2, 2, 1,
839 3, 2, 1, 3,
840 1, 7,
841 2, 1, 3,
842 2, 2, 1,
843 // Row constraints
844 1, 2,
845 2, 2, 1,
846 2, 1, 1,
847 1, 3,
848 2, 1, 1,
849 2, 1, 1,
850 1, 2,
851 2, 1, 1,
852 2, 1, 2,
853 1, 2,
854 };
855
857 const int webpbn6[]=
858 { 20, 20,
859 // Column constraints
860 1, 5,
861 2, 5, 3,
862 3, 2, 3, 4,
863 3, 1, 7, 2,
864 1, 8,
865 1, 9,
866 1, 9,
867 1, 8,
868 1, 7,
869 1, 8,
870 1, 9,
871 1, 10,
872 1, 13,
873 2, 6, 2,
874 1, 4,
875 1, 6,
876 1, 6,
877 1, 5,
878 1, 6,
879 1, 6,
880 // Row constraints
881 1, 2,
882 1, 2,
883 1, 1,
884 1, 1,
885 2, 1, 3,
886 2, 2, 5,
887 4, 1, 7, 1, 1,
888 4, 1, 8, 2, 2,
889 3, 1, 9, 5,
890 2, 2, 16,
891 2, 1, 17,
892 2, 7, 11,
893 3, 5, 5, 3,
894 2, 5, 4,
895 2, 3, 3,
896 2, 2, 2,
897 2, 2, 1,
898 2, 1, 1,
899 2, 2, 2,
900 2, 2, 2,
901 };
902
904 const int webpbn23[]=
905 { 10, 11,
906 // Column constraints
907 1, 1,
908 1, 3,
909 1, 1,
910 2, 2, 2,
911 1, 2,
912 1, 4,
913 1, 1,
914 1, 3,
915 1, 3,
916 1, 1,
917 // Row constraints
918 1, 1,
919 1, 3,
920 1, 1,
921 1, 2,
922 1, 1,
923 1, 3,
924 1, 3,
925 1, 1,
926 1, 2,
927 1, 2,
928 1, 4,
929 };
930
932const int webpbn16[]=
933 { 34, 34,
934 // Column constraints
935 2, 1, 1,
936 2, 2, 2,
937 2, 3, 3,
938 4, 2, 1, 1, 2,
939 4, 2, 1, 1, 2,
940 4, 1, 1, 1, 1,
941 4, 1, 1, 1, 1,
942 1, 18,
943 6, 2, 1, 1, 1, 1, 2,
944 6, 1, 1, 1, 1, 1, 1,
945 6, 1, 1, 1, 1, 1, 1,
946 1, 26,
947 8, 2, 1, 1, 1, 1, 1, 1, 2,
948 8, 2, 1, 1, 2, 2, 1, 1, 2,
949 8, 2, 1, 1, 2, 2, 1, 1, 2,
950 2, 14, 14,
951 4, 1, 1, 1, 1,
952 4, 1, 1, 1, 1,
953 2, 14, 14,
954 8, 2, 1, 1, 2, 2, 1, 1, 2,
955 8, 2, 1, 1, 2, 2, 1, 1, 2,
956 8, 2, 1, 1, 1, 1, 1, 1, 2,
957 1, 26,
958 6, 1, 1, 1, 1, 1, 1,
959 6, 1, 1, 1, 1, 1, 1,
960 6, 2, 1, 1, 1, 1, 2,
961 1, 18,
962 4, 1, 1, 1, 1,
963 4, 1, 1, 1, 1,
964 4, 2, 1, 1, 2,
965 4, 2, 1, 1, 2,
966 2, 3, 3,
967 2, 2, 2,
968 2, 1, 1,
969 // Row constraints
970 2, 1, 1,
971 2, 2, 2,
972 2, 3, 3,
973 4, 2, 1, 1, 2,
974 4, 2, 1, 1, 2,
975 4, 1, 1, 1, 1,
976 4, 1, 1, 1, 1,
977 1, 18,
978 6, 2, 1, 1, 1, 1, 2,
979 6, 1, 1, 1, 1, 1, 1,
980 6, 1, 1, 1, 1, 1, 1,
981 1, 26,
982 8, 2, 1, 1, 1, 1, 1, 1, 2,
983 8, 2, 1, 1, 2, 2, 1, 1, 2,
984 8, 2, 1, 1, 2, 2, 1, 1, 2,
985 2, 14, 14,
986 4, 1, 1, 1, 1,
987 4, 1, 1, 1, 1,
988 2, 14, 14,
989 8, 2, 1, 1, 2, 2, 1, 1, 2,
990 8, 2, 1, 1, 2, 2, 1, 1, 2,
991 8, 2, 1, 1, 1, 1, 1, 1, 2,
992 1, 26,
993 6, 1, 1, 1, 1, 1, 1,
994 6, 1, 1, 1, 1, 1, 1,
995 6, 2, 1, 1, 1, 1, 2,
996 1, 18,
997 4, 1, 1, 1, 1,
998 4, 1, 1, 1, 1,
999 4, 2, 1, 1, 2,
1000 4, 2, 1, 1, 2,
1001 2, 3, 3,
1002 2, 2, 2,
1003 2, 1, 1,
1004 };
1005
1007 const int webpbn529[]=
1008 { 45, 45,
1009 // Column constraints
1010 6, 7, 1, 1, 1, 1, 1,
1011 13, 2, 2, 4, 1, 4, 1, 5, 1, 4, 1, 4, 1, 2,
1012 10, 3, 1, 4, 1, 4, 1, 14, 4, 1, 2,
1013 8, 1, 1, 5, 1, 2, 3, 4, 1,
1014 4, 3, 13, 1, 10,
1015 3, 1, 9, 4,
1016 4, 6, 7, 2, 2,
1017 4, 8, 4, 1, 4,
1018 6, 2, 8, 3, 2, 5, 3,
1019 5, 10, 1, 3, 7, 2,
1020 6, 8, 6, 2, 8, 1, 2,
1021 7, 1, 1, 2, 2, 8, 1, 1,
1022 11, 2, 1, 1, 1, 2, 1, 3, 1, 3, 3, 1,
1023 8, 2, 1, 1, 1, 5, 4, 2, 1,
1024 8, 2, 1, 1, 1, 1, 7, 2, 1,
1025 8, 2, 1, 1, 2, 9, 1, 2, 1,
1026 5, 4, 6, 12, 1, 3,
1027 4, 16, 13, 3, 2,
1028 3, 12, 21, 2,
1029 3, 2, 13, 23,
1030 3, 2, 14, 19,
1031 4, 2, 14, 20, 2,
1032 6, 2, 13, 7, 2, 8, 2,
1033 5, 12, 8, 1, 7, 2,
1034 9, 5, 1, 1, 1, 2, 8, 1, 5, 2,
1035 8, 2, 1, 1, 1, 9, 1, 1, 4,
1036 8, 2, 1, 1, 1, 6, 1, 3, 5,
1037 6, 2, 2, 1, 5, 6, 2,
1038 8, 2, 1, 3, 1, 3, 7, 3, 2,
1039 9, 2, 3, 2, 1, 1, 2, 4, 4, 2,
1040 9, 2, 2, 1, 1, 2, 3, 1, 8, 2,
1041 5, 9, 3, 1, 7, 2,
1042 5, 12, 4, 1, 6, 2,
1043 5, 7, 4, 1, 2, 5,
1044 5, 2, 6, 6, 5, 6,
1045 4, 8, 8, 6, 3,
1046 5, 3, 10, 8, 4, 2,
1047 5, 5, 11, 9, 5, 2,
1048 5, 3, 1, 12, 16, 2,
1049 4, 3, 1, 12, 16,
1050 4, 5, 2, 13, 21,
1051 6, 6, 1, 3, 3, 1, 1,
1052 14, 5, 1, 3, 1, 3, 1, 1, 2, 1, 4, 1, 3, 1, 3,
1053 13, 5, 1, 3, 1, 3, 1, 4, 1, 4, 1, 3, 1, 3,
1054 6, 1, 1, 1, 1, 1, 1,
1055 // Row constraints
1056 6, 7, 1, 1, 1, 1, 1,
1057 13, 3, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
1058 14, 1, 1, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
1059 9, 2, 1, 2, 1, 1, 1, 1, 6, 2,
1060 4, 3, 30, 1, 5,
1061 9, 1, 5, 8, 1, 1, 7, 1, 1, 3,
1062 7, 3, 4, 8, 1, 5, 1, 2,
1063 4, 3, 20, 6, 6,
1064 6, 3, 3, 7, 2, 5, 1,
1065 9, 3, 3, 1, 1, 9, 1, 1, 5, 6,
1066 7, 2, 3, 8, 1, 3, 4, 2,
1067 7, 5, 3, 1, 10, 4, 5, 2,
1068 6, 1, 2, 3, 8, 4, 6,
1069 5, 2, 2, 3, 11, 10,
1070 5, 2, 2, 3, 10, 7,
1071 6, 2, 3, 1, 7, 12, 2,
1072 6, 2, 3, 1, 4, 11, 2,
1073 6, 4, 1, 2, 1, 11, 2,
1074 4, 9, 1, 2, 9,
1075 5, 6, 2, 1, 4, 11,
1076 6, 2, 5, 1, 2, 6, 6,
1077 5, 6, 2, 4, 8, 4,
1078 4, 4, 2, 16, 1,
1079 4, 2, 2, 15, 2,
1080 4, 3, 2, 15, 4,
1081 4, 3, 3, 13, 4,
1082 3, 4, 12, 9,
1083 3, 1, 9, 10,
1084 5, 2, 1, 17, 7, 2,
1085 6, 2, 2, 8, 3, 8, 2,
1086 6, 2, 3, 6, 3, 8, 2,
1087 6, 2, 4, 5, 4, 7, 2,
1088 5, 2, 5, 5, 4, 6,
1089 5, 4, 4, 5, 4, 9,
1090 5, 1, 4, 6, 4, 4,
1091 6, 4, 3, 6, 4, 3, 2,
1092 7, 2, 1, 2, 7, 4, 4, 2,
1093 7, 2, 2, 2, 9, 5, 5, 2,
1094 6, 2, 2, 2, 10, 6, 6,
1095 5, 3, 2, 1, 9, 18,
1096 3, 8, 4, 23,
1097 9, 1, 2, 1, 2, 2, 1, 1, 1, 2,
1098 12, 2, 1, 4, 2, 1, 4, 1, 5, 1, 3, 1, 2,
1099 11, 2, 1, 5, 4, 4, 1, 5, 1, 3, 1, 2,
1100 5, 1, 10, 1, 1, 1,
1101 };
1102
1103
1105 const int webpbn65[]=
1106 { 34, 40,
1107 // Column constraints
1108 1, 5,
1109 3, 3, 2, 1,
1110 4, 3, 2, 2, 1,
1111 5, 3, 2, 2, 2, 2,
1112 6, 3, 2, 2, 2, 2, 3,
1113 7, 1, 2, 2, 2, 2, 2, 16,
1114 9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
1115 9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
1116 10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
1117 9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
1118 11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
1119 12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
1120 11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
1121 6, 1, 7, 2, 16, 1, 1,
1122 11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1123 11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
1124 9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
1125 9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
1126 11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
1127 11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1128 6, 1, 7, 2, 16, 1, 1,
1129 11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
1130 12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
1131 11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
1132 9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
1133 10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
1134 9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
1135 9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
1136 7, 1, 2, 2, 2, 2, 2, 16,
1137 6, 3, 2, 2, 2, 2, 3,
1138 5, 3, 2, 2, 2, 2,
1139 4, 3, 2, 2, 1,
1140 3, 3, 2, 1,
1141 1, 5,
1142 // Row constraints
1143 1, 12,
1144 3, 5, 2, 5,
1145 4, 5, 2, 2, 5,
1146 7, 1, 2, 2, 2, 2, 2, 1,
1147 7, 4, 2, 2, 4, 2, 2, 4,
1148 7, 4, 2, 2, 4, 2, 2, 4,
1149 7, 1, 2, 2, 2, 2, 2, 1,
1150 7, 6, 2, 2, 2, 2, 2, 6,
1151 7, 6, 2, 2, 2, 2, 2, 6,
1152 3, 1, 14, 1,
1153 2, 10, 10,
1154 4, 8, 3, 3, 8,
1155 8, 1, 1, 2, 1, 1, 2, 1, 1,
1156 6, 9, 2, 2, 2, 2, 9,
1157 2, 9, 9,
1158 6, 1, 1, 1, 1, 1, 1,
1159 3, 12, 2, 12,
1160 2, 12, 12,
1161 5, 1, 1, 4, 1, 1,
1162 2, 14, 14,
1163 2, 12, 12,
1164 5, 2, 1, 4, 1, 2,
1165 3, 9, 4, 9,
1166 5, 1, 7, 4, 7, 1,
1167 7, 1, 1, 1, 4, 1, 1, 1,
1168 5, 1, 7, 4, 7, 1,
1169 5, 1, 7, 4, 7, 1,
1170 7, 1, 2, 1, 2, 1, 2, 1,
1171 5, 1, 7, 2, 7, 1,
1172 7, 1, 1, 6, 2, 6, 1, 1,
1173 9, 1, 1, 1, 1, 2, 1, 1, 1, 1,
1174 7, 1, 1, 6, 2, 6, 1, 1,
1175 6, 1, 1, 5, 5, 1, 1,
1176 7, 1, 1, 1, 8, 1, 1, 1,
1177 6, 1, 1, 4, 4, 1, 1,
1178 5, 1, 2, 6, 2, 1,
1179 4, 2, 4, 4, 2,
1180 3, 2, 6, 2,
1181 2, 4, 4,
1182 1, 6,
1183 };
1184
1185
1186 const int *specs[] = {heart, bear, crocodile, unknown,
1187 pinwheel, difficult, non_unique, dragonfly,
1188 castle, p200,
1189 // From the webpbn survey
1190 webpbn1, // 10
1191 webpbn6, // 11
1192 webpbn21, // 12
1193 webpbn27, // 13
1194 webpbn23, // 14
1195 webpbn16, // 15
1196 webpbn529, // 16
1197 webpbn65, // 17
1198 webpbn436, // 18
1199 };
1200 const unsigned n_examples = sizeof(specs)/sizeof(int*);
1202
1203}
1204
1205// STATISTICS: example-any
Gecode::BoolVarArray
Boolean variable array.
Definition int.hh:839
Gecode::DFA
Deterministic finite automaton (DFA).
Definition int.hh:2203
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >::run
static void run(const Options &opt, Script *s=nullptr)
Gecode::Matrix
Matrix-interface for arrays.
Definition minimodel.hh:2208
Gecode::Matrix::col
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Gecode::Matrix::row
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
Gecode::REG
Regular expressions over integer values.
Definition minimodel.hh:1672
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:723
Gecode::Space
Computation spaces.
Definition core.hpp:1775
Nonogram::webpbn6
const int webpbn6[]
Cat.
Definition nonogram.cpp:857
Nonogram::main
int main(int argc, char *argv[])
Main-function.
Definition nonogram.cpp:199
Nonogram::width
int width(void) const
Return width of board.
Definition nonogram.cpp:75
Nonogram::webpbn65
const int webpbn65[]
Mum.
Definition nonogram.cpp:1105
Nonogram::difficult
const int difficult[]
Specification for a more difficult picture.
Definition nonogram.cpp:361
Nonogram::heart
const int heart[]
Specification for a heart-shaped picture.
Definition nonogram.cpp:231
Nonogram::specs
const int * specs[]
Specification for a heart-shaped picture.
Definition nonogram.cpp:1186
Nonogram::webpbn1
const int webpbn1[]
Dancer.
Definition nonogram.cpp:835
Nonogram::copy
virtual Space * copy(void)
Copy space during cloning.
Definition nonogram.cpp:176
Nonogram::p200
const int p200[]
Specification for a picture of cupid.
Definition nonogram.cpp:589
Nonogram::webpbn27
const int webpbn27[]
Bucks.
Definition nonogram.cpp:778
Nonogram::BRANCH_NONE
@ BRANCH_NONE
Branch on rows/columns in order.
Definition nonogram.cpp:102
Nonogram::BRANCH_AFC
@ BRANCH_AFC
Use AFC for branching.
Definition nonogram.cpp:103
Nonogram::n_examples
const unsigned n_examples
Specification for a heart-shaped picture.
Definition nonogram.cpp:1200
Nonogram::bear
const int bear[]
Specification for a bear/bunny-shaped picture.
Definition nonogram.cpp:256
Nonogram::b
BoolVarArray b
Fields of board.
Definition nonogram.cpp:72
Nonogram::dragonfly
const int dragonfly[]
Specification for a dragonfly-picture.
Definition nonogram.cpp:435
Nonogram::height
int height(void) const
Return height of board.
Definition nonogram.cpp:79
Nonogram::crocodile
const int crocodile[]
Specification for a crocodile-shaped picture.
Definition nonogram.cpp:284
Nonogram::Nonogram
Nonogram(Nonogram &s)
Constructor for cloning s.
Definition nonogram.cpp:170
Nonogram::spec
const int * spec
Specification to be used.
Definition nonogram.cpp:70
Nonogram::pinwheel
const int pinwheel[]
Specification for a pinwheel-picture.
Definition nonogram.cpp:342
Nonogram::print
virtual void print(std::ostream &os) const
Print solution.
Definition nonogram.cpp:182
Nonogram::webpbn436
const int webpbn436[]
Petro.
Definition nonogram.cpp:650
Nonogram::castle
const int castle[]
From http://www.cs.kuleuven.be/~bmd/nonogram.pl.
Definition nonogram.cpp:482
Nonogram::unknown
const int unknown[]
Specification for an unknown picture.
Definition nonogram.cpp:315
Nonogram::Nonogram
Nonogram(const SizeOptions &opt)
Construction of the model.
Definition nonogram.cpp:107
Nonogram::non_unique
const int non_unique[]
Specification for a non-unique picture.
Definition nonogram.cpp:398
Nonogram::webpbn16
const int webpbn16[]
Knot.
Definition nonogram.cpp:932
Nonogram::line
DFA line(int &spos)
Returns next regular expression for line starting from spos.
Definition nonogram.cpp:84
Nonogram::webpbn23
const int webpbn23[]
Edge.
Definition nonogram.cpp:904
Nonogram::webpbn21
const int webpbn21[]
Skid.
Definition nonogram.cpp:732
Nonogram::webpbn529
const int webpbn529[]
Swing.
Definition nonogram.cpp:1007
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::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
Gecode toplevel namespace
Gecode::BOOL_VAR_NONE
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:364
Gecode::BOOL_VAL_MAX
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition val.hpp:135
Gecode::BOOL_VAR_AFC_MAX
BoolVarBranch BOOL_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count with decay factor d.
Definition var.hpp:404