this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Lagerkvist <lagerkvist@gecode.org>
5 *
6 * Copyright:
7 * Mikael Lagerkvist, 2005
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
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
43 /// List of specifications
44 extern const int* specs[];
45 /// Number of specifications
46 extern const unsigned int n_examples;
47
48}
49
50/**
51 * \brief %Example: %Nonogram
52 *
53 * This example solves nonograms. A nonogram is composed of a matrix of
54 * markers. For each row/column there is a specification on how many groups
55 * of markers (separated by one or more unmarked spots) and their length.
56 * The objective is to find a valid assignment, which incidentally may also
57 * produce a pretty picture.
58 *
59 * See problem 12 at http://www.csplib.org/.
60 *
61 * Note that "Modeling and Programming with Gecode" uses this example
62 * as a case study.
63 *
64 * \ingroup Example
65 *
66 */
67class Nonogram : public Script {
68protected:
69 /// Specification to be used
70 const int* spec;
71 /// Fields of board
72 BoolVarArray b;
73
74 /// Return width of board
75 int width(void) const {
76 return spec[0];
77 }
78 /// Return height of board
79 int height(void) const {
80 return spec[1];
81 }
82
83 /// Returns next regular expression for line starting from spos
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, ///< Branch on rows/columns in order
103 BRANCH_AFC, ///< Use AFC for branching
104 };
105
106 /// Construction of the model.
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
169 /// Constructor for cloning \a s
170 Nonogram(Nonogram& s) : Script(s), spec(s.spec) {
171 b.update(*this, s.b);
172 }
173
174 /// Copy space during cloning
175 virtual Space*
176 copy(void) {
177 return new Nonogram(*this);
178 }
179
180 /// Print solution
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
195/** \brief Main-function
196 * \relates Nonogram
197 */
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
219 /** \name Picture specifications
220 *
221 * A specification is given by a list of integers. The first two
222 * integers (w and h) specify the number of columns and rows
223 * respectively. Then w + h groups of integers follows. Each group is
224 * started by the number of integers it contains (n), followed by n integers
225 * specifying the sizes of the stretches of markers in that row/column.
226 *
227 * \relates Nonogram
228 */
229 //@{
230 /// Specification for a heart-shaped picture.
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
255 /// Specification for a bear/bunny-shaped picture.
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
283 /// Specification for a crocodile-shaped picture
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
314 /// Specification for an unknown picture
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
341 /// Specification for a pinwheel-picture
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
360 /// Specification for a more difficult picture.
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
397 /// Specification for a non-unique picture
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
430 /** \brief Specification for a dragonfly-picture.
431 *
432 * From http://www.oberlin.edu/math/faculty/bosch/pbn-page.html, where
433 * it is claimed that it is hard.
434 */
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
481 /// From http://www.cs.kuleuven.be/~bmd/nonogram.pl
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
584 /** \brief Specification for a picture of cupid.
585 *
586 * From http://www.icparc.ic.ac.uk/eclipse/examples/nono.ecl.txt, the
587 * hardest instance.
588 */
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
649 /// Petro
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
731 /// Skid
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
777 /// Bucks
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
834 /// Dancer
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
856 /// Cat
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
903 /// Edge
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
931 /// Knot
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
1006 /// Swing
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
1104 /// Mum
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*);
1201 //@}
1202
1203}
1204
1205// STATISTICS: example-any