Generated on Fri Oct 19 11:24:49 2018 for Gecode by doxygen 1.6.3

nonogram.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Mikael Lagerkvist, 2005
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/driver.hh>
00035 #include <gecode/int.hh>
00036 #include <gecode/minimodel.hh>
00037 
00038 
00039 using namespace Gecode;
00040 
00041 namespace {
00042 
00044   extern const int* specs[];
00046   extern const unsigned int n_examples;
00047 
00048 }
00049 
00067 class Nonogram : public Script {
00068 protected:
00070   const int* spec;
00072   BoolVarArray b;
00073 
00075   int width(void) const {
00076     return spec[0];
00077   }
00079   int height(void) const {
00080     return spec[1];
00081   }
00082 
00084   DFA line(int& spos) {
00085     REG r0(0), r1(1);
00086     REG border = *r0;
00087     REG between = +r0;
00088     int hints = spec[spos++];
00089     REG r = border;
00090     if (hints > 0) {
00091       r += r1(spec[spos],spec[spos]);
00092       spos++;
00093       for (int i=hints-1; i--; spos++)
00094         r += between + r1(spec[spos],spec[spos]);
00095     }
00096     return r + border;
00097   }
00098 
00099 public:
00100   // Branching variants
00101   enum {
00102     BRANCH_NONE, 
00103     BRANCH_AFC,  
00104   };
00105 
00107   Nonogram(const SizeOptions& opt)
00108     : Script(opt), spec(specs[opt.size()]), b(*this,width()*height(),0,1) {
00109     Matrix<BoolVarArray> m(b, width(), height());
00110 
00111     {
00112       int spos = 2;
00113       // Post constraints for columns
00114       for (int w=0; w<width(); w++)
00115         extensional(*this, m.col(w), line(spos));
00116       // Post constraints for rows
00117       for (int h=0; h<height(); h++)
00118         extensional(*this, m.row(h), line(spos));
00119     }
00120 
00121 
00122 
00123     switch (opt.branching()) {
00124     case BRANCH_NONE:
00125       {
00126         /*
00127          * The following branches either by columns or rows, depending on
00128          * whether there are more hints relative to the height or width
00129          * for columns or rows.
00130          *
00131          * This idea is due to Pascal Van Hentenryck and has been suggested
00132          * to us by Hakan Kjellerstrand.
00133          */
00134 
00135         // Number of hints for columns
00136         int cols = 0;
00137         // Number of hints for rows
00138         int rows = 0;
00139         int spos = 2;
00140         for (int w=0; w<width(); w++) {
00141           int hint = spec[spos++];
00142           cols += hint; spos += hint;
00143         }
00144         for (int h=0; h<height(); h++) {
00145           int hint = spec[spos++];
00146           rows += hint; spos += hint;
00147         }
00148 
00149         if (rows*width() > cols*height()) {
00150           for (int w=0; w<width(); w++)
00151             branch(*this, m.col(w), BOOL_VAR_NONE(), BOOL_VAL_MAX());
00152         } else {
00153           for (int h=0; h<height(); h++)
00154             branch(*this, m.row(h), BOOL_VAR_NONE(), BOOL_VAL_MAX());
00155         }
00156       }
00157       break;
00158     case BRANCH_AFC:
00159       /*
00160        * The following just uses the AFC for branching. This is
00161        * equivalent to SIZE/AFC in this case since the variables are
00162        * binary.
00163        */
00164       branch(*this, b, BOOL_VAR_AFC_MAX(opt.decay()), BOOL_VAL_MAX());
00165       break;
00166     }
00167   }
00168 
00170   Nonogram(Nonogram& s) : Script(s), spec(s.spec) {
00171     b.update(*this, s.b);
00172   }
00173 
00175   virtual Space*
00176   copy(void) {
00177     return new Nonogram(*this);
00178   }
00179 
00181   virtual void
00182   print(std::ostream& os) const {
00183     Matrix<BoolVarArray> m(b, width(), height());
00184     for (int h = 0; h < height(); ++h) {
00185       os << '\t';
00186       for (int w = 0; w < width(); ++w)
00187         os << ((m(w,h).val() == 1) ? '#' : ' ');
00188       os << std::endl;
00189     }
00190     os << std::endl;
00191   }
00192 };
00193 
00194 
00198 int
00199 main(int argc, char* argv[]) {
00200   SizeOptions opt("Nonogram");
00201   opt.size(8);
00202   opt.branching(Nonogram::BRANCH_AFC);
00203   opt.branching(Nonogram::BRANCH_NONE, "none",
00204                 "Branch on rows/columns in order");
00205   opt.branching(Nonogram::BRANCH_AFC, "afc",
00206                 "Use AFC for branching");
00207   opt.parse(argc,argv);
00208   if (opt.size() >= n_examples) {
00209     std::cerr << "Error: size must be between 0 and "
00210               << n_examples-1 << std::endl;
00211     return 1;
00212   }
00213   Script::run<Nonogram,DFS,SizeOptions>(opt);
00214   return 0;
00215 }
00216 
00217 namespace {
00218 
00230 
00231 const int heart[] =
00232   { 9, 9,
00233     // Column constraints.
00234     1, 3,
00235     2, 2, 3,
00236     2, 2, 2,
00237     2, 2, 2,
00238     2, 2, 2,
00239     2, 2, 2,
00240     2, 2, 2,
00241     2, 2, 3,
00242     1, 3,
00243     // Row constraints
00244     2, 2, 2,
00245     2, 4, 4,
00246     3, 1, 3, 1,
00247     3, 2, 1, 2,
00248     2, 1, 1,
00249     2, 2, 2,
00250     2, 2, 2,
00251     1, 3,
00252     1, 1
00253   };
00254 
00256 const int bear[] =
00257   { 13, 8,
00258     // Column constraints
00259     1, 2,
00260     2, 2, 1,
00261     2, 3, 2,
00262     1, 6,
00263     2, 1, 4,
00264     1, 3,
00265     1, 4,
00266     1, 4,
00267     1, 4,
00268     1, 5,
00269     1, 4,
00270     2, 1, 3,
00271     1, 2,
00272     // Row constraints
00273     1, 1,
00274     1, 2,
00275     2, 4, 4,
00276     1, 12,
00277     1, 8,
00278     1, 9,
00279     2, 3, 4,
00280     2, 2, 2
00281   };
00282 
00284 const int crocodile[] =
00285   { 15, 9,
00286     // Column constraints
00287     1, 3,
00288     1, 4,
00289     2, 2, 2,
00290     2, 3, 1,
00291     2, 2, 3,
00292     2, 3, 2,
00293     2, 2, 3,
00294     2, 4, 2,
00295     2, 3, 2,
00296     1, 6,
00297     2, 1, 3,
00298     2, 1, 3,
00299     2, 1, 4,
00300     1, 5,
00301     1, 5,
00302     // Row constraints
00303     1, 3,
00304     3, 2, 3, 2,
00305     2, 10, 3,
00306     1, 15,
00307     5, 1, 1, 1, 1, 6,
00308     2, 1, 7,
00309     2, 1, 4,
00310     2, 1, 4,
00311     1, 4
00312   };
00313 
00315 const int unknown[] =
00316   { 10, 10,
00317     // Column constraints
00318     1, 3,
00319     2, 2, 1,
00320     2, 2, 2,
00321     2, 2, 1,
00322     3, 1, 2, 1,
00323     2, 1, 1,
00324     3, 1, 4, 1,
00325     3, 1, 1, 2,
00326     2, 3, 1,
00327     1, 4,
00328     // Row constraints
00329     1, 3,
00330     2, 2, 1,
00331     2, 1, 1,
00332     2, 1, 4,
00333     4, 1, 1, 1, 1,
00334     4, 2, 1, 1, 1,
00335     3, 2, 1, 1,
00336     2, 1, 2,
00337     2, 2, 3,
00338     1, 3
00339   };
00340 
00342 const int pinwheel[] =
00343   { 6, 6,
00344     // Column constraints
00345     2, 1, 2,
00346     1, 1,
00347     1, 2,
00348     1, 2,
00349     1, 1,
00350     2, 2, 1,
00351     // Row constraints
00352     2, 2, 1,
00353     1, 1,
00354     1, 2,
00355     1, 2,
00356     1, 1,
00357     2, 1, 2
00358   };
00359 
00361 const int difficult[] =
00362   { 15, 15,
00363     // Column constraints
00364     1, 3,
00365     1, 2,
00366     1, 2,
00367     1, 1,
00368     1, 2,
00369     1, 3,
00370     1, 2,
00371     1, 4,
00372     1, 3,
00373     1, 4,
00374     2, 2, 1,
00375     2, 1, 1,
00376     2, 1, 1,
00377     2, 1, 1,
00378     1, 3,
00379     // Row constraints
00380     1, 3,
00381     2, 1, 1,
00382     2, 1, 1,
00383     2, 1, 1,
00384     2, 1, 2,
00385     1, 5,
00386     1, 1,
00387     1, 2,
00388     1, 1,
00389     1, 1,
00390     2, 1, 2,
00391     2, 1, 2,
00392     2, 2, 1,
00393     2, 2, 2,
00394     1, 3
00395   };
00396 
00398 const int non_unique[] =
00399   { 11, 15,
00400     // Column constraints
00401     1, 5,
00402     3, 1, 2, 4,
00403     3, 2, 1, 3,
00404     4, 2, 2, 1, 1,
00405     4, 1, 1, 1, 1,
00406     2, 1, 5,
00407     5, 2, 1, 1, 3, 2,
00408     5, 2, 1, 1, 1, 1,
00409     3, 1, 4, 1,
00410     2, 1, 1,
00411     1, 1,
00412     // Row constraints
00413     2, 2, 2,
00414     2, 2, 2,
00415     1, 4,
00416     2, 1, 1,
00417     2, 1, 1,
00418     4, 1, 1, 1, 1,
00419     2, 1, 1,
00420     2, 1, 4,
00421     3, 1, 1, 1,
00422     3, 1, 1, 4,
00423     2, 1, 3,
00424     2, 1, 2,
00425     1, 5,
00426     2, 2, 2,
00427     2, 3, 3
00428   };
00429 
00435   const int dragonfly[] =
00436     { 20, 20,
00437       // Column constraints.
00438       4, 1, 1, 1, 2,
00439       5, 3, 1, 2, 1, 1,
00440       5, 1, 4, 2, 1, 1,
00441       4, 1, 3, 2, 4,
00442       4, 1, 4, 6, 1,
00443       3, 1, 11, 1,
00444       4, 5, 1, 6, 2,
00445       1, 14,
00446       2, 7, 2,
00447       2, 7, 2,
00448       3, 6, 1, 1,
00449       2, 9, 2,
00450       4, 3, 1, 1, 1,
00451       3, 3, 1, 3,
00452       3, 2, 1, 3,
00453       3, 2, 1, 5,
00454       3, 3, 2, 2,
00455       3, 3, 3, 2,
00456       3, 2, 3, 2,
00457       2, 2, 6,
00458       // Row constraints
00459       2, 7, 1,
00460       3, 1, 1, 2,
00461       3, 2, 1, 2,
00462       3, 1, 2, 2,
00463       3, 4, 2, 3,
00464       3, 3, 1, 4,
00465       3, 3, 1, 3,
00466       3, 2, 1, 4,
00467       2, 2, 9,
00468       3, 2, 1, 5,
00469       2, 2, 7,
00470       1, 14,
00471       2, 8, 2,
00472       3, 6, 2, 2,
00473       4, 2, 8, 1, 3,
00474       4, 1, 5, 5, 2,
00475       5, 1, 3, 2, 4, 1,
00476       5, 3, 1, 2, 4, 1,
00477       5, 1, 1, 3, 1, 3,
00478       4, 2, 1, 1, 2
00479     };
00480 
00482   const int castle[]  = {
00483     60, 35,
00484     // Column constraints
00485     7, 2,3,1,5,1,7,1,
00486     7, 2,4,2,3,2,3,5,
00487     8, 2,6,3,1,1,5,1,5,
00488     10, 2,4,2,1,1,1,4,1,1,2,
00489     7, 2,8,2,1,5,2,5,
00490     7, 3,1,6,2,5,1,5,
00491     9, 3,3,3,1,1,6,1,1,1,
00492     9, 3,2,2,2,2,8,1,1,3,
00493     7, 1,4,4,3,7,1,1,
00494     7, 1,2,2,2,3,7,9,
00495     8, 1,2,3,1,1,5,2,2,
00496     7, 2,2,3,1,1,6,1,
00497     6, 1,3,1,5,4,1,
00498     8, 1,3,1,1,6,1,3,1,
00499     8, 3,3,4,5,1,4,2,1,
00500     6, 2,3,3,9,7,1,
00501     8, 2,3,2,2,1,1,3,5,
00502     8, 4,2,1,1,1,1,2,3,
00503     7, 4,2,2,1,4,3,2,
00504     4, 4,3,16,2,
00505     5, 1,2,5,7,1,
00506     6, 4,3,2,2,7,1,
00507     5, 2,3,1,10,1,
00508     6, 2,4,2,1,4,1,
00509     5, 1,6,7,3,1,
00510     4, 3,11,3,1,
00511     5, 7,1,11,2,1,
00512     7, 2,2,2,2,2,2,2,
00513     7, 3,1,1,1,1,2,1,
00514     7, 2,2,2,2,1,1,1,
00515     7, 1,1,1,1,2,1,2,
00516     8, 2,2,2,2,1,1,1,1,
00517     5, 4,1,1,2,2,
00518     5, 5,2,17,2,1,
00519     6, 9,2,3,1,4,2,
00520     6, 9,4,2,1,1,1,
00521     5, 5,4,2,1,4,
00522     7, 11,1,2,1,4,1,2,
00523     5, 3,4,2,4,4,
00524     8, 2,1,4,1,2,1,5,2,
00525     5, 8,4,1,1,2,
00526     5, 1,1,3,2,3,
00527     6, 1,3,1,8,1,6,
00528     4, 2,1,7,14,
00529     7, 1,2,4,4,1,2,3,
00530     10, 1,1,4,2,1,1,1,1,1,4,
00531     6, 3,5,3,1,1,4,
00532     6, 2,4,2,2,1,2,
00533     5, 4,2,3,8,4,
00534     5, 4,15,2,2,4,
00535     6, 4,1,10,2,1,2,
00536     6, 2,12,6,1,2,4,
00537     7, 3,1,3,1,3,3,4,
00538     6, 3,1,2,3,4,1,
00539     7, 5,2,2,2,3,3,3,
00540     9, 1,2,2,2,2,4,1,1,3,
00541     7, 2,1,4,2,7,1,1,
00542     6, 5,2,2,3,6,3,
00543     7, 3,3,2,2,3,2,3,
00544     7, 4,1,2,1,1,2,1,
00545 
00546     // Row constraints
00547     4, 12,1,1,1,
00548     5, 8,6,3,1,3,
00549     6, 5,8,4,3,1,5,
00550     8, 7,3,4,1,3,5,1,7,
00551     13, 2,2,4,9,1,5,1,1,1,1,1,1,1,
00552     8, 4,5,10,2,1,8,7,1,
00553     7, 5,1,3,3,16,1,2,
00554     8, 8,5,1,2,4,9,1,3,
00555     12, 4,5,3,14,1,1,1,1,4,1,1,3,
00556     19, 3,3,2,2,2,4,1,1,1,1,1,1,1,1,3,1,1,3,2,
00557     11, 8,2,7,2,1,1,2,1,1,3,3,
00558     13, 1,5,9,12,2,1,1,3,1,1,2,2,1,
00559     17, 3,2,2,1,1,1,1,4,1,1,1,3,3,1,1,2,2,
00560     12, 5,2,2,2,2,1,5,2,1,1,2,5,
00561     12, 3,5,9,2,1,1,6,3,1,3,2,3,
00562     12, 1,4,1,1,1,4,1,5,5,3,3,3,
00563     10, 4,1,1,1,1,3,4,6,6,3,
00564     12, 3,1,3,1,1,3,3,1,1,4,6,1,
00565     11, 3,1,5,1,1,3,1,1,9,4,1,
00566     14, 2,1,1,7,1,4,1,1,1,1,1,1,3,5,
00567     11, 9,2,1,3,1,1,1,1,4,2,1,
00568     10, 1,14,1,1,2,2,2,10,1,2,
00569     10, 1,9,2,1,2,6,1,5,3,2,
00570     12, 1,9,9,1,2,2,3,1,1,4,3,1,
00571     10, 10,1,3,4,1,3,2,1,2,8,
00572     9, 9,1,3,5,1,1,1,2,7,
00573     12, 4,5,1,2,5,1,3,1,1,2,1,3,
00574     14, 1,1,1,1,2,6,2,3,2,1,1,2,3,1,
00575     11, 1,6,1,5,7,1,3,3,2,4,3,
00576     10, 1,2,1,2,9,1,5,2,6,2,
00577     8, 10,2,2,13,1,3,3,1,
00578     11, 2,2,1,6,2,3,3,2,2,2,1,
00579     12, 2,2,1,1,12,2,2,9,2,2,2,2,
00580     9, 5,1,2,4,1,5,11,2,2,
00581     3, 15,6,18,
00582   };
00583 
00589   const int p200[] =
00590     { 25, 25,
00591       // Column constraints
00592       4, 1,1,2,2,
00593       3, 5,5,7,
00594       4, 5,2,2,9,
00595       4, 3,2,3,9,
00596       5, 1,1,3,2,7,
00597       3, 3,1,5,
00598       5, 7,1,1,1,3,
00599       6, 1,2,1,1,2,1,
00600       3, 4,2,4,
00601       4, 1,2,2,2,
00602       3, 4,6,2,
00603       4, 1,2,2,1,
00604       4, 3,3,2,1,
00605       3, 4,1,15,
00606       6, 1,1,1,3,1,1,
00607       6, 2,1,1,2,2,3,
00608       4, 1,4,4,1,
00609       4, 1,4,3,2,
00610       4, 1,1,2,2,
00611       5, 7,2,3,1,1,
00612       5, 2,1,1,1,5,
00613       3, 1,2,5,
00614       4, 1,1,1,3,
00615       3, 4,2,1,
00616       1, 3,
00617       // Row constraints
00618       3, 2,2,3,
00619       5, 4,1,1,1,4,
00620       5, 4,1,2,1,1,
00621       7, 4,1,1,1,1,1,1,
00622       6, 2,1,1,2,3,5,
00623       6, 1,1,1,1,2,1,
00624       5, 3,1,5,1,2,
00625       6, 3,2,2,1,2,2,
00626       7, 2,1,4,1,1,1,1,
00627       6, 2,2,1,2,1,2,
00628       6, 1,1,1,3,2,3,
00629       5, 1,1,2,7,3,
00630       5, 1,2,2,1,5,
00631       5, 3,2,2,1,2,
00632       4, 3,2,1,2,
00633       3, 5,1,2,
00634       4, 2,2,1,2,
00635       4, 4,2,1,2,
00636       4, 6,2,3,2,
00637       4, 7,4,3,2,
00638       3, 7,4,4,
00639       3, 7,1,4,
00640       3, 6,1,4,
00641       3, 4,2,2,
00642       2, 2,1
00643     };
00644 
00645   // The following instances are from the http://webpbn.com site and
00646   // are all designed by Jan Wolter.
00647   // See also the survey at http://webpbn.com/survey/
00648 
00650   const int webpbn436[]=
00651     { 40, 35,
00652       // Column constraints
00653       1, 1,
00654       2, 3, 2,
00655       3, 2, 3, 3,
00656       3, 3, 3, 3,
00657       4, 3, 3, 3, 3,
00658       4, 4, 2, 2, 2,
00659       4, 3, 3, 2, 3,
00660       4, 3, 2, 2, 2,
00661       3, 3, 2, 6,
00662       2, 2, 9,
00663       3, 2, 3, 3,
00664       5, 4, 4, 3, 2, 4,
00665       5, 7, 2, 5, 2, 6,
00666       6, 12, 2, 3, 2, 3, 2,
00667       6, 3, 1, 2, 2, 2, 3,
00668       6, 2, 2, 3, 2, 2, 2,
00669       6, 6, 2, 6, 2, 2, 2,
00670       5, 12, 4, 3, 2, 2,
00671       4, 12, 2, 2, 2,
00672       3, 2, 6, 2,
00673       4, 2, 6, 5, 2,
00674       4, 10, 9, 2, 2,
00675       5, 12, 3, 3, 2, 2,
00676       7, 6, 2, 2, 2, 2, 2, 2,
00677       6, 2, 2, 3, 2, 2, 2,
00678       6, 4, 3, 2, 2, 2, 3,
00679       6, 7, 3, 3, 2, 3, 2,
00680       5, 5, 3, 5, 2, 6,
00681       5, 4, 3, 3, 3, 4,
00682       3, 3, 5, 3,
00683       2, 3, 9,
00684       3, 4, 2, 6,
00685       4, 4, 2, 2, 2,
00686       4, 4, 2, 2, 3,
00687       4, 3, 2, 2, 3,
00688       3, 3, 3, 3,
00689       3, 3, 3, 3,
00690       3, 4, 3, 3,
00691       3, 2, 3, 3,
00692       2, 2, 1,
00693       // Row constraints
00694       2, 2, 2,
00695       3, 2, 3, 2,
00696       4, 3, 3, 3, 2,
00697       4, 3, 3, 3, 3,
00698       6, 2, 3, 3, 3, 3, 2,
00699       6, 3, 3, 3, 3, 3, 3,
00700       6, 4, 2, 3, 2, 2, 4,
00701       7, 4, 2, 2, 2, 2, 3, 1,
00702       7, 3, 1, 2, 2, 2, 3, 3,
00703       7, 3, 2, 2, 2, 2, 2, 4,
00704       5, 3, 2, 15, 2, 4,
00705       3, 5, 19, 4,
00706       4, 6, 4, 3, 3,
00707       3, 6, 4, 4,
00708       4, 2, 4, 6, 2,
00709       6, 2, 2, 3, 3, 3, 2,
00710       6, 9, 2, 2, 2, 3, 9,
00711       7, 10, 2, 2, 2, 2, 2, 10,
00712       9, 4, 2, 3, 3, 2, 2, 3, 2, 5,
00713       5, 2, 5, 2, 4, 2,
00714       5, 5, 3, 2, 2, 5,
00715       5, 6, 3, 2, 3, 7,
00716       4, 6, 8, 9, 7,
00717       4, 4, 8, 7, 5,
00718       1, 4,
00719       1, 2,
00720       1, 2,
00721       1, 14,
00722       1, 16,
00723       2, 3, 3,
00724       2, 2, 2,
00725       2, 2, 2,
00726       2, 4, 4,
00727       1, 16,
00728       1, 12,
00729     };
00730 
00732   const int webpbn21[]=
00733     { 14, 25,
00734       // Column constraints
00735       1, 2,
00736       2, 4, 6,
00737       4, 9, 4, 4, 2,
00738       4, 1, 6, 2, 6,
00739     3, 1, 5, 2,
00740     2, 1, 6,
00741     2, 1, 5,
00742     2, 1, 4,
00743     2, 1, 4,
00744     3, 1, 4, 2,
00745     3, 1, 4, 6,
00746     5, 1, 6, 4, 4, 2,
00747     3, 9, 2, 6,
00748     2, 4, 2,
00749     // Row constraints
00750     1, 9,
00751     2, 1, 1,
00752     3, 1, 1, 1,
00753     3, 1, 3, 1,
00754     1, 13,
00755     1, 13,
00756     1, 13,
00757     1, 13,
00758     2, 2, 2,
00759     2, 2, 2,
00760     0,
00761     2, 2, 2,
00762     2, 2, 2,
00763     2, 2, 2,
00764     2, 2, 2,
00765     2, 2, 2,
00766     2, 2, 2,
00767     2, 2, 2,
00768     2, 2, 2,
00769     2, 2, 2,
00770     2, 2, 2,
00771     2, 2, 2,
00772     2, 2, 2,
00773     2, 2, 2,
00774     2, 2, 2,
00775   };
00776 
00778 const int webpbn27[]=
00779   { 27, 23,
00780     // Column constraints
00781     2, 4, 12,
00782     3, 6, 1, 1,
00783     3, 8, 1, 1,
00784     5, 3, 2, 2, 1, 1,
00785     6, 2, 1, 1, 2, 1, 6,
00786     4, 1, 1, 1, 1,
00787     6, 3, 1, 1, 2, 1, 1,
00788     5, 3, 2, 3, 1, 1,
00789     3, 10, 1, 1,
00790     5, 4, 2, 2, 1, 1,
00791     6, 3, 1, 1, 2, 1, 1,
00792     4, 2, 1, 1, 1,
00793     6, 3, 1, 1, 2, 1, 1,
00794     5, 3, 2, 3, 1, 6,
00795     3, 10, 1, 1,
00796     5, 4, 2, 2, 1, 1,
00797     6, 3, 1, 1, 2, 1, 1,
00798     4, 1, 1, 1, 9,
00799     6, 2, 1, 1, 2, 1, 1,
00800     5, 2, 2, 3, 1, 3,
00801     3, 8, 1, 5,
00802     3, 6, 1, 1,
00803     3, 4, 9, 1,
00804     2, 1, 1,
00805     2, 2, 1,
00806     2, 1, 1,
00807     1, 4,
00808     // Row constraints
00809     1, 11,
00810     1, 17,
00811     4, 3, 5, 5, 3,
00812     4, 2, 2, 2, 1,
00813     7, 2, 1, 3, 1, 3, 1, 4,
00814     4, 3, 3, 3, 3,
00815     7, 5, 1, 3, 1, 3, 1, 3,
00816     4, 3, 2, 2, 4,
00817     4, 5, 5, 5, 5,
00818     1, 23,
00819     0,
00820     1, 23,
00821     2, 1, 1,
00822     2, 1, 1,
00823     3, 1, 2, 1,
00824     4, 1, 1, 1, 1,
00825     4, 1, 1, 1, 1,
00826     5, 1, 10, 1, 2, 1,
00827     7, 1, 1, 1, 1, 1, 1, 3,
00828     8, 1, 1, 1, 1, 1, 1, 1, 1,
00829     7, 1, 1, 1, 1, 1, 1, 1,
00830     6, 1, 1, 1, 1, 2, 2,
00831     3, 5, 5, 3,
00832   };
00833 
00835   const int webpbn1[]=
00836   { 5, 10,
00837     // Column constraints
00838     2, 2, 1,
00839     3, 2, 1, 3,
00840     1, 7,
00841     2, 1, 3,
00842     2, 2, 1,
00843     // Row constraints
00844     1, 2,
00845     2, 2, 1,
00846     2, 1, 1,
00847     1, 3,
00848     2, 1, 1,
00849     2, 1, 1,
00850     1, 2,
00851     2, 1, 1,
00852     2, 1, 2,
00853     1, 2,
00854   };
00855 
00857   const int webpbn6[]=
00858   { 20, 20,
00859     // Column constraints
00860     1, 5,
00861     2, 5, 3,
00862     3, 2, 3, 4,
00863     3, 1, 7, 2,
00864     1, 8,
00865     1, 9,
00866     1, 9,
00867     1, 8,
00868     1, 7,
00869     1, 8,
00870     1, 9,
00871     1, 10,
00872     1, 13,
00873     2, 6, 2,
00874     1, 4,
00875     1, 6,
00876     1, 6,
00877     1, 5,
00878     1, 6,
00879     1, 6,
00880     // Row constraints
00881     1, 2,
00882     1, 2,
00883     1, 1,
00884     1, 1,
00885     2, 1, 3,
00886     2, 2, 5,
00887     4, 1, 7, 1, 1,
00888     4, 1, 8, 2, 2,
00889     3, 1, 9, 5,
00890     2, 2, 16,
00891     2, 1, 17,
00892     2, 7, 11,
00893     3, 5, 5, 3,
00894     2, 5, 4,
00895     2, 3, 3,
00896     2, 2, 2,
00897     2, 2, 1,
00898     2, 1, 1,
00899     2, 2, 2,
00900     2, 2, 2,
00901   };
00902 
00904   const int webpbn23[]=
00905   { 10, 11,
00906     // Column constraints
00907     1, 1,
00908     1, 3,
00909     1, 1,
00910     2, 2, 2,
00911     1, 2,
00912     1, 4,
00913     1, 1,
00914     1, 3,
00915     1, 3,
00916     1, 1,
00917     // Row constraints
00918     1, 1,
00919     1, 3,
00920     1, 1,
00921     1, 2,
00922     1, 1,
00923     1, 3,
00924     1, 3,
00925     1, 1,
00926     1, 2,
00927     1, 2,
00928     1, 4,
00929   };
00930 
00932 const int webpbn16[]=
00933   { 34, 34,
00934     // Column constraints
00935     2, 1, 1,
00936     2, 2, 2,
00937     2, 3, 3,
00938     4, 2, 1, 1, 2,
00939     4, 2, 1, 1, 2,
00940     4, 1, 1, 1, 1,
00941     4, 1, 1, 1, 1,
00942     1, 18,
00943     6, 2, 1, 1, 1, 1, 2,
00944     6, 1, 1, 1, 1, 1, 1,
00945     6, 1, 1, 1, 1, 1, 1,
00946     1, 26,
00947     8, 2, 1, 1, 1, 1, 1, 1, 2,
00948     8, 2, 1, 1, 2, 2, 1, 1, 2,
00949     8, 2, 1, 1, 2, 2, 1, 1, 2,
00950     2, 14, 14,
00951     4, 1, 1, 1, 1,
00952     4, 1, 1, 1, 1,
00953     2, 14, 14,
00954     8, 2, 1, 1, 2, 2, 1, 1, 2,
00955     8, 2, 1, 1, 2, 2, 1, 1, 2,
00956     8, 2, 1, 1, 1, 1, 1, 1, 2,
00957     1, 26,
00958     6, 1, 1, 1, 1, 1, 1,
00959     6, 1, 1, 1, 1, 1, 1,
00960     6, 2, 1, 1, 1, 1, 2,
00961     1, 18,
00962     4, 1, 1, 1, 1,
00963     4, 1, 1, 1, 1,
00964     4, 2, 1, 1, 2,
00965     4, 2, 1, 1, 2,
00966     2, 3, 3,
00967     2, 2, 2,
00968     2, 1, 1,
00969     // Row constraints
00970     2, 1, 1,
00971     2, 2, 2,
00972     2, 3, 3,
00973     4, 2, 1, 1, 2,
00974     4, 2, 1, 1, 2,
00975     4, 1, 1, 1, 1,
00976     4, 1, 1, 1, 1,
00977     1, 18,
00978     6, 2, 1, 1, 1, 1, 2,
00979     6, 1, 1, 1, 1, 1, 1,
00980     6, 1, 1, 1, 1, 1, 1,
00981     1, 26,
00982     8, 2, 1, 1, 1, 1, 1, 1, 2,
00983     8, 2, 1, 1, 2, 2, 1, 1, 2,
00984     8, 2, 1, 1, 2, 2, 1, 1, 2,
00985     2, 14, 14,
00986     4, 1, 1, 1, 1,
00987     4, 1, 1, 1, 1,
00988     2, 14, 14,
00989     8, 2, 1, 1, 2, 2, 1, 1, 2,
00990     8, 2, 1, 1, 2, 2, 1, 1, 2,
00991     8, 2, 1, 1, 1, 1, 1, 1, 2,
00992     1, 26,
00993     6, 1, 1, 1, 1, 1, 1,
00994     6, 1, 1, 1, 1, 1, 1,
00995     6, 2, 1, 1, 1, 1, 2,
00996     1, 18,
00997     4, 1, 1, 1, 1,
00998     4, 1, 1, 1, 1,
00999     4, 2, 1, 1, 2,
01000     4, 2, 1, 1, 2,
01001     2, 3, 3,
01002     2, 2, 2,
01003     2, 1, 1,
01004   };
01005 
01007   const int webpbn529[]=
01008   { 45, 45,
01009     // Column constraints
01010     6, 7, 1, 1, 1, 1, 1,
01011     13, 2, 2, 4, 1, 4, 1, 5, 1, 4, 1, 4, 1, 2,
01012     10, 3, 1, 4, 1, 4, 1, 14, 4, 1, 2,
01013     8, 1, 1, 5, 1, 2, 3, 4, 1,
01014     4, 3, 13, 1, 10,
01015     3, 1, 9, 4,
01016     4, 6, 7, 2, 2,
01017     4, 8, 4, 1, 4,
01018     6, 2, 8, 3, 2, 5, 3,
01019     5, 10, 1, 3, 7, 2,
01020     6, 8, 6, 2, 8, 1, 2,
01021     7, 1, 1, 2, 2, 8, 1, 1,
01022     11, 2, 1, 1, 1, 2, 1, 3, 1, 3, 3, 1,
01023     8, 2, 1, 1, 1, 5, 4, 2, 1,
01024     8, 2, 1, 1, 1, 1, 7, 2, 1,
01025     8, 2, 1, 1, 2, 9, 1, 2, 1,
01026     5, 4, 6, 12, 1, 3,
01027     4, 16, 13, 3, 2,
01028     3, 12, 21, 2,
01029     3, 2, 13, 23,
01030     3, 2, 14, 19,
01031     4, 2, 14, 20, 2,
01032     6, 2, 13, 7, 2, 8, 2,
01033     5, 12, 8, 1, 7, 2,
01034     9, 5, 1, 1, 1, 2, 8, 1, 5, 2,
01035     8, 2, 1, 1, 1, 9, 1, 1, 4,
01036     8, 2, 1, 1, 1, 6, 1, 3, 5,
01037     6, 2, 2, 1, 5, 6, 2,
01038     8, 2, 1, 3, 1, 3, 7, 3, 2,
01039     9, 2, 3, 2, 1, 1, 2, 4, 4, 2,
01040     9, 2, 2, 1, 1, 2, 3, 1, 8, 2,
01041     5, 9, 3, 1, 7, 2,
01042     5, 12, 4, 1, 6, 2,
01043     5, 7, 4, 1, 2, 5,
01044     5, 2, 6, 6, 5, 6,
01045     4, 8, 8, 6, 3,
01046     5, 3, 10, 8, 4, 2,
01047     5, 5, 11, 9, 5, 2,
01048     5, 3, 1, 12, 16, 2,
01049     4, 3, 1, 12, 16,
01050     4, 5, 2, 13, 21,
01051     6, 6, 1, 3, 3, 1, 1,
01052     14, 5, 1, 3, 1, 3, 1, 1, 2, 1, 4, 1, 3, 1, 3,
01053     13, 5, 1, 3, 1, 3, 1, 4, 1, 4, 1, 3, 1, 3,
01054     6, 1, 1, 1, 1, 1, 1,
01055     // Row constraints
01056     6, 7, 1, 1, 1, 1, 1,
01057     13, 3, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
01058     14, 1, 1, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
01059     9, 2, 1, 2, 1, 1, 1, 1, 6, 2,
01060     4, 3, 30, 1, 5,
01061     9, 1, 5, 8, 1, 1, 7, 1, 1, 3,
01062     7, 3, 4, 8, 1, 5, 1, 2,
01063     4, 3, 20, 6, 6,
01064     6, 3, 3, 7, 2, 5, 1,
01065     9, 3, 3, 1, 1, 9, 1, 1, 5, 6,
01066     7, 2, 3, 8, 1, 3, 4, 2,
01067     7, 5, 3, 1, 10, 4, 5, 2,
01068     6, 1, 2, 3, 8, 4, 6,
01069     5, 2, 2, 3, 11, 10,
01070     5, 2, 2, 3, 10, 7,
01071     6, 2, 3, 1, 7, 12, 2,
01072     6, 2, 3, 1, 4, 11, 2,
01073     6, 4, 1, 2, 1, 11, 2,
01074     4, 9, 1, 2, 9,
01075     5, 6, 2, 1, 4, 11,
01076     6, 2, 5, 1, 2, 6, 6,
01077     5, 6, 2, 4, 8, 4,
01078     4, 4, 2, 16, 1,
01079     4, 2, 2, 15, 2,
01080     4, 3, 2, 15, 4,
01081     4, 3, 3, 13, 4,
01082     3, 4, 12, 9,
01083     3, 1, 9, 10,
01084     5, 2, 1, 17, 7, 2,
01085     6, 2, 2, 8, 3, 8, 2,
01086     6, 2, 3, 6, 3, 8, 2,
01087     6, 2, 4, 5, 4, 7, 2,
01088     5, 2, 5, 5, 4, 6,
01089     5, 4, 4, 5, 4, 9,
01090     5, 1, 4, 6, 4, 4,
01091     6, 4, 3, 6, 4, 3, 2,
01092     7, 2, 1, 2, 7, 4, 4, 2,
01093     7, 2, 2, 2, 9, 5, 5, 2,
01094     6, 2, 2, 2, 10, 6, 6,
01095     5, 3, 2, 1, 9, 18,
01096     3, 8, 4, 23,
01097     9, 1, 2, 1, 2, 2, 1, 1, 1, 2,
01098     12, 2, 1, 4, 2, 1, 4, 1, 5, 1, 3, 1, 2,
01099     11, 2, 1, 5, 4, 4, 1, 5, 1, 3, 1, 2,
01100     5, 1, 10, 1, 1, 1,
01101   };
01102 
01103 
01105   const int webpbn65[]=
01106   { 34, 40,
01107     // Column constraints
01108     1, 5,
01109     3, 3, 2, 1,
01110     4, 3, 2, 2, 1,
01111     5, 3, 2, 2, 2, 2,
01112     6, 3, 2, 2, 2, 2, 3,
01113     7, 1, 2, 2, 2, 2, 2, 16,
01114     9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
01115     9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
01116     10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
01117     9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
01118     11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
01119     12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
01120     11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
01121     6, 1, 7, 2, 16, 1, 1,
01122     11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
01123     11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
01124     9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
01125     9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
01126     11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
01127     11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
01128     6, 1, 7, 2, 16, 1, 1,
01129     11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
01130     12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
01131     11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
01132     9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
01133     10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
01134     9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
01135     9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
01136     7, 1, 2, 2, 2, 2, 2, 16,
01137     6, 3, 2, 2, 2, 2, 3,
01138     5, 3, 2, 2, 2, 2,
01139     4, 3, 2, 2, 1,
01140     3, 3, 2, 1,
01141     1, 5,
01142     // Row constraints
01143     1, 12,
01144     3, 5, 2, 5,
01145     4, 5, 2, 2, 5,
01146     7, 1, 2, 2, 2, 2, 2, 1,
01147     7, 4, 2, 2, 4, 2, 2, 4,
01148     7, 4, 2, 2, 4, 2, 2, 4,
01149     7, 1, 2, 2, 2, 2, 2, 1,
01150     7, 6, 2, 2, 2, 2, 2, 6,
01151     7, 6, 2, 2, 2, 2, 2, 6,
01152     3, 1, 14, 1,
01153     2, 10, 10,
01154     4, 8, 3, 3, 8,
01155     8, 1, 1, 2, 1, 1, 2, 1, 1,
01156     6, 9, 2, 2, 2, 2, 9,
01157     2, 9, 9,
01158     6, 1, 1, 1, 1, 1, 1,
01159     3, 12, 2, 12,
01160     2, 12, 12,
01161     5, 1, 1, 4, 1, 1,
01162     2, 14, 14,
01163     2, 12, 12,
01164     5, 2, 1, 4, 1, 2,
01165     3, 9, 4, 9,
01166     5, 1, 7, 4, 7, 1,
01167     7, 1, 1, 1, 4, 1, 1, 1,
01168     5, 1, 7, 4, 7, 1,
01169     5, 1, 7, 4, 7, 1,
01170     7, 1, 2, 1, 2, 1, 2, 1,
01171     5, 1, 7, 2, 7, 1,
01172     7, 1, 1, 6, 2, 6, 1, 1,
01173     9, 1, 1, 1, 1, 2, 1, 1, 1, 1,
01174     7, 1, 1, 6, 2, 6, 1, 1,
01175     6, 1, 1, 5, 5, 1, 1,
01176     7, 1, 1, 1, 8, 1, 1, 1,
01177     6, 1, 1, 4, 4, 1, 1,
01178     5, 1, 2, 6, 2, 1,
01179     4, 2, 4, 4, 2,
01180     3, 2, 6, 2,
01181     2, 4, 4,
01182     1, 6,
01183   };
01184 
01185 
01186   const int *specs[] = {heart, bear, crocodile, unknown,
01187                         pinwheel, difficult, non_unique, dragonfly,
01188                         castle, p200,
01189                         // From the webpbn survey
01190                         webpbn1,    // 10
01191                         webpbn6,    // 11
01192                         webpbn21,   // 12
01193                         webpbn27,   // 13
01194                         webpbn23,   // 14
01195                         webpbn16,   // 15
01196                         webpbn529,  // 16
01197                         webpbn65,   // 17
01198                         webpbn436,  // 18
01199   };
01200   const unsigned n_examples = sizeof(specs)/sizeof(int*);
01202 
01203 }
01204 
01205 // STATISTICS: example-any