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#include <string>
39
40using namespace Gecode;
41
42namespace {
43
45 extern const int* specs[];
47 extern const unsigned int n_examples;
48
61 const char* instance_spec = R"(format nonogram
62
63separators ","
64sections skip other {
65 "width {width:1..}"
66 "height {height:1..}"
67 "rows" { repeat height { list row: 0.. until eol } }
68 "columns" { repeat width { list col: 0.. until eol } }
69}
70
71check height <= 1000000 / width "the board must have at most a million fields"
72check size(row) == height && size(col) == width "the numbers of rows and columns differ from the board size"
73check count(row) <= 1 || min(row) > 0 "a 0 must be the only clue of its row"
74check count(col) <= 1 || min(col) > 0 "a 0 must be the only clue of its column"
75check sum(row) + count(row) - 1 <= width "the clues of a row do not fit into the width of the board"
76check sum(col) + count(col) - 1 <= height "the clues of a column do not fit into the height of the board"
77)";
78
87 const int* specification(const InstanceOptions& opt, IntSharedArray& file) {
88 unsigned int i;
89 if (opt.builtin(i))
90 return (i < n_examples) ? specs[i] : nullptr;
91 if (!opt.is_file())
92 return nullptr;
93 // The spec has checked the data, so clues are at most a million
94 Instance::Data d = opt.data();
95 int w = static_cast<int>(d.integer("width")), h = static_cast<int>(d.integer("height"));
96 // Width and height, then columns and rows: number of clues and clues
97 IntArgs s;
98 s << w << h;
99 for (int k=0; k<w+h; k++) {
100 bool column = (k < w);
101 IntArgs line = column ? d.ints("col", {k}) : d.ints("row", {k-w});
102 IntArgs clues;
103 for (int c : line)
104 if (c > 0)
105 clues << c;
106 s << clues.size();
107 s << clues;
108 }
109 file = IntSharedArray(s);
110 return &file[0];
111 }
112
113}
114
135class Nonogram : public Script {
136protected:
140 const int* spec;
143
145 int width(void) const {
146 return spec[0];
147 }
148
149 int height(void) const {
150 return spec[1];
151 }
152
154 DFA line(int& spos) {
155 REG r0(0), r1(1);
156 REG border = *r0;
157 REG between = +r0;
158 int hints = spec[spos++];
159 REG r = border;
160 if (hints > 0) {
161 r += r1(spec[spos],spec[spos]);
162 spos++;
163 for (int i=hints-1; i--; spos++)
164 r += between + r1(spec[spos],spec[spos]);
165 }
166 return r + border;
167 }
168
169public:
170 // Branching variants
171 enum {
174 };
175
178 : Script(opt), spec(specification(opt,file)), b(*this,width()*height(),0,1) {
180
181 {
182 int spos = 2;
183 // Post constraints for columns
184 for (int w=0; w<width(); w++)
185 extensional(*this, m.col(w), line(spos));
186 // Post constraints for rows
187 for (int h=0; h<height(); h++)
188 extensional(*this, m.row(h), line(spos));
189 }
190
191
192
193 switch (opt.branching()) {
194 case BRANCH_NONE:
195 {
196 /*
197 * The following branches either by columns or rows, depending on
198 * whether there are more hints relative to the height or width
199 * for columns or rows.
200 *
201 * This idea is due to Pascal Van Hentenryck and has been suggested
202 * to us by Hakan Kjellerstrand.
203 */
204
205 // Number of hints for columns
206 int cols = 0;
207 // Number of hints for rows
208 int rows = 0;
209 int spos = 2;
210 for (int w=0; w<width(); w++) {
211 int hint = spec[spos++];
212 cols += hint; spos += hint;
213 }
214 for (int h=0; h<height(); h++) {
215 int hint = spec[spos++];
216 rows += hint; spos += hint;
217 }
218
219 if (rows*width() > cols*height()) {
220 for (int w=0; w<width(); w++)
221 branch(*this, m.col(w), BOOL_VAR_NONE(), BOOL_VAL_MAX());
222 } else {
223 for (int h=0; h<height(); h++)
224 branch(*this, m.row(h), BOOL_VAR_NONE(), BOOL_VAL_MAX());
225 }
226 }
227 break;
228 case BRANCH_AFC:
229 /*
230 * The following just uses the AFC for branching. This is
231 * equivalent to SIZE/AFC in this case since the variables are
232 * binary.
233 */
234 branch(*this, b, BOOL_VAR_AFC_MAX(opt.decay()), BOOL_VAL_MAX());
235 break;
236 }
237 }
238
241 b.update(*this, s.b);
242 }
243
245 virtual Space*
246 copy(void) {
247 return new Nonogram(*this);
248 }
249
251 virtual void
252 print(std::ostream& os) const {
254 for (int h = 0; h < height(); ++h) {
255 os << '\t';
256 for (int w = 0; w < width(); ++w)
257 os << ((m(w,h).val() == 1) ? '#' : ' ');
258 os << std::endl;
259 }
260 os << std::endl;
261 }
262};
263
264
268int
269main(int argc, char* argv[]) {
270 InstanceOptions opt("Nonogram", instance_spec);
271 opt.instance("8");
272 opt.branching(Nonogram::BRANCH_AFC);
273 opt.branching(Nonogram::BRANCH_NONE, "none",
274 "Branch on rows/columns in order");
275 opt.branching(Nonogram::BRANCH_AFC, "afc",
276 "Use AFC for branching");
277 opt.parse(argc,argv);
278 try {
280 if (specification(opt,file) == nullptr) {
281 std::cerr << "Error: instance must be a number between 0 and " << n_examples-1 << " or a file" << std::endl;
282 return 1;
283 }
284 } catch (const Instance::Error& e) {
285 std::cerr << e.what() << std::endl;
286 return 1;
287 }
289 return 0;
290}
291
292namespace {
293
305
306const int heart[] =
307 { 9, 9,
308 // Column constraints.
309 1, 3,
310 2, 2, 3,
311 2, 2, 2,
312 2, 2, 2,
313 2, 2, 2,
314 2, 2, 2,
315 2, 2, 2,
316 2, 2, 3,
317 1, 3,
318 // Row constraints
319 2, 2, 2,
320 2, 4, 4,
321 3, 1, 3, 1,
322 3, 2, 1, 2,
323 2, 1, 1,
324 2, 2, 2,
325 2, 2, 2,
326 1, 3,
327 1, 1
328 };
329
331const int bear[] =
332 { 13, 8,
333 // Column constraints
334 1, 2,
335 2, 2, 1,
336 2, 3, 2,
337 1, 6,
338 2, 1, 4,
339 1, 3,
340 1, 4,
341 1, 4,
342 1, 4,
343 1, 5,
344 1, 4,
345 2, 1, 3,
346 1, 2,
347 // Row constraints
348 1, 1,
349 1, 2,
350 2, 4, 4,
351 1, 12,
352 1, 8,
353 1, 9,
354 2, 3, 4,
355 2, 2, 2
356 };
357
359const int crocodile[] =
360 { 15, 9,
361 // Column constraints
362 1, 3,
363 1, 4,
364 2, 2, 2,
365 2, 3, 1,
366 2, 2, 3,
367 2, 3, 2,
368 2, 2, 3,
369 2, 4, 2,
370 2, 3, 2,
371 1, 6,
372 2, 1, 3,
373 2, 1, 3,
374 2, 1, 4,
375 1, 5,
376 1, 5,
377 // Row constraints
378 1, 3,
379 3, 2, 3, 2,
380 2, 10, 3,
381 1, 15,
382 5, 1, 1, 1, 1, 6,
383 2, 1, 7,
384 2, 1, 4,
385 2, 1, 4,
386 1, 4
387 };
388
390const int unknown[] =
391 { 10, 10,
392 // Column constraints
393 1, 3,
394 2, 2, 1,
395 2, 2, 2,
396 2, 2, 1,
397 3, 1, 2, 1,
398 2, 1, 1,
399 3, 1, 4, 1,
400 3, 1, 1, 2,
401 2, 3, 1,
402 1, 4,
403 // Row constraints
404 1, 3,
405 2, 2, 1,
406 2, 1, 1,
407 2, 1, 4,
408 4, 1, 1, 1, 1,
409 4, 2, 1, 1, 1,
410 3, 2, 1, 1,
411 2, 1, 2,
412 2, 2, 3,
413 1, 3
414 };
415
417const int pinwheel[] =
418 { 6, 6,
419 // Column constraints
420 2, 1, 2,
421 1, 1,
422 1, 2,
423 1, 2,
424 1, 1,
425 2, 2, 1,
426 // Row constraints
427 2, 2, 1,
428 1, 1,
429 1, 2,
430 1, 2,
431 1, 1,
432 2, 1, 2
433 };
434
436const int difficult[] =
437 { 15, 15,
438 // Column constraints
439 1, 3,
440 1, 2,
441 1, 2,
442 1, 1,
443 1, 2,
444 1, 3,
445 1, 2,
446 1, 4,
447 1, 3,
448 1, 4,
449 2, 2, 1,
450 2, 1, 1,
451 2, 1, 1,
452 2, 1, 1,
453 1, 3,
454 // Row constraints
455 1, 3,
456 2, 1, 1,
457 2, 1, 1,
458 2, 1, 1,
459 2, 1, 2,
460 1, 5,
461 1, 1,
462 1, 2,
463 1, 1,
464 1, 1,
465 2, 1, 2,
466 2, 1, 2,
467 2, 2, 1,
468 2, 2, 2,
469 1, 3
470 };
471
473const int non_unique[] =
474 { 11, 15,
475 // Column constraints
476 1, 5,
477 3, 1, 2, 4,
478 3, 2, 1, 3,
479 4, 2, 2, 1, 1,
480 4, 1, 1, 1, 1,
481 2, 1, 5,
482 5, 2, 1, 1, 3, 2,
483 5, 2, 1, 1, 1, 1,
484 3, 1, 4, 1,
485 2, 1, 1,
486 1, 1,
487 // Row constraints
488 2, 2, 2,
489 2, 2, 2,
490 1, 4,
491 2, 1, 1,
492 2, 1, 1,
493 4, 1, 1, 1, 1,
494 2, 1, 1,
495 2, 1, 4,
496 3, 1, 1, 1,
497 3, 1, 1, 4,
498 2, 1, 3,
499 2, 1, 2,
500 1, 5,
501 2, 2, 2,
502 2, 3, 3
503 };
504
510 const int dragonfly[] =
511 { 20, 20,
512 // Column constraints.
513 4, 1, 1, 1, 2,
514 5, 3, 1, 2, 1, 1,
515 5, 1, 4, 2, 1, 1,
516 4, 1, 3, 2, 4,
517 4, 1, 4, 6, 1,
518 3, 1, 11, 1,
519 4, 5, 1, 6, 2,
520 1, 14,
521 2, 7, 2,
522 2, 7, 2,
523 3, 6, 1, 1,
524 2, 9, 2,
525 4, 3, 1, 1, 1,
526 3, 3, 1, 3,
527 3, 2, 1, 3,
528 3, 2, 1, 5,
529 3, 3, 2, 2,
530 3, 3, 3, 2,
531 3, 2, 3, 2,
532 2, 2, 6,
533 // Row constraints
534 2, 7, 1,
535 3, 1, 1, 2,
536 3, 2, 1, 2,
537 3, 1, 2, 2,
538 3, 4, 2, 3,
539 3, 3, 1, 4,
540 3, 3, 1, 3,
541 3, 2, 1, 4,
542 2, 2, 9,
543 3, 2, 1, 5,
544 2, 2, 7,
545 1, 14,
546 2, 8, 2,
547 3, 6, 2, 2,
548 4, 2, 8, 1, 3,
549 4, 1, 5, 5, 2,
550 5, 1, 3, 2, 4, 1,
551 5, 3, 1, 2, 4, 1,
552 5, 1, 1, 3, 1, 3,
553 4, 2, 1, 1, 2
554 };
555
557 const int castle[] = {
558 60, 35,
559 // Column constraints
560 7, 2,3,1,5,1,7,1,
561 7, 2,4,2,3,2,3,5,
562 8, 2,6,3,1,1,5,1,5,
563 10, 2,4,2,1,1,1,4,1,1,2,
564 7, 2,8,2,1,5,2,5,
565 7, 3,1,6,2,5,1,5,
566 9, 3,3,3,1,1,6,1,1,1,
567 9, 3,2,2,2,2,8,1,1,3,
568 7, 1,4,4,3,7,1,1,
569 7, 1,2,2,2,3,7,9,
570 8, 1,2,3,1,1,5,2,2,
571 7, 2,2,3,1,1,6,1,
572 6, 1,3,1,5,4,1,
573 8, 1,3,1,1,6,1,3,1,
574 8, 3,3,4,5,1,4,2,1,
575 6, 2,3,3,9,7,1,
576 8, 2,3,2,2,1,1,3,5,
577 8, 4,2,1,1,1,1,2,3,
578 7, 4,2,2,1,4,3,2,
579 4, 4,3,16,2,
580 5, 1,2,5,7,1,
581 6, 4,3,2,2,7,1,
582 5, 2,3,1,10,1,
583 6, 2,4,2,1,4,1,
584 5, 1,6,7,3,1,
585 4, 3,11,3,1,
586 5, 7,1,11,2,1,
587 7, 2,2,2,2,2,2,2,
588 7, 3,1,1,1,1,2,1,
589 7, 2,2,2,2,1,1,1,
590 7, 1,1,1,1,2,1,2,
591 8, 2,2,2,2,1,1,1,1,
592 5, 4,1,1,2,2,
593 5, 5,2,17,2,1,
594 6, 9,2,3,1,4,2,
595 6, 9,4,2,1,1,1,
596 5, 5,4,2,1,4,
597 7, 11,1,2,1,4,1,2,
598 5, 3,4,2,4,4,
599 8, 2,1,4,1,2,1,5,2,
600 5, 8,4,1,1,2,
601 5, 1,1,3,2,3,
602 6, 1,3,1,8,1,6,
603 4, 2,1,7,14,
604 7, 1,2,4,4,1,2,3,
605 10, 1,1,4,2,1,1,1,1,1,4,
606 6, 3,5,3,1,1,4,
607 6, 2,4,2,2,1,2,
608 5, 4,2,3,8,4,
609 5, 4,15,2,2,4,
610 6, 4,1,10,2,1,2,
611 6, 2,12,6,1,2,4,
612 7, 3,1,3,1,3,3,4,
613 6, 3,1,2,3,4,1,
614 7, 5,2,2,2,3,3,3,
615 9, 1,2,2,2,2,4,1,1,3,
616 7, 2,1,4,2,7,1,1,
617 6, 5,2,2,3,6,3,
618 7, 3,3,2,2,3,2,3,
619 7, 4,1,2,1,1,2,1,
620
621 // Row constraints
622 4, 12,1,1,1,
623 5, 8,6,3,1,3,
624 6, 5,8,4,3,1,5,
625 8, 7,3,4,1,3,5,1,7,
626 13, 2,2,4,9,1,5,1,1,1,1,1,1,1,
627 8, 4,5,10,2,1,8,7,1,
628 7, 5,1,3,3,16,1,2,
629 8, 8,5,1,2,4,9,1,3,
630 12, 4,5,3,14,1,1,1,1,4,1,1,3,
631 19, 3,3,2,2,2,4,1,1,1,1,1,1,1,1,3,1,1,3,2,
632 11, 8,2,7,2,1,1,2,1,1,3,3,
633 13, 1,5,9,12,2,1,1,3,1,1,2,2,1,
634 17, 3,2,2,1,1,1,1,4,1,1,1,3,3,1,1,2,2,
635 12, 5,2,2,2,2,1,5,2,1,1,2,5,
636 12, 3,5,9,2,1,1,6,3,1,3,2,3,
637 12, 1,4,1,1,1,4,1,5,5,3,3,3,
638 10, 4,1,1,1,1,3,4,6,6,3,
639 12, 3,1,3,1,1,3,3,1,1,4,6,1,
640 11, 3,1,5,1,1,3,1,1,9,4,1,
641 14, 2,1,1,7,1,4,1,1,1,1,1,1,3,5,
642 11, 9,2,1,3,1,1,1,1,4,2,1,
643 10, 1,14,1,1,2,2,2,10,1,2,
644 10, 1,9,2,1,2,6,1,5,3,2,
645 12, 1,9,9,1,2,2,3,1,1,4,3,1,
646 10, 10,1,3,4,1,3,2,1,2,8,
647 9, 9,1,3,5,1,1,1,2,7,
648 12, 4,5,1,2,5,1,3,1,1,2,1,3,
649 14, 1,1,1,1,2,6,2,3,2,1,1,2,3,1,
650 11, 1,6,1,5,7,1,3,3,2,4,3,
651 10, 1,2,1,2,9,1,5,2,6,2,
652 8, 10,2,2,13,1,3,3,1,
653 11, 2,2,1,6,2,3,3,2,2,2,1,
654 12, 2,2,1,1,12,2,2,9,2,2,2,2,
655 9, 5,1,2,4,1,5,11,2,2,
656 3, 15,6,18,
657 };
658
664 const int p200[] =
665 { 25, 25,
666 // Column constraints
667 4, 1,1,2,2,
668 3, 5,5,7,
669 4, 5,2,2,9,
670 4, 3,2,3,9,
671 5, 1,1,3,2,7,
672 3, 3,1,5,
673 5, 7,1,1,1,3,
674 6, 1,2,1,1,2,1,
675 3, 4,2,4,
676 4, 1,2,2,2,
677 3, 4,6,2,
678 4, 1,2,2,1,
679 4, 3,3,2,1,
680 3, 4,1,15,
681 6, 1,1,1,3,1,1,
682 6, 2,1,1,2,2,3,
683 4, 1,4,4,1,
684 4, 1,4,3,2,
685 4, 1,1,2,2,
686 5, 7,2,3,1,1,
687 5, 2,1,1,1,5,
688 3, 1,2,5,
689 4, 1,1,1,3,
690 3, 4,2,1,
691 1, 3,
692 // Row constraints
693 3, 2,2,3,
694 5, 4,1,1,1,4,
695 5, 4,1,2,1,1,
696 7, 4,1,1,1,1,1,1,
697 6, 2,1,1,2,3,5,
698 6, 1,1,1,1,2,1,
699 5, 3,1,5,1,2,
700 6, 3,2,2,1,2,2,
701 7, 2,1,4,1,1,1,1,
702 6, 2,2,1,2,1,2,
703 6, 1,1,1,3,2,3,
704 5, 1,1,2,7,3,
705 5, 1,2,2,1,5,
706 5, 3,2,2,1,2,
707 4, 3,2,1,2,
708 3, 5,1,2,
709 4, 2,2,1,2,
710 4, 4,2,1,2,
711 4, 6,2,3,2,
712 4, 7,4,3,2,
713 3, 7,4,4,
714 3, 7,1,4,
715 3, 6,1,4,
716 3, 4,2,2,
717 2, 2,1
718 };
719
720 // The following instances are from the http://webpbn.com site and
721 // are all designed by Jan Wolter.
722 // See also the survey at http://webpbn.com/survey/
723
725 const int webpbn436[]=
726 { 40, 35,
727 // Column constraints
728 1, 1,
729 2, 3, 2,
730 3, 2, 3, 3,
731 3, 3, 3, 3,
732 4, 3, 3, 3, 3,
733 4, 4, 2, 2, 2,
734 4, 3, 3, 2, 3,
735 4, 3, 2, 2, 2,
736 3, 3, 2, 6,
737 2, 2, 9,
738 3, 2, 3, 3,
739 5, 4, 4, 3, 2, 4,
740 5, 7, 2, 5, 2, 6,
741 6, 12, 2, 3, 2, 3, 2,
742 6, 3, 1, 2, 2, 2, 3,
743 6, 2, 2, 3, 2, 2, 2,
744 6, 6, 2, 6, 2, 2, 2,
745 5, 12, 4, 3, 2, 2,
746 4, 12, 2, 2, 2,
747 3, 2, 6, 2,
748 4, 2, 6, 5, 2,
749 4, 10, 9, 2, 2,
750 5, 12, 3, 3, 2, 2,
751 7, 6, 2, 2, 2, 2, 2, 2,
752 6, 2, 2, 3, 2, 2, 2,
753 6, 4, 3, 2, 2, 2, 3,
754 6, 7, 3, 3, 2, 3, 2,
755 5, 5, 3, 5, 2, 6,
756 5, 4, 3, 3, 3, 4,
757 3, 3, 5, 3,
758 2, 3, 9,
759 3, 4, 2, 6,
760 4, 4, 2, 2, 2,
761 4, 4, 2, 2, 3,
762 4, 3, 2, 2, 3,
763 3, 3, 3, 3,
764 3, 3, 3, 3,
765 3, 4, 3, 3,
766 3, 2, 3, 3,
767 2, 2, 1,
768 // Row constraints
769 2, 2, 2,
770 3, 2, 3, 2,
771 4, 3, 3, 3, 2,
772 4, 3, 3, 3, 3,
773 6, 2, 3, 3, 3, 3, 2,
774 6, 3, 3, 3, 3, 3, 3,
775 6, 4, 2, 3, 2, 2, 4,
776 7, 4, 2, 2, 2, 2, 3, 1,
777 7, 3, 1, 2, 2, 2, 3, 3,
778 7, 3, 2, 2, 2, 2, 2, 4,
779 5, 3, 2, 15, 2, 4,
780 3, 5, 19, 4,
781 4, 6, 4, 3, 3,
782 3, 6, 4, 4,
783 4, 2, 4, 6, 2,
784 6, 2, 2, 3, 3, 3, 2,
785 6, 9, 2, 2, 2, 3, 9,
786 7, 10, 2, 2, 2, 2, 2, 10,
787 9, 4, 2, 3, 3, 2, 2, 3, 2, 5,
788 5, 2, 5, 2, 4, 2,
789 5, 5, 3, 2, 2, 5,
790 5, 6, 3, 2, 3, 7,
791 4, 6, 8, 9, 7,
792 4, 4, 8, 7, 5,
793 1, 4,
794 1, 2,
795 1, 2,
796 1, 14,
797 1, 16,
798 2, 3, 3,
799 2, 2, 2,
800 2, 2, 2,
801 2, 4, 4,
802 1, 16,
803 1, 12,
804 };
805
807 const int webpbn21[]=
808 { 14, 25,
809 // Column constraints
810 1, 2,
811 2, 4, 6,
812 4, 9, 4, 4, 2,
813 4, 1, 6, 2, 6,
814 3, 1, 5, 2,
815 2, 1, 6,
816 2, 1, 5,
817 2, 1, 4,
818 2, 1, 4,
819 3, 1, 4, 2,
820 3, 1, 4, 6,
821 5, 1, 6, 4, 4, 2,
822 3, 9, 2, 6,
823 2, 4, 2,
824 // Row constraints
825 1, 9,
826 2, 1, 1,
827 3, 1, 1, 1,
828 3, 1, 3, 1,
829 1, 13,
830 1, 13,
831 1, 13,
832 1, 13,
833 2, 2, 2,
834 2, 2, 2,
835 0,
836 2, 2, 2,
837 2, 2, 2,
838 2, 2, 2,
839 2, 2, 2,
840 2, 2, 2,
841 2, 2, 2,
842 2, 2, 2,
843 2, 2, 2,
844 2, 2, 2,
845 2, 2, 2,
846 2, 2, 2,
847 2, 2, 2,
848 2, 2, 2,
849 2, 2, 2,
850 };
851
853const int webpbn27[]=
854 { 27, 23,
855 // Column constraints
856 2, 4, 12,
857 3, 6, 1, 1,
858 3, 8, 1, 1,
859 5, 3, 2, 2, 1, 1,
860 6, 2, 1, 1, 2, 1, 6,
861 4, 1, 1, 1, 1,
862 6, 3, 1, 1, 2, 1, 1,
863 5, 3, 2, 3, 1, 1,
864 3, 10, 1, 1,
865 5, 4, 2, 2, 1, 1,
866 6, 3, 1, 1, 2, 1, 1,
867 4, 2, 1, 1, 1,
868 6, 3, 1, 1, 2, 1, 1,
869 5, 3, 2, 3, 1, 6,
870 3, 10, 1, 1,
871 5, 4, 2, 2, 1, 1,
872 6, 3, 1, 1, 2, 1, 1,
873 4, 1, 1, 1, 9,
874 6, 2, 1, 1, 2, 1, 1,
875 5, 2, 2, 3, 1, 3,
876 3, 8, 1, 5,
877 3, 6, 1, 1,
878 3, 4, 9, 1,
879 2, 1, 1,
880 2, 2, 1,
881 2, 1, 1,
882 1, 4,
883 // Row constraints
884 1, 11,
885 1, 17,
886 4, 3, 5, 5, 3,
887 4, 2, 2, 2, 1,
888 7, 2, 1, 3, 1, 3, 1, 4,
889 4, 3, 3, 3, 3,
890 7, 5, 1, 3, 1, 3, 1, 3,
891 4, 3, 2, 2, 4,
892 4, 5, 5, 5, 5,
893 1, 23,
894 0,
895 1, 23,
896 2, 1, 1,
897 2, 1, 1,
898 3, 1, 2, 1,
899 4, 1, 1, 1, 1,
900 4, 1, 1, 1, 1,
901 5, 1, 10, 1, 2, 1,
902 7, 1, 1, 1, 1, 1, 1, 3,
903 8, 1, 1, 1, 1, 1, 1, 1, 1,
904 7, 1, 1, 1, 1, 1, 1, 1,
905 6, 1, 1, 1, 1, 2, 2,
906 3, 5, 5, 3,
907 };
908
910 const int webpbn1[]=
911 { 5, 10,
912 // Column constraints
913 2, 2, 1,
914 3, 2, 1, 3,
915 1, 7,
916 2, 1, 3,
917 2, 2, 1,
918 // Row constraints
919 1, 2,
920 2, 2, 1,
921 2, 1, 1,
922 1, 3,
923 2, 1, 1,
924 2, 1, 1,
925 1, 2,
926 2, 1, 1,
927 2, 1, 2,
928 1, 2,
929 };
930
932 const int webpbn6[]=
933 { 20, 20,
934 // Column constraints
935 1, 5,
936 2, 5, 3,
937 3, 2, 3, 4,
938 3, 1, 7, 2,
939 1, 8,
940 1, 9,
941 1, 9,
942 1, 8,
943 1, 7,
944 1, 8,
945 1, 9,
946 1, 10,
947 1, 13,
948 2, 6, 2,
949 1, 4,
950 1, 6,
951 1, 6,
952 1, 5,
953 1, 6,
954 1, 6,
955 // Row constraints
956 1, 2,
957 1, 2,
958 1, 1,
959 1, 1,
960 2, 1, 3,
961 2, 2, 5,
962 4, 1, 7, 1, 1,
963 4, 1, 8, 2, 2,
964 3, 1, 9, 5,
965 2, 2, 16,
966 2, 1, 17,
967 2, 7, 11,
968 3, 5, 5, 3,
969 2, 5, 4,
970 2, 3, 3,
971 2, 2, 2,
972 2, 2, 1,
973 2, 1, 1,
974 2, 2, 2,
975 2, 2, 2,
976 };
977
979 const int webpbn23[]=
980 { 10, 11,
981 // Column constraints
982 1, 1,
983 1, 3,
984 1, 1,
985 2, 2, 2,
986 1, 2,
987 1, 4,
988 1, 1,
989 1, 3,
990 1, 3,
991 1, 1,
992 // Row constraints
993 1, 1,
994 1, 3,
995 1, 1,
996 1, 2,
997 1, 1,
998 1, 3,
999 1, 3,
1000 1, 1,
1001 1, 2,
1002 1, 2,
1003 1, 4,
1004 };
1005
1007const int webpbn16[]=
1008 { 34, 34,
1009 // Column constraints
1010 2, 1, 1,
1011 2, 2, 2,
1012 2, 3, 3,
1013 4, 2, 1, 1, 2,
1014 4, 2, 1, 1, 2,
1015 4, 1, 1, 1, 1,
1016 4, 1, 1, 1, 1,
1017 1, 18,
1018 6, 2, 1, 1, 1, 1, 2,
1019 6, 1, 1, 1, 1, 1, 1,
1020 6, 1, 1, 1, 1, 1, 1,
1021 1, 26,
1022 8, 2, 1, 1, 1, 1, 1, 1, 2,
1023 8, 2, 1, 1, 2, 2, 1, 1, 2,
1024 8, 2, 1, 1, 2, 2, 1, 1, 2,
1025 2, 14, 14,
1026 4, 1, 1, 1, 1,
1027 4, 1, 1, 1, 1,
1028 2, 14, 14,
1029 8, 2, 1, 1, 2, 2, 1, 1, 2,
1030 8, 2, 1, 1, 2, 2, 1, 1, 2,
1031 8, 2, 1, 1, 1, 1, 1, 1, 2,
1032 1, 26,
1033 6, 1, 1, 1, 1, 1, 1,
1034 6, 1, 1, 1, 1, 1, 1,
1035 6, 2, 1, 1, 1, 1, 2,
1036 1, 18,
1037 4, 1, 1, 1, 1,
1038 4, 1, 1, 1, 1,
1039 4, 2, 1, 1, 2,
1040 4, 2, 1, 1, 2,
1041 2, 3, 3,
1042 2, 2, 2,
1043 2, 1, 1,
1044 // Row constraints
1045 2, 1, 1,
1046 2, 2, 2,
1047 2, 3, 3,
1048 4, 2, 1, 1, 2,
1049 4, 2, 1, 1, 2,
1050 4, 1, 1, 1, 1,
1051 4, 1, 1, 1, 1,
1052 1, 18,
1053 6, 2, 1, 1, 1, 1, 2,
1054 6, 1, 1, 1, 1, 1, 1,
1055 6, 1, 1, 1, 1, 1, 1,
1056 1, 26,
1057 8, 2, 1, 1, 1, 1, 1, 1, 2,
1058 8, 2, 1, 1, 2, 2, 1, 1, 2,
1059 8, 2, 1, 1, 2, 2, 1, 1, 2,
1060 2, 14, 14,
1061 4, 1, 1, 1, 1,
1062 4, 1, 1, 1, 1,
1063 2, 14, 14,
1064 8, 2, 1, 1, 2, 2, 1, 1, 2,
1065 8, 2, 1, 1, 2, 2, 1, 1, 2,
1066 8, 2, 1, 1, 1, 1, 1, 1, 2,
1067 1, 26,
1068 6, 1, 1, 1, 1, 1, 1,
1069 6, 1, 1, 1, 1, 1, 1,
1070 6, 2, 1, 1, 1, 1, 2,
1071 1, 18,
1072 4, 1, 1, 1, 1,
1073 4, 1, 1, 1, 1,
1074 4, 2, 1, 1, 2,
1075 4, 2, 1, 1, 2,
1076 2, 3, 3,
1077 2, 2, 2,
1078 2, 1, 1,
1079 };
1080
1082 const int webpbn529[]=
1083 { 45, 45,
1084 // Column constraints
1085 6, 7, 1, 1, 1, 1, 1,
1086 13, 2, 2, 4, 1, 4, 1, 5, 1, 4, 1, 4, 1, 2,
1087 10, 3, 1, 4, 1, 4, 1, 14, 4, 1, 2,
1088 8, 1, 1, 5, 1, 2, 3, 4, 1,
1089 4, 3, 13, 1, 10,
1090 3, 1, 9, 4,
1091 4, 6, 7, 2, 2,
1092 4, 8, 4, 1, 4,
1093 6, 2, 8, 3, 2, 5, 3,
1094 5, 10, 1, 3, 7, 2,
1095 6, 8, 6, 2, 8, 1, 2,
1096 7, 1, 1, 2, 2, 8, 1, 1,
1097 11, 2, 1, 1, 1, 2, 1, 3, 1, 3, 3, 1,
1098 8, 2, 1, 1, 1, 5, 4, 2, 1,
1099 8, 2, 1, 1, 1, 1, 7, 2, 1,
1100 8, 2, 1, 1, 2, 9, 1, 2, 1,
1101 5, 4, 6, 12, 1, 3,
1102 4, 16, 13, 3, 2,
1103 3, 12, 21, 2,
1104 3, 2, 13, 23,
1105 3, 2, 14, 19,
1106 4, 2, 14, 20, 2,
1107 6, 2, 13, 7, 2, 8, 2,
1108 5, 12, 8, 1, 7, 2,
1109 9, 5, 1, 1, 1, 2, 8, 1, 5, 2,
1110 8, 2, 1, 1, 1, 9, 1, 1, 4,
1111 8, 2, 1, 1, 1, 6, 1, 3, 5,
1112 6, 2, 2, 1, 5, 6, 2,
1113 8, 2, 1, 3, 1, 3, 7, 3, 2,
1114 9, 2, 3, 2, 1, 1, 2, 4, 4, 2,
1115 9, 2, 2, 1, 1, 2, 3, 1, 8, 2,
1116 5, 9, 3, 1, 7, 2,
1117 5, 12, 4, 1, 6, 2,
1118 5, 7, 4, 1, 2, 5,
1119 5, 2, 6, 6, 5, 6,
1120 4, 8, 8, 6, 3,
1121 5, 3, 10, 8, 4, 2,
1122 5, 5, 11, 9, 5, 2,
1123 5, 3, 1, 12, 16, 2,
1124 4, 3, 1, 12, 16,
1125 4, 5, 2, 13, 21,
1126 6, 6, 1, 3, 3, 1, 1,
1127 14, 5, 1, 3, 1, 3, 1, 1, 2, 1, 4, 1, 3, 1, 3,
1128 13, 5, 1, 3, 1, 3, 1, 4, 1, 4, 1, 3, 1, 3,
1129 6, 1, 1, 1, 1, 1, 1,
1130 // Row constraints
1131 6, 7, 1, 1, 1, 1, 1,
1132 13, 3, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
1133 14, 1, 1, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
1134 9, 2, 1, 2, 1, 1, 1, 1, 6, 2,
1135 4, 3, 30, 1, 5,
1136 9, 1, 5, 8, 1, 1, 7, 1, 1, 3,
1137 7, 3, 4, 8, 1, 5, 1, 2,
1138 4, 3, 20, 6, 6,
1139 6, 3, 3, 7, 2, 5, 1,
1140 9, 3, 3, 1, 1, 9, 1, 1, 5, 6,
1141 7, 2, 3, 8, 1, 3, 4, 2,
1142 7, 5, 3, 1, 10, 4, 5, 2,
1143 6, 1, 2, 3, 8, 4, 6,
1144 5, 2, 2, 3, 11, 10,
1145 5, 2, 2, 3, 10, 7,
1146 6, 2, 3, 1, 7, 12, 2,
1147 6, 2, 3, 1, 4, 11, 2,
1148 6, 4, 1, 2, 1, 11, 2,
1149 4, 9, 1, 2, 9,
1150 5, 6, 2, 1, 4, 11,
1151 6, 2, 5, 1, 2, 6, 6,
1152 5, 6, 2, 4, 8, 4,
1153 4, 4, 2, 16, 1,
1154 4, 2, 2, 15, 2,
1155 4, 3, 2, 15, 4,
1156 4, 3, 3, 13, 4,
1157 3, 4, 12, 9,
1158 3, 1, 9, 10,
1159 5, 2, 1, 17, 7, 2,
1160 6, 2, 2, 8, 3, 8, 2,
1161 6, 2, 3, 6, 3, 8, 2,
1162 6, 2, 4, 5, 4, 7, 2,
1163 5, 2, 5, 5, 4, 6,
1164 5, 4, 4, 5, 4, 9,
1165 5, 1, 4, 6, 4, 4,
1166 6, 4, 3, 6, 4, 3, 2,
1167 7, 2, 1, 2, 7, 4, 4, 2,
1168 7, 2, 2, 2, 9, 5, 5, 2,
1169 6, 2, 2, 2, 10, 6, 6,
1170 5, 3, 2, 1, 9, 18,
1171 3, 8, 4, 23,
1172 9, 1, 2, 1, 2, 2, 1, 1, 1, 2,
1173 12, 2, 1, 4, 2, 1, 4, 1, 5, 1, 3, 1, 2,
1174 11, 2, 1, 5, 4, 4, 1, 5, 1, 3, 1, 2,
1175 5, 1, 10, 1, 1, 1,
1176 };
1177
1178
1180 const int webpbn65[]=
1181 { 34, 40,
1182 // Column constraints
1183 1, 5,
1184 3, 3, 2, 1,
1185 4, 3, 2, 2, 1,
1186 5, 3, 2, 2, 2, 2,
1187 6, 3, 2, 2, 2, 2, 3,
1188 7, 1, 2, 2, 2, 2, 2, 16,
1189 9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
1190 9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
1191 10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
1192 9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
1193 11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
1194 12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
1195 11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
1196 6, 1, 7, 2, 16, 1, 1,
1197 11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1198 11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
1199 9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
1200 9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
1201 11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
1202 11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1203 6, 1, 7, 2, 16, 1, 1,
1204 11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
1205 12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
1206 11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
1207 9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
1208 10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
1209 9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
1210 9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
1211 7, 1, 2, 2, 2, 2, 2, 16,
1212 6, 3, 2, 2, 2, 2, 3,
1213 5, 3, 2, 2, 2, 2,
1214 4, 3, 2, 2, 1,
1215 3, 3, 2, 1,
1216 1, 5,
1217 // Row constraints
1218 1, 12,
1219 3, 5, 2, 5,
1220 4, 5, 2, 2, 5,
1221 7, 1, 2, 2, 2, 2, 2, 1,
1222 7, 4, 2, 2, 4, 2, 2, 4,
1223 7, 4, 2, 2, 4, 2, 2, 4,
1224 7, 1, 2, 2, 2, 2, 2, 1,
1225 7, 6, 2, 2, 2, 2, 2, 6,
1226 7, 6, 2, 2, 2, 2, 2, 6,
1227 3, 1, 14, 1,
1228 2, 10, 10,
1229 4, 8, 3, 3, 8,
1230 8, 1, 1, 2, 1, 1, 2, 1, 1,
1231 6, 9, 2, 2, 2, 2, 9,
1232 2, 9, 9,
1233 6, 1, 1, 1, 1, 1, 1,
1234 3, 12, 2, 12,
1235 2, 12, 12,
1236 5, 1, 1, 4, 1, 1,
1237 2, 14, 14,
1238 2, 12, 12,
1239 5, 2, 1, 4, 1, 2,
1240 3, 9, 4, 9,
1241 5, 1, 7, 4, 7, 1,
1242 7, 1, 1, 1, 4, 1, 1, 1,
1243 5, 1, 7, 4, 7, 1,
1244 5, 1, 7, 4, 7, 1,
1245 7, 1, 2, 1, 2, 1, 2, 1,
1246 5, 1, 7, 2, 7, 1,
1247 7, 1, 1, 6, 2, 6, 1, 1,
1248 9, 1, 1, 1, 1, 2, 1, 1, 1, 1,
1249 7, 1, 1, 6, 2, 6, 1, 1,
1250 6, 1, 1, 5, 5, 1, 1,
1251 7, 1, 1, 1, 8, 1, 1, 1,
1252 6, 1, 1, 4, 4, 1, 1,
1253 5, 1, 2, 6, 2, 1,
1254 4, 2, 4, 4, 2,
1255 3, 2, 6, 2,
1256 2, 4, 4,
1257 1, 6,
1258 };
1259
1260
1261 const int *specs[] = {heart, bear, crocodile, unknown,
1263 castle, p200,
1264 // From the webpbn survey
1265 webpbn1, // 10
1266 webpbn6, // 11
1267 webpbn21, // 12
1268 webpbn27, // 13
1269 webpbn23, // 14
1270 webpbn16, // 15
1271 webpbn529, // 16
1272 webpbn65, // 17
1273 webpbn436, // 18
1274 };
1275 const unsigned n_examples = sizeof(specs)/sizeof(int*);
1277
1278}
1279
1280// STATISTICS: example-any
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
Boolean variable array.
Definition int.hh:840
Finite automaton with deterministic construction by default.
Definition int.hh:2620
static void run(const Options &opt, Script *s=nullptr)
Options for scripts with additional instance parameter
Definition driver.hh:834
Named values read from an instance.
Definition instance.hh:406
Exception for errors in specs and instance files
Definition instance.hh:337
virtual const char * what(void) const noexcept override
Return the full message.
Definition data.cpp:56
Passing integer arguments.
Definition int.hh:653
Matrix-interface for arrays.
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
Regular expressions over integer values.
Computation spaces.
Definition core.hpp:1787
const int webpbn6[]
Cat.
Definition nonogram.cpp:932
int main(int argc, char *argv[])
Main-function.
Definition nonogram.cpp:269
int width(void) const
Return width of board.
Definition nonogram.cpp:145
const int webpbn65[]
Mum.
const int difficult[]
Specification for a more difficult picture.
Definition nonogram.cpp:436
const int heart[]
Specification for a heart-shaped picture.
Definition nonogram.cpp:306
const int * specs[]
Specification for a heart-shaped picture.
const char * instance_spec
Reader spec for nonogram files.
Definition nonogram.cpp:61
const int webpbn1[]
Dancer.
Definition nonogram.cpp:910
virtual Space * copy(void)
Copy space during cloning.
Definition nonogram.cpp:246
const int p200[]
Specification for a picture of cupid.
Definition nonogram.cpp:664
const int webpbn27[]
Bucks.
Definition nonogram.cpp:853
Nonogram(const InstanceOptions &opt)
Construction of the model.
Definition nonogram.cpp:177
@ BRANCH_NONE
Branch on rows/columns in order.
Definition nonogram.cpp:172
@ BRANCH_AFC
Use AFC for branching.
Definition nonogram.cpp:173
const unsigned n_examples
Specification for a heart-shaped picture.
const int bear[]
Specification for a bear/bunny-shaped picture.
Definition nonogram.cpp:331
BoolVarArray b
Fields of board.
Definition nonogram.cpp:142
IntSharedArray file
Specification read from a file.
Definition nonogram.cpp:138
const int dragonfly[]
Specification for a dragonfly-picture.
Definition nonogram.cpp:510
int height(void) const
Return height of board.
Definition nonogram.cpp:149
const int crocodile[]
Specification for a crocodile-shaped picture.
Definition nonogram.cpp:359
Nonogram(Nonogram &s)
Constructor for cloning s.
Definition nonogram.cpp:240
const int * spec
Specification to be used.
Definition nonogram.cpp:140
const int pinwheel[]
Specification for a pinwheel-picture.
Definition nonogram.cpp:417
virtual void print(std::ostream &os) const
Print solution.
Definition nonogram.cpp:252
const int webpbn436[]
Petro.
Definition nonogram.cpp:725
const int castle[]
From http://www.cs.kuleuven.be/~bmd/nonogram.pl.
Definition nonogram.cpp:557
const int unknown[]
Specification for an unknown picture.
Definition nonogram.cpp:390
const int non_unique[]
Specification for a non-unique picture.
Definition nonogram.cpp:473
const int webpbn16[]
Knot.
DFA line(int &spos)
Returns next regular expression for line starting from spos.
Definition nonogram.cpp:154
const int webpbn23[]
Edge.
Definition nonogram.cpp:979
const int webpbn21[]
Skid.
Definition nonogram.cpp:807
const int webpbn529[]
Swing.
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:177
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:1002
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 extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
Gecode toplevel namespace
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Definition int.hh:1813
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:364
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition val.hpp:135
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