Generated on Sat Aug 25 2012 03:32:42 for Gecode by doxygen 1.8.1.2
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 Lagerkvist <lagerkvist@gecode.org>
5  *
6  * Copyright:
7  * Mikael Lagerkvist, 2005
8  *
9  * Last modified:
10  * $Date: 2010-10-07 20:52:01 +1100 (Thu, 07 Oct 2010) $ by $Author: schulte $
11  * $Revision: 11473 $
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 
42 
43 using namespace Gecode;
44 
45 namespace {
46 
48  extern const int* specs[];
50  extern const unsigned int n_examples;
51 
53  struct Slack {
54  int slack, n;
55  bool row;
56  bool operator<(const Slack& rhs) const { return slack < rhs.slack; }
57  };
58 }
59 
77 class Nonogram : public Script {
78 protected:
80  const int* spec;
83 
85  int width(void) const {
86  return spec[0];
87  }
89  int height(void) const {
90  return spec[1];
91  }
92 
94  DFA line(int& spos) {
95  REG r0(0), r1(1);
96  REG border = *r0;
97  REG between = +r0;
98  int hints = spec[spos++];
99  REG r = border;
100  if (hints > 0) {
101  r += r1(spec[spos],spec[spos]);
102  spos++;
103  for (int i=hints-1; i--; spos++)
104  r += between + r1(spec[spos],spec[spos]);
105  }
106  return r + border;
107  }
108 
109 public:
110  // Branching variants
111  enum {
114  };
115 
118  : spec(specs[opt.size()]), b(*this,width()*height(),0,1) {
119  Matrix<BoolVarArray> m(b, width(), height());
120 
121  {
122  int spos = 2;
123  // Post constraints for columns
124  for (int w=0; w<width(); w++)
125  extensional(*this, m.col(w), line(spos));
126  // Post constraints for rows
127  for (int h=0; h<height(); h++)
128  extensional(*this, m.row(h), line(spos));
129  }
130 
131 
132 
133  switch (opt.branching()) {
134  case BRANCH_NONE:
135  {
136  /*
137  * The following branches either by columns or rows, depending on
138  * whether there are more hints relative to the height or width
139  * for columns or rows.
140  *
141  * This idea is due to Pascal Van Hentenryck and has been suggested
142  * to us by Hakan Kjellerstrand.
143  */
144 
145  // Number of hints for columns
146  int cols = 0;
147  // Number of hints for rows
148  int rows = 0;
149  int spos = 2;
150  for (int w=0; w<width(); w++) {
151  int hint = spec[spos++];
152  cols += hint; spos += hint;
153  }
154  for (int h=0; h<height(); h++) {
155  int hint = spec[spos++];
156  rows += hint; spos += hint;
157  }
158 
159  if (rows*width() > cols*height()) {
160  for (int w=0; w<width(); w++)
161  branch(*this, m.col(w), INT_VAR_NONE, INT_VAL_MAX);
162  } else {
163  for (int h=0; h<height(); h++)
164  branch(*this, m.row(h), INT_VAR_NONE, INT_VAL_MAX);
165  }
166  }
167  break;
168  case BRANCH_AFC:
169  /*
170  * The following just uses the AFC for branching. This is
171  * equivalent to SIZE/AFC in this case since the variables are
172  * binary.
173  */
175  break;
176  }
177  }
178 
180  Nonogram(bool share, Nonogram& s) : Script(share,s), spec(s.spec) {
181  b.update(*this, share, s.b);
182  }
183 
185  virtual Space*
186  copy(bool share) {
187  return new Nonogram(share,*this);
188  }
189 
191  virtual void
192  print(std::ostream& os) const {
193  Matrix<BoolVarArray> m(b, width(), height());
194  for (int h = 0; h < height(); ++h) {
195  os << '\t';
196  for (int w = 0; w < width(); ++w)
197  os << ((m(w,h).val() == 1) ? '#' : ' ');
198  os << std::endl;
199  }
200  os << std::endl;
201  }
202 };
203 
204 
208 int
209 main(int argc, char* argv[]) {
210  SizeOptions opt("Nonogram");
211  opt.size(8);
213  opt.branching(Nonogram::BRANCH_NONE, "none",
214  "Branch on rows/columns in order");
215  opt.branching(Nonogram::BRANCH_AFC, "afc",
216  "Use AFC for branching");
217  opt.parse(argc,argv);
218  if (opt.size() >= n_examples) {
219  std::cerr << "Error: size must be between 0 and "
220  << n_examples-1 << std::endl;
221  return 1;
222  }
223  Script::run<Nonogram,DFS,SizeOptions>(opt);
224  return 0;
225 }
226 
227 namespace {
228 
240 
241 const int heart[] =
242  { 9, 9,
243  // Column constraints.
244  1, 3,
245  2, 2, 3,
246  2, 2, 2,
247  2, 2, 2,
248  2, 2, 2,
249  2, 2, 2,
250  2, 2, 2,
251  2, 2, 3,
252  1, 3,
253  // Row constraints
254  2, 2, 2,
255  2, 4, 4,
256  3, 1, 3, 1,
257  3, 2, 1, 2,
258  2, 1, 1,
259  2, 2, 2,
260  2, 2, 2,
261  1, 3,
262  1, 1
263  };
264 
266 const int bear[] =
267  { 13, 8,
268  // Column constraints
269  1, 2,
270  2, 2, 1,
271  2, 3, 2,
272  1, 6,
273  2, 1, 4,
274  1, 3,
275  1, 4,
276  1, 4,
277  1, 4,
278  1, 5,
279  1, 4,
280  2, 1, 3,
281  1, 2,
282  // Row constraints
283  1, 1,
284  1, 2,
285  2, 4, 4,
286  1, 12,
287  1, 8,
288  1, 9,
289  2, 3, 4,
290  2, 2, 2
291  };
292 
294 const int crocodile[] =
295  { 15, 9,
296  // Column constraints
297  1, 3,
298  1, 4,
299  2, 2, 2,
300  2, 3, 1,
301  2, 2, 3,
302  2, 3, 2,
303  2, 2, 3,
304  2, 4, 2,
305  2, 3, 2,
306  1, 6,
307  2, 1, 3,
308  2, 1, 3,
309  2, 1, 4,
310  1, 5,
311  1, 5,
312  // Row constraints
313  1, 3,
314  3, 2, 3, 2,
315  2, 10, 3,
316  1, 15,
317  5, 1, 1, 1, 1, 6,
318  2, 1, 7,
319  2, 1, 4,
320  2, 1, 4,
321  1, 4
322  };
323 
325 const int unknown[] =
326  { 10, 10,
327  // Column constraints
328  1, 3,
329  2, 2, 1,
330  2, 2, 2,
331  2, 2, 1,
332  3, 1, 2, 1,
333  2, 1, 1,
334  3, 1, 4, 1,
335  3, 1, 1, 2,
336  2, 3, 1,
337  1, 4,
338  // Row constraints
339  1, 3,
340  2, 2, 1,
341  2, 1, 1,
342  2, 1, 4,
343  4, 1, 1, 1, 1,
344  4, 2, 1, 1, 1,
345  3, 2, 1, 1,
346  2, 1, 2,
347  2, 2, 3,
348  1, 3
349  };
350 
352 const int pinwheel[] =
353  { 6, 6,
354  // Column constraints
355  2, 1, 2,
356  1, 1,
357  1, 2,
358  1, 2,
359  1, 1,
360  2, 2, 1,
361  // Row constraints
362  2, 2, 1,
363  1, 1,
364  1, 2,
365  1, 2,
366  1, 1,
367  2, 1, 2
368  };
369 
371 const int difficult[] =
372  { 15, 15,
373  // Column constraints
374  1, 3,
375  1, 2,
376  1, 2,
377  1, 1,
378  1, 2,
379  1, 3,
380  1, 2,
381  1, 4,
382  1, 3,
383  1, 4,
384  2, 2, 1,
385  2, 1, 1,
386  2, 1, 1,
387  2, 1, 1,
388  1, 3,
389  // Row constraints
390  1, 3,
391  2, 1, 1,
392  2, 1, 1,
393  2, 1, 1,
394  2, 1, 2,
395  1, 5,
396  1, 1,
397  1, 2,
398  1, 1,
399  1, 1,
400  2, 1, 2,
401  2, 1, 2,
402  2, 2, 1,
403  2, 2, 2,
404  1, 3
405  };
406 
408 const int non_unique[] =
409  { 11, 15,
410  // Column constraints
411  1, 5,
412  3, 1, 2, 4,
413  3, 2, 1, 3,
414  4, 2, 2, 1, 1,
415  4, 1, 1, 1, 1,
416  2, 1, 5,
417  5, 2, 1, 1, 3, 2,
418  5, 2, 1, 1, 1, 1,
419  3, 1, 4, 1,
420  2, 1, 1,
421  1, 1,
422  // Row constraints
423  2, 2, 2,
424  2, 2, 2,
425  1, 4,
426  2, 1, 1,
427  2, 1, 1,
428  4, 1, 1, 1, 1,
429  2, 1, 1,
430  2, 1, 4,
431  3, 1, 1, 1,
432  3, 1, 1, 4,
433  2, 1, 3,
434  2, 1, 2,
435  1, 5,
436  2, 2, 2,
437  2, 3, 3
438  };
439 
445  const int dragonfly[] =
446  { 20, 20,
447  // Column constraints.
448  4, 1, 1, 1, 2,
449  5, 3, 1, 2, 1, 1,
450  5, 1, 4, 2, 1, 1,
451  4, 1, 3, 2, 4,
452  4, 1, 4, 6, 1,
453  3, 1, 11, 1,
454  4, 5, 1, 6, 2,
455  1, 14,
456  2, 7, 2,
457  2, 7, 2,
458  3, 6, 1, 1,
459  2, 9, 2,
460  4, 3, 1, 1, 1,
461  3, 3, 1, 3,
462  3, 2, 1, 3,
463  3, 2, 1, 5,
464  3, 3, 2, 2,
465  3, 3, 3, 2,
466  3, 2, 3, 2,
467  2, 2, 6,
468  // Row constraints
469  2, 7, 1,
470  3, 1, 1, 2,
471  3, 2, 1, 2,
472  3, 1, 2, 2,
473  3, 4, 2, 3,
474  3, 3, 1, 4,
475  3, 3, 1, 3,
476  3, 2, 1, 4,
477  2, 2, 9,
478  3, 2, 1, 5,
479  2, 2, 7,
480  1, 14,
481  2, 8, 2,
482  3, 6, 2, 2,
483  4, 2, 8, 1, 3,
484  4, 1, 5, 5, 2,
485  5, 1, 3, 2, 4, 1,
486  5, 3, 1, 2, 4, 1,
487  5, 1, 1, 3, 1, 3,
488  4, 2, 1, 1, 2
489  };
490 
492  const int castle[] = {
493  60, 35,
494  // Column constraints
495  7, 2,3,1,5,1,7,1,
496  7, 2,4,2,3,2,3,5,
497  8, 2,6,3,1,1,5,1,5,
498  10, 2,4,2,1,1,1,4,1,1,2,
499  7, 2,8,2,1,5,2,5,
500  7, 3,1,6,2,5,1,5,
501  9, 3,3,3,1,1,6,1,1,1,
502  9, 3,2,2,2,2,8,1,1,3,
503  7, 1,4,4,3,7,1,1,
504  7, 1,2,2,2,3,7,9,
505  8, 1,2,3,1,1,5,2,2,
506  7, 2,2,3,1,1,6,1,
507  6, 1,3,1,5,4,1,
508  8, 1,3,1,1,6,1,3,1,
509  8, 3,3,4,5,1,4,2,1,
510  6, 2,3,3,9,7,1,
511  8, 2,3,2,2,1,1,3,5,
512  8, 4,2,1,1,1,1,2,3,
513  7, 4,2,2,1,4,3,2,
514  4, 4,3,16,2,
515  5, 1,2,5,7,1,
516  6, 4,3,2,2,7,1,
517  5, 2,3,1,10,1,
518  6, 2,4,2,1,4,1,
519  5, 1,6,7,3,1,
520  4, 3,11,3,1,
521  5, 7,1,11,2,1,
522  7, 2,2,2,2,2,2,2,
523  7, 3,1,1,1,1,2,1,
524  7, 2,2,2,2,1,1,1,
525  7, 1,1,1,1,2,1,2,
526  8, 2,2,2,2,1,1,1,1,
527  5, 4,1,1,2,2,
528  5, 5,2,17,2,1,
529  6, 9,2,3,1,4,2,
530  6, 9,4,2,1,1,1,
531  5, 5,4,2,1,4,
532  7, 11,1,2,1,4,1,2,
533  5, 3,4,2,4,4,
534  8, 2,1,4,1,2,1,5,2,
535  5, 8,4,1,1,2,
536  5, 1,1,3,2,3,
537  6, 1,3,1,8,1,6,
538  4, 2,1,7,14,
539  7, 1,2,4,4,1,2,3,
540  10, 1,1,4,2,1,1,1,1,1,4,
541  6, 3,5,3,1,1,4,
542  6, 2,4,2,2,1,2,
543  5, 4,2,3,8,4,
544  5, 4,15,2,2,4,
545  6, 4,1,10,2,1,2,
546  6, 2,12,6,1,2,4,
547  7, 3,1,3,1,3,3,4,
548  6, 3,1,2,3,4,1,
549  7, 5,2,2,2,3,3,3,
550  9, 1,2,2,2,2,4,1,1,3,
551  7, 2,1,4,2,7,1,1,
552  6, 5,2,2,3,6,3,
553  7, 3,3,2,2,3,2,3,
554  7, 4,1,2,1,1,2,1,
555 
556  // Row constraints
557  4, 12,1,1,1,
558  5, 8,6,3,1,3,
559  6, 5,8,4,3,1,5,
560  8, 7,3,4,1,3,5,1,7,
561  13, 2,2,4,9,1,5,1,1,1,1,1,1,1,
562  8, 4,5,10,2,1,8,7,1,
563  7, 5,1,3,3,16,1,2,
564  8, 8,5,1,2,4,9,1,3,
565  12, 4,5,3,14,1,1,1,1,4,1,1,3,
566  19, 3,3,2,2,2,4,1,1,1,1,1,1,1,1,3,1,1,3,2,
567  11, 8,2,7,2,1,1,2,1,1,3,3,
568  13, 1,5,9,12,2,1,1,3,1,1,2,2,1,
569  17, 3,2,2,1,1,1,1,4,1,1,1,3,3,1,1,2,2,
570  12, 5,2,2,2,2,1,5,2,1,1,2,5,
571  12, 3,5,9,2,1,1,6,3,1,3,2,3,
572  12, 1,4,1,1,1,4,1,5,5,3,3,3,
573  10, 4,1,1,1,1,3,4,6,6,3,
574  12, 3,1,3,1,1,3,3,1,1,4,6,1,
575  11, 3,1,5,1,1,3,1,1,9,4,1,
576  14, 2,1,1,7,1,4,1,1,1,1,1,1,3,5,
577  11, 9,2,1,3,1,1,1,1,4,2,1,
578  10, 1,14,1,1,2,2,2,10,1,2,
579  10, 1,9,2,1,2,6,1,5,3,2,
580  12, 1,9,9,1,2,2,3,1,1,4,3,1,
581  10, 10,1,3,4,1,3,2,1,2,8,
582  9, 9,1,3,5,1,1,1,2,7,
583  12, 4,5,1,2,5,1,3,1,1,2,1,3,
584  14, 1,1,1,1,2,6,2,3,2,1,1,2,3,1,
585  11, 1,6,1,5,7,1,3,3,2,4,3,
586  10, 1,2,1,2,9,1,5,2,6,2,
587  8, 10,2,2,13,1,3,3,1,
588  11, 2,2,1,6,2,3,3,2,2,2,1,
589  12, 2,2,1,1,12,2,2,9,2,2,2,2,
590  9, 5,1,2,4,1,5,11,2,2,
591  3, 15,6,18,
592  };
593 
599  const int p200[] =
600  { 25, 25,
601  // Column constraints
602  4, 1,1,2,2,
603  3, 5,5,7,
604  4, 5,2,2,9,
605  4, 3,2,3,9,
606  5, 1,1,3,2,7,
607  3, 3,1,5,
608  5, 7,1,1,1,3,
609  6, 1,2,1,1,2,1,
610  3, 4,2,4,
611  4, 1,2,2,2,
612  3, 4,6,2,
613  4, 1,2,2,1,
614  4, 3,3,2,1,
615  3, 4,1,15,
616  6, 1,1,1,3,1,1,
617  6, 2,1,1,2,2,3,
618  4, 1,4,4,1,
619  4, 1,4,3,2,
620  4, 1,1,2,2,
621  5, 7,2,3,1,1,
622  5, 2,1,1,1,5,
623  3, 1,2,5,
624  4, 1,1,1,3,
625  3, 4,2,1,
626  1, 3,
627  // Row constraints
628  3, 2,2,3,
629  5, 4,1,1,1,4,
630  5, 4,1,2,1,1,
631  7, 4,1,1,1,1,1,1,
632  6, 2,1,1,2,3,5,
633  6, 1,1,1,1,2,1,
634  5, 3,1,5,1,2,
635  6, 3,2,2,1,2,2,
636  7, 2,1,4,1,1,1,1,
637  6, 2,2,1,2,1,2,
638  6, 1,1,1,3,2,3,
639  5, 1,1,2,7,3,
640  5, 1,2,2,1,5,
641  5, 3,2,2,1,2,
642  4, 3,2,1,2,
643  3, 5,1,2,
644  4, 2,2,1,2,
645  4, 4,2,1,2,
646  4, 6,2,3,2,
647  4, 7,4,3,2,
648  3, 7,4,4,
649  3, 7,1,4,
650  3, 6,1,4,
651  3, 4,2,2,
652  2, 2,1
653  };
654 
655  // The following instances are from the http://webpbn.com site and
656  // are all designed by Jan Wolter.
657  // See also the survey at http://webpbn.com/survey/
658 
660  const int webpbn436[]=
661  { 40, 35,
662  // Column constraints
663  1, 1,
664  2, 3, 2,
665  3, 2, 3, 3,
666  3, 3, 3, 3,
667  4, 3, 3, 3, 3,
668  4, 4, 2, 2, 2,
669  4, 3, 3, 2, 3,
670  4, 3, 2, 2, 2,
671  3, 3, 2, 6,
672  2, 2, 9,
673  3, 2, 3, 3,
674  5, 4, 4, 3, 2, 4,
675  5, 7, 2, 5, 2, 6,
676  6, 12, 2, 3, 2, 3, 2,
677  6, 3, 1, 2, 2, 2, 3,
678  6, 2, 2, 3, 2, 2, 2,
679  6, 6, 2, 6, 2, 2, 2,
680  5, 12, 4, 3, 2, 2,
681  4, 12, 2, 2, 2,
682  3, 2, 6, 2,
683  4, 2, 6, 5, 2,
684  4, 10, 9, 2, 2,
685  5, 12, 3, 3, 2, 2,
686  7, 6, 2, 2, 2, 2, 2, 2,
687  6, 2, 2, 3, 2, 2, 2,
688  6, 4, 3, 2, 2, 2, 3,
689  6, 7, 3, 3, 2, 3, 2,
690  5, 5, 3, 5, 2, 6,
691  5, 4, 3, 3, 3, 4,
692  3, 3, 5, 3,
693  2, 3, 9,
694  3, 4, 2, 6,
695  4, 4, 2, 2, 2,
696  4, 4, 2, 2, 3,
697  4, 3, 2, 2, 3,
698  3, 3, 3, 3,
699  3, 3, 3, 3,
700  3, 4, 3, 3,
701  3, 2, 3, 3,
702  2, 2, 1,
703  // Row constraints
704  2, 2, 2,
705  3, 2, 3, 2,
706  4, 3, 3, 3, 2,
707  4, 3, 3, 3, 3,
708  6, 2, 3, 3, 3, 3, 2,
709  6, 3, 3, 3, 3, 3, 3,
710  6, 4, 2, 3, 2, 2, 4,
711  7, 4, 2, 2, 2, 2, 3, 1,
712  7, 3, 1, 2, 2, 2, 3, 3,
713  7, 3, 2, 2, 2, 2, 2, 4,
714  5, 3, 2, 15, 2, 4,
715  3, 5, 19, 4,
716  4, 6, 4, 3, 3,
717  3, 6, 4, 4,
718  4, 2, 4, 6, 2,
719  6, 2, 2, 3, 3, 3, 2,
720  6, 9, 2, 2, 2, 3, 9,
721  7, 10, 2, 2, 2, 2, 2, 10,
722  9, 4, 2, 3, 3, 2, 2, 3, 2, 5,
723  5, 2, 5, 2, 4, 2,
724  5, 5, 3, 2, 2, 5,
725  5, 6, 3, 2, 3, 7,
726  4, 6, 8, 9, 7,
727  4, 4, 8, 7, 5,
728  1, 4,
729  1, 2,
730  1, 2,
731  1, 14,
732  1, 16,
733  2, 3, 3,
734  2, 2, 2,
735  2, 2, 2,
736  2, 4, 4,
737  1, 16,
738  1, 12,
739  };
740 
742  const int webpbn21[]=
743  { 14, 25,
744  // Column constraints
745  1, 2,
746  2, 4, 6,
747  4, 9, 4, 4, 2,
748  4, 1, 6, 2, 6,
749  3, 1, 5, 2,
750  2, 1, 6,
751  2, 1, 5,
752  2, 1, 4,
753  2, 1, 4,
754  3, 1, 4, 2,
755  3, 1, 4, 6,
756  5, 1, 6, 4, 4, 2,
757  3, 9, 2, 6,
758  2, 4, 2,
759  // Row constraints
760  1, 9,
761  2, 1, 1,
762  3, 1, 1, 1,
763  3, 1, 3, 1,
764  1, 13,
765  1, 13,
766  1, 13,
767  1, 13,
768  2, 2, 2,
769  2, 2, 2,
770  0,
771  2, 2, 2,
772  2, 2, 2,
773  2, 2, 2,
774  2, 2, 2,
775  2, 2, 2,
776  2, 2, 2,
777  2, 2, 2,
778  2, 2, 2,
779  2, 2, 2,
780  2, 2, 2,
781  2, 2, 2,
782  2, 2, 2,
783  2, 2, 2,
784  2, 2, 2,
785  };
786 
788 const int webpbn27[]=
789  { 27, 23,
790  // Column constraints
791  2, 4, 12,
792  3, 6, 1, 1,
793  3, 8, 1, 1,
794  5, 3, 2, 2, 1, 1,
795  6, 2, 1, 1, 2, 1, 6,
796  4, 1, 1, 1, 1,
797  6, 3, 1, 1, 2, 1, 1,
798  5, 3, 2, 3, 1, 1,
799  3, 10, 1, 1,
800  5, 4, 2, 2, 1, 1,
801  6, 3, 1, 1, 2, 1, 1,
802  4, 2, 1, 1, 1,
803  6, 3, 1, 1, 2, 1, 1,
804  5, 3, 2, 3, 1, 6,
805  3, 10, 1, 1,
806  5, 4, 2, 2, 1, 1,
807  6, 3, 1, 1, 2, 1, 1,
808  4, 1, 1, 1, 9,
809  6, 2, 1, 1, 2, 1, 1,
810  5, 2, 2, 3, 1, 3,
811  3, 8, 1, 5,
812  3, 6, 1, 1,
813  3, 4, 9, 1,
814  2, 1, 1,
815  2, 2, 1,
816  2, 1, 1,
817  1, 4,
818  // Row constraints
819  1, 11,
820  1, 17,
821  4, 3, 5, 5, 3,
822  4, 2, 2, 2, 1,
823  7, 2, 1, 3, 1, 3, 1, 4,
824  4, 3, 3, 3, 3,
825  7, 5, 1, 3, 1, 3, 1, 3,
826  4, 3, 2, 2, 4,
827  4, 5, 5, 5, 5,
828  1, 23,
829  0,
830  1, 23,
831  2, 1, 1,
832  2, 1, 1,
833  3, 1, 2, 1,
834  4, 1, 1, 1, 1,
835  4, 1, 1, 1, 1,
836  5, 1, 10, 1, 2, 1,
837  7, 1, 1, 1, 1, 1, 1, 3,
838  8, 1, 1, 1, 1, 1, 1, 1, 1,
839  7, 1, 1, 1, 1, 1, 1, 1,
840  6, 1, 1, 1, 1, 2, 2,
841  3, 5, 5, 3,
842  };
843 
845  const int webpbn1[]=
846  { 5, 10,
847  // Column constraints
848  2, 2, 1,
849  3, 2, 1, 3,
850  1, 7,
851  2, 1, 3,
852  2, 2, 1,
853  // Row constraints
854  1, 2,
855  2, 2, 1,
856  2, 1, 1,
857  1, 3,
858  2, 1, 1,
859  2, 1, 1,
860  1, 2,
861  2, 1, 1,
862  2, 1, 2,
863  1, 2,
864  };
865 
867  const int webpbn6[]=
868  { 20, 20,
869  // Column constraints
870  1, 5,
871  2, 5, 3,
872  3, 2, 3, 4,
873  3, 1, 7, 2,
874  1, 8,
875  1, 9,
876  1, 9,
877  1, 8,
878  1, 7,
879  1, 8,
880  1, 9,
881  1, 10,
882  1, 13,
883  2, 6, 2,
884  1, 4,
885  1, 6,
886  1, 6,
887  1, 5,
888  1, 6,
889  1, 6,
890  // Row constraints
891  1, 2,
892  1, 2,
893  1, 1,
894  1, 1,
895  2, 1, 3,
896  2, 2, 5,
897  4, 1, 7, 1, 1,
898  4, 1, 8, 2, 2,
899  3, 1, 9, 5,
900  2, 2, 16,
901  2, 1, 17,
902  2, 7, 11,
903  3, 5, 5, 3,
904  2, 5, 4,
905  2, 3, 3,
906  2, 2, 2,
907  2, 2, 1,
908  2, 1, 1,
909  2, 2, 2,
910  2, 2, 2,
911  };
912 
914  const int webpbn23[]=
915  { 10, 11,
916  // Column constraints
917  1, 1,
918  1, 3,
919  1, 1,
920  2, 2, 2,
921  1, 2,
922  1, 4,
923  1, 1,
924  1, 3,
925  1, 3,
926  1, 1,
927  // Row constraints
928  1, 1,
929  1, 3,
930  1, 1,
931  1, 2,
932  1, 1,
933  1, 3,
934  1, 3,
935  1, 1,
936  1, 2,
937  1, 2,
938  1, 4,
939  };
940 
942 const int webpbn16[]=
943  { 34, 34,
944  // Column constraints
945  2, 1, 1,
946  2, 2, 2,
947  2, 3, 3,
948  4, 2, 1, 1, 2,
949  4, 2, 1, 1, 2,
950  4, 1, 1, 1, 1,
951  4, 1, 1, 1, 1,
952  1, 18,
953  6, 2, 1, 1, 1, 1, 2,
954  6, 1, 1, 1, 1, 1, 1,
955  6, 1, 1, 1, 1, 1, 1,
956  1, 26,
957  8, 2, 1, 1, 1, 1, 1, 1, 2,
958  8, 2, 1, 1, 2, 2, 1, 1, 2,
959  8, 2, 1, 1, 2, 2, 1, 1, 2,
960  2, 14, 14,
961  4, 1, 1, 1, 1,
962  4, 1, 1, 1, 1,
963  2, 14, 14,
964  8, 2, 1, 1, 2, 2, 1, 1, 2,
965  8, 2, 1, 1, 2, 2, 1, 1, 2,
966  8, 2, 1, 1, 1, 1, 1, 1, 2,
967  1, 26,
968  6, 1, 1, 1, 1, 1, 1,
969  6, 1, 1, 1, 1, 1, 1,
970  6, 2, 1, 1, 1, 1, 2,
971  1, 18,
972  4, 1, 1, 1, 1,
973  4, 1, 1, 1, 1,
974  4, 2, 1, 1, 2,
975  4, 2, 1, 1, 2,
976  2, 3, 3,
977  2, 2, 2,
978  2, 1, 1,
979  // Row constraints
980  2, 1, 1,
981  2, 2, 2,
982  2, 3, 3,
983  4, 2, 1, 1, 2,
984  4, 2, 1, 1, 2,
985  4, 1, 1, 1, 1,
986  4, 1, 1, 1, 1,
987  1, 18,
988  6, 2, 1, 1, 1, 1, 2,
989  6, 1, 1, 1, 1, 1, 1,
990  6, 1, 1, 1, 1, 1, 1,
991  1, 26,
992  8, 2, 1, 1, 1, 1, 1, 1, 2,
993  8, 2, 1, 1, 2, 2, 1, 1, 2,
994  8, 2, 1, 1, 2, 2, 1, 1, 2,
995  2, 14, 14,
996  4, 1, 1, 1, 1,
997  4, 1, 1, 1, 1,
998  2, 14, 14,
999  8, 2, 1, 1, 2, 2, 1, 1, 2,
1000  8, 2, 1, 1, 2, 2, 1, 1, 2,
1001  8, 2, 1, 1, 1, 1, 1, 1, 2,
1002  1, 26,
1003  6, 1, 1, 1, 1, 1, 1,
1004  6, 1, 1, 1, 1, 1, 1,
1005  6, 2, 1, 1, 1, 1, 2,
1006  1, 18,
1007  4, 1, 1, 1, 1,
1008  4, 1, 1, 1, 1,
1009  4, 2, 1, 1, 2,
1010  4, 2, 1, 1, 2,
1011  2, 3, 3,
1012  2, 2, 2,
1013  2, 1, 1,
1014  };
1015 
1017  const int webpbn529[]=
1018  { 45, 45,
1019  // Column constraints
1020  6, 7, 1, 1, 1, 1, 1,
1021  13, 2, 2, 4, 1, 4, 1, 5, 1, 4, 1, 4, 1, 2,
1022  10, 3, 1, 4, 1, 4, 1, 14, 4, 1, 2,
1023  8, 1, 1, 5, 1, 2, 3, 4, 1,
1024  4, 3, 13, 1, 10,
1025  3, 1, 9, 4,
1026  4, 6, 7, 2, 2,
1027  4, 8, 4, 1, 4,
1028  6, 2, 8, 3, 2, 5, 3,
1029  5, 10, 1, 3, 7, 2,
1030  6, 8, 6, 2, 8, 1, 2,
1031  7, 1, 1, 2, 2, 8, 1, 1,
1032  11, 2, 1, 1, 1, 2, 1, 3, 1, 3, 3, 1,
1033  8, 2, 1, 1, 1, 5, 4, 2, 1,
1034  8, 2, 1, 1, 1, 1, 7, 2, 1,
1035  8, 2, 1, 1, 2, 9, 1, 2, 1,
1036  5, 4, 6, 12, 1, 3,
1037  4, 16, 13, 3, 2,
1038  3, 12, 21, 2,
1039  3, 2, 13, 23,
1040  3, 2, 14, 19,
1041  4, 2, 14, 20, 2,
1042  6, 2, 13, 7, 2, 8, 2,
1043  5, 12, 8, 1, 7, 2,
1044  9, 5, 1, 1, 1, 2, 8, 1, 5, 2,
1045  8, 2, 1, 1, 1, 9, 1, 1, 4,
1046  8, 2, 1, 1, 1, 6, 1, 3, 5,
1047  6, 2, 2, 1, 5, 6, 2,
1048  8, 2, 1, 3, 1, 3, 7, 3, 2,
1049  9, 2, 3, 2, 1, 1, 2, 4, 4, 2,
1050  9, 2, 2, 1, 1, 2, 3, 1, 8, 2,
1051  5, 9, 3, 1, 7, 2,
1052  5, 12, 4, 1, 6, 2,
1053  5, 7, 4, 1, 2, 5,
1054  5, 2, 6, 6, 5, 6,
1055  4, 8, 8, 6, 3,
1056  5, 3, 10, 8, 4, 2,
1057  5, 5, 11, 9, 5, 2,
1058  5, 3, 1, 12, 16, 2,
1059  4, 3, 1, 12, 16,
1060  4, 5, 2, 13, 21,
1061  6, 6, 1, 3, 3, 1, 1,
1062  14, 5, 1, 3, 1, 3, 1, 1, 2, 1, 4, 1, 3, 1, 3,
1063  13, 5, 1, 3, 1, 3, 1, 4, 1, 4, 1, 3, 1, 3,
1064  6, 1, 1, 1, 1, 1, 1,
1065  // Row constraints
1066  6, 7, 1, 1, 1, 1, 1,
1067  13, 3, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
1068  14, 1, 1, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
1069  9, 2, 1, 2, 1, 1, 1, 1, 6, 2,
1070  4, 3, 30, 1, 5,
1071  9, 1, 5, 8, 1, 1, 7, 1, 1, 3,
1072  7, 3, 4, 8, 1, 5, 1, 2,
1073  4, 3, 20, 6, 6,
1074  6, 3, 3, 7, 2, 5, 1,
1075  9, 3, 3, 1, 1, 9, 1, 1, 5, 6,
1076  7, 2, 3, 8, 1, 3, 4, 2,
1077  7, 5, 3, 1, 10, 4, 5, 2,
1078  6, 1, 2, 3, 8, 4, 6,
1079  5, 2, 2, 3, 11, 10,
1080  5, 2, 2, 3, 10, 7,
1081  6, 2, 3, 1, 7, 12, 2,
1082  6, 2, 3, 1, 4, 11, 2,
1083  6, 4, 1, 2, 1, 11, 2,
1084  4, 9, 1, 2, 9,
1085  5, 6, 2, 1, 4, 11,
1086  6, 2, 5, 1, 2, 6, 6,
1087  5, 6, 2, 4, 8, 4,
1088  4, 4, 2, 16, 1,
1089  4, 2, 2, 15, 2,
1090  4, 3, 2, 15, 4,
1091  4, 3, 3, 13, 4,
1092  3, 4, 12, 9,
1093  3, 1, 9, 10,
1094  5, 2, 1, 17, 7, 2,
1095  6, 2, 2, 8, 3, 8, 2,
1096  6, 2, 3, 6, 3, 8, 2,
1097  6, 2, 4, 5, 4, 7, 2,
1098  5, 2, 5, 5, 4, 6,
1099  5, 4, 4, 5, 4, 9,
1100  5, 1, 4, 6, 4, 4,
1101  6, 4, 3, 6, 4, 3, 2,
1102  7, 2, 1, 2, 7, 4, 4, 2,
1103  7, 2, 2, 2, 9, 5, 5, 2,
1104  6, 2, 2, 2, 10, 6, 6,
1105  5, 3, 2, 1, 9, 18,
1106  3, 8, 4, 23,
1107  9, 1, 2, 1, 2, 2, 1, 1, 1, 2,
1108  12, 2, 1, 4, 2, 1, 4, 1, 5, 1, 3, 1, 2,
1109  11, 2, 1, 5, 4, 4, 1, 5, 1, 3, 1, 2,
1110  5, 1, 10, 1, 1, 1,
1111  };
1112 
1113 
1115  const int webpbn65[]=
1116  { 34, 40,
1117  // Column constraints
1118  1, 5,
1119  3, 3, 2, 1,
1120  4, 3, 2, 2, 1,
1121  5, 3, 2, 2, 2, 2,
1122  6, 3, 2, 2, 2, 2, 3,
1123  7, 1, 2, 2, 2, 2, 2, 16,
1124  9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
1125  9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
1126  10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
1127  9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
1128  11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
1129  12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
1130  11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
1131  6, 1, 7, 2, 16, 1, 1,
1132  11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1133  11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
1134  9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
1135  9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
1136  11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
1137  11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1138  6, 1, 7, 2, 16, 1, 1,
1139  11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
1140  12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
1141  11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
1142  9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
1143  10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
1144  9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
1145  9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
1146  7, 1, 2, 2, 2, 2, 2, 16,
1147  6, 3, 2, 2, 2, 2, 3,
1148  5, 3, 2, 2, 2, 2,
1149  4, 3, 2, 2, 1,
1150  3, 3, 2, 1,
1151  1, 5,
1152  // Row constraints
1153  1, 12,
1154  3, 5, 2, 5,
1155  4, 5, 2, 2, 5,
1156  7, 1, 2, 2, 2, 2, 2, 1,
1157  7, 4, 2, 2, 4, 2, 2, 4,
1158  7, 4, 2, 2, 4, 2, 2, 4,
1159  7, 1, 2, 2, 2, 2, 2, 1,
1160  7, 6, 2, 2, 2, 2, 2, 6,
1161  7, 6, 2, 2, 2, 2, 2, 6,
1162  3, 1, 14, 1,
1163  2, 10, 10,
1164  4, 8, 3, 3, 8,
1165  8, 1, 1, 2, 1, 1, 2, 1, 1,
1166  6, 9, 2, 2, 2, 2, 9,
1167  2, 9, 9,
1168  6, 1, 1, 1, 1, 1, 1,
1169  3, 12, 2, 12,
1170  2, 12, 12,
1171  5, 1, 1, 4, 1, 1,
1172  2, 14, 14,
1173  2, 12, 12,
1174  5, 2, 1, 4, 1, 2,
1175  3, 9, 4, 9,
1176  5, 1, 7, 4, 7, 1,
1177  7, 1, 1, 1, 4, 1, 1, 1,
1178  5, 1, 7, 4, 7, 1,
1179  5, 1, 7, 4, 7, 1,
1180  7, 1, 2, 1, 2, 1, 2, 1,
1181  5, 1, 7, 2, 7, 1,
1182  7, 1, 1, 6, 2, 6, 1, 1,
1183  9, 1, 1, 1, 1, 2, 1, 1, 1, 1,
1184  7, 1, 1, 6, 2, 6, 1, 1,
1185  6, 1, 1, 5, 5, 1, 1,
1186  7, 1, 1, 1, 8, 1, 1, 1,
1187  6, 1, 1, 4, 4, 1, 1,
1188  5, 1, 2, 6, 2, 1,
1189  4, 2, 4, 4, 2,
1190  3, 2, 6, 2,
1191  2, 4, 4,
1192  1, 6,
1193  };
1194 
1195 
1196  const int *specs[] = {heart, bear, crocodile, unknown,
1197  pinwheel, difficult, non_unique, dragonfly,
1198  castle, p200,
1199  // From the webpbn survey
1200  webpbn1, // 10
1201  webpbn6, // 11
1202  webpbn21, // 12
1203  webpbn27, // 13
1204  webpbn23, // 14
1205  webpbn16, // 15
1206  webpbn529, // 16
1207  webpbn65, // 17
1208  webpbn436, // 18
1209  };
1210  const unsigned n_examples = sizeof(specs)/sizeof(int*);
1212 
1213 }
1214 
1215 // STATISTICS: example-any