Generated on Mon Nov 30 23:53:17 2009 for Gecode by doxygen 1.6.1

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  *  Last modified:
00010  *     $Date: 2009-11-02 10:52:51 +0100 (Mon, 02 Nov 2009) $ by $Author: zayenz $
00011  *     $Revision: 10018 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041 
00042 using namespace Gecode;
00043 
00044 namespace {
00045 
00047   extern const int* specs[];
00049   extern const unsigned int n_examples;
00050 
00051 }
00052 
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 
00100 public:
00102   Nonogram(const SizeOptions& opt)
00103     : spec(specs[opt.size()]), b(*this,width()*height(),0,1) {
00104     Matrix<BoolVarArray> m(b, width(), height());
00105 
00106     {
00107       int spos = 2;
00108       // Post constraints for columns
00109       for (int w=0; w<width(); w++)
00110         extensional(*this, m.col(w), line(spos));
00111       // Post constraints for rows
00112       for (int h=0; h<height(); h++)
00113         extensional(*this, m.row(h), line(spos));
00114     }
00115 
00116     // Number of hints for columns
00117     int cols = 0;
00118     // Number of hints for rows
00119     int rows = 0;
00120     // Compute number of hints
00121     {
00122       int spos = 2;
00123       for (int w=0; w<width(); w++) {
00124         int hint = spec[spos++];
00125         cols += hint; spos += hint;
00126       }
00127       for (int h=0; h<height(); h++) {
00128         int hint = spec[spos++];
00129         rows += hint; spos += hint;
00130       }
00131     }
00132 
00133     /*
00134      * The following branches either by columns or rows, depending on
00135      * whether there are more hints relative to the height or width
00136      * for columns or rows.
00137      *
00138      * This idea is due to Pascal Van Hentenryck and has been suggested
00139      * to us by Hakan Kjellerstrand.
00140      */
00141     if (rows*width() > cols*height()) {
00142       for (int w=0; w<width(); w++)
00143         branch(*this, m.col(w), INT_VAR_NONE, INT_VAL_MAX);
00144     } else {
00145       for (int h=0; h<height(); h++)
00146         branch(*this, m.row(h), INT_VAR_NONE, INT_VAL_MAX);
00147     }
00148   }
00149 
00151   Nonogram(bool share, Nonogram& s) : Script(share,s), spec(s.spec) {
00152     b.update(*this, share, s.b);
00153   }
00154 
00156   virtual Space*
00157   copy(bool share) {
00158     return new Nonogram(share,*this);
00159   }
00160 
00162   virtual void
00163   print(std::ostream& os) const {
00164     Matrix<BoolVarArray> m(b, width(), height());
00165     for (int h = 0; h < height(); ++h) {
00166       os << '\t';
00167       for (int w = 0; w < width(); ++w)
00168         os << ((m(w,h).val() == 1) ? '#' : ' ');
00169       os << std::endl;
00170     }
00171     os << std::endl;
00172   }
00173 };
00174 
00175 
00179 int
00180 main(int argc, char* argv[]) {
00181   SizeOptions opt("Nonogram");
00182   opt.size(8);
00183   opt.parse(argc,argv);
00184   if (opt.size() >= n_examples) {
00185     std::cerr << "Error: size must be between 0 and "
00186               << n_examples-1 << std::endl;
00187     return 1;
00188   }
00189   Script::run<Nonogram,DFS,SizeOptions>(opt);
00190   return 0;
00191 }
00192 
00193 namespace {
00194 
00206 
00207 const int heart[] =
00208   { 9, 9,
00209     // Column constraints.
00210     1, 3,
00211     2, 2, 3,
00212     2, 2, 2,
00213     2, 2, 2,
00214     2, 2, 2,
00215     2, 2, 2,
00216     2, 2, 2,
00217     2, 2, 3,
00218     1, 3,
00219     // Row constraints
00220     2, 2, 2,
00221     2, 4, 4,
00222     3, 1, 3, 1,
00223     3, 2, 1, 2,
00224     2, 1, 1,
00225     2, 2, 2,
00226     2, 2, 2,
00227     1, 3,
00228     1, 1
00229   };
00230 
00232 const int bear[] =
00233   { 13, 8,
00234     // Column constraints
00235     1, 2,
00236     2, 2, 1,
00237     2, 3, 2,
00238     1, 6,
00239     2, 1, 4,
00240     1, 3,
00241     1, 4,
00242     1, 4,
00243     1, 4,
00244     1, 5,
00245     1, 4,
00246     2, 1, 3,
00247     1, 2,
00248     // Row constraints
00249     1, 1,
00250     1, 2,
00251     2, 4, 4,
00252     1, 12,
00253     1, 8,
00254     1, 9,
00255     2, 3, 4,
00256     2, 2, 2
00257   };
00258 
00260 const int crocodile[] =
00261   { 15, 9,
00262     // Column constraints
00263     1, 3,
00264     1, 4,
00265     2, 2, 2,
00266     2, 3, 1,
00267     2, 2, 3,
00268     2, 3, 2,
00269     2, 2, 3,
00270     2, 4, 2,
00271     2, 3, 2,
00272     1, 6,
00273     2, 1, 3,
00274     2, 1, 3,
00275     2, 1, 4,
00276     1, 5,
00277     1, 5,
00278     // Row constraints
00279     1, 3,
00280     3, 2, 3, 2,
00281     2, 10, 3,
00282     1, 15,
00283     5, 1, 1, 1, 1, 6,
00284     2, 1, 7,
00285     2, 1, 4,
00286     2, 1, 4,
00287     1, 4
00288   };
00289 
00291 const int unknown[] =
00292   { 10, 10,
00293     // Column constraints
00294     1, 3,
00295     2, 2, 1,
00296     2, 2, 2,
00297     2, 2, 1,
00298     3, 1, 2, 1,
00299     2, 1, 1,
00300     3, 1, 4, 1,
00301     3, 1, 1, 2,
00302     2, 3, 1,
00303     1, 4,
00304     // Row constraints
00305     1, 3,
00306     2, 2, 1,
00307     2, 1, 1,
00308     2, 1, 4,
00309     4, 1, 1, 1, 1,
00310     4, 2, 1, 1, 1,
00311     3, 2, 1, 1,
00312     2, 1, 2,
00313     2, 2, 3,
00314     1, 3
00315   };
00316 
00318 const int pinwheel[] =
00319   { 6, 6,
00320     // Column constraints
00321     2, 1, 2,
00322     1, 1,
00323     1, 2,
00324     1, 2,
00325     1, 1,
00326     2, 2, 1,
00327     // Row constraints
00328     2, 2, 1,
00329     1, 1,
00330     1, 2,
00331     1, 2,
00332     1, 1,
00333     2, 1, 2
00334   };
00335 
00337 const int difficult[] =
00338   { 15, 15,
00339     // Column constraints
00340     1, 3,
00341     1, 2,
00342     1, 2,
00343     1, 1,
00344     1, 2,
00345     1, 3,
00346     1, 2,
00347     1, 4,
00348     1, 3,
00349     1, 4,
00350     2, 2, 1,
00351     2, 1, 1,
00352     2, 1, 1,
00353     2, 1, 1,
00354     1, 3,
00355     // Row constraints
00356     1, 3,
00357     2, 1, 1,
00358     2, 1, 1,
00359     2, 1, 1,
00360     2, 1, 2,
00361     1, 5,
00362     1, 1,
00363     1, 2,
00364     1, 1,
00365     1, 1,
00366     2, 1, 2,
00367     2, 1, 2,
00368     2, 2, 1,
00369     2, 2, 2,
00370     1, 3
00371   };
00372 
00374 const int non_unique[] =
00375   { 11, 15,
00376     // Column constraints
00377     1, 5,
00378     3, 1, 2, 4,
00379     3, 2, 1, 3,
00380     4, 2, 2, 1, 1,
00381     4, 1, 1, 1, 1,
00382     2, 1, 5,
00383     5, 2, 1, 1, 3, 2,
00384     5, 2, 1, 1, 1, 1,
00385     3, 1, 4, 1,
00386     2, 1, 1,
00387     1, 1,
00388     // Row constraints
00389     2, 2, 2,
00390     2, 2, 2,
00391     1, 4,
00392     2, 1, 1,
00393     2, 1, 1,
00394     4, 1, 1, 1, 1,
00395     2, 1, 1,
00396     2, 1, 4,
00397     3, 1, 1, 1,
00398     3, 1, 1, 4,
00399     2, 1, 3,
00400     2, 1, 2,
00401     1, 5,
00402     2, 2, 2,
00403     2, 3, 3
00404   };
00405 
00411   const int dragonfly[] =
00412     { 20, 20,
00413       // Column constraints.
00414       4, 1, 1, 1, 2,
00415       5, 3, 1, 2, 1, 1,
00416       5, 1, 4, 2, 1, 1,
00417       4, 1, 3, 2, 4,
00418       4, 1, 4, 6, 1,
00419       3, 1, 11, 1,
00420       4, 5, 1, 6, 2,
00421       1, 14,
00422       2, 7, 2,
00423       2, 7, 2,
00424       3, 6, 1, 1,
00425       2, 9, 2,
00426       4, 3, 1, 1, 1,
00427       3, 3, 1, 3,
00428       3, 2, 1, 3,
00429       3, 2, 1, 5,
00430       3, 3, 2, 2,
00431       3, 3, 3, 2,
00432       3, 2, 3, 2,
00433       2, 2, 6,
00434       // Row constraints
00435       2, 7, 1,
00436       3, 1, 1, 2,
00437       3, 2, 1, 2,
00438       3, 1, 2, 2,
00439       3, 4, 2, 3,
00440       3, 3, 1, 4,
00441       3, 3, 1, 3,
00442       3, 2, 1, 4,
00443       2, 2, 9,
00444       3, 2, 1, 5,
00445       2, 2, 7,
00446       1, 14,
00447       2, 8, 2,
00448       3, 6, 2, 2,
00449       4, 2, 8, 1, 3,
00450       4, 1, 5, 5, 2,
00451       5, 1, 3, 2, 4, 1,
00452       5, 3, 1, 2, 4, 1,
00453       5, 1, 1, 3, 1, 3,
00454       4, 2, 1, 1, 2
00455     };
00456 
00458   const int castle[]  = {
00459     60, 35,
00460     // Column constraints
00461     7, 2,3,1,5,1,7,1,
00462     7, 2,4,2,3,2,3,5,
00463     8, 2,6,3,1,1,5,1,5,
00464     10, 2,4,2,1,1,1,4,1,1,2,
00465     7, 2,8,2,1,5,2,5,
00466     7, 3,1,6,2,5,1,5,
00467     9, 3,3,3,1,1,6,1,1,1,
00468     9, 3,2,2,2,2,8,1,1,3,
00469     7, 1,4,4,3,7,1,1,
00470     7, 1,2,2,2,3,7,9,
00471     8, 1,2,3,1,1,5,2,2,
00472     7, 2,2,3,1,1,6,1,
00473     6, 1,3,1,5,4,1,
00474     8, 1,3,1,1,6,1,3,1,
00475     8, 3,3,4,5,1,4,2,1,
00476     6, 2,3,3,9,7,1,
00477     8, 2,3,2,2,1,1,3,5,
00478     8, 4,2,1,1,1,1,2,3,
00479     7, 4,2,2,1,4,3,2,
00480     4, 4,3,16,2,
00481     5, 1,2,5,7,1,      
00482     6, 4,3,2,2,7,1,      
00483     5, 2,3,1,10,1,      
00484     6, 2,4,2,1,4,1,      
00485     5, 1,6,7,3,1,      
00486     4, 3,11,3,1,      
00487     5, 7,1,11,2,1,      
00488     7, 2,2,2,2,2,2,2,      
00489     7, 3,1,1,1,1,2,1,      
00490     7, 2,2,2,2,1,1,1,      
00491     7, 1,1,1,1,2,1,2,      
00492     8, 2,2,2,2,1,1,1,1,      
00493     5, 4,1,1,2,2,      
00494     5, 5,2,17,2,1,      
00495     6, 9,2,3,1,4,2,      
00496     6, 9,4,2,1,1,1,      
00497     5, 5,4,2,1,4,      
00498     7, 11,1,2,1,4,1,2,      
00499     5, 3,4,2,4,4,      
00500     8, 2,1,4,1,2,1,5,2,      
00501     5, 8,4,1,1,2,      
00502     5, 1,1,3,2,3,      
00503     6, 1,3,1,8,1,6,      
00504     4, 2,1,7,14,      
00505     7, 1,2,4,4,1,2,3,      
00506     10, 1,1,4,2,1,1,1,1,1,4,      
00507     6, 3,5,3,1,1,4,      
00508     6, 2,4,2,2,1,2,      
00509     5, 4,2,3,8,4,      
00510     5, 4,15,2,2,4,      
00511     6, 4,1,10,2,1,2,      
00512     6, 2,12,6,1,2,4,      
00513     7, 3,1,3,1,3,3,4,      
00514     6, 3,1,2,3,4,1,      
00515     7, 5,2,2,2,3,3,3,      
00516     9, 1,2,2,2,2,4,1,1,3,      
00517     7, 2,1,4,2,7,1,1,      
00518     6, 5,2,2,3,6,3,      
00519     7, 3,3,2,2,3,2,3,      
00520     7, 4,1,2,1,1,2,1,
00521 
00522     // Row constraints
00523     4, 12,1,1,1,                                
00524     5, 8,6,3,1,3,                                
00525     6, 5,8,4,3,1,5,                                
00526     8, 7,3,4,1,3,5,1,7,                                
00527     13, 2,2,4,9,1,5,1,1,1,1,1,1,1,                                
00528     8, 4,5,10,2,1,8,7,1,                                
00529     7, 5,1,3,3,16,1,2,                                
00530     8, 8,5,1,2,4,9,1,3,                                
00531     12, 4,5,3,14,1,1,1,1,4,1,1,3,                                
00532     19, 3,3,2,2,2,4,1,1,1,1,1,1,1,1,3,1,1,3,2,                                
00533     11, 8,2,7,2,1,1,2,1,1,3,3,                                
00534     13, 1,5,9,12,2,1,1,3,1,1,2,2,1,                                
00535     17, 3,2,2,1,1,1,1,4,1,1,1,3,3,1,1,2,2,                                
00536     12, 5,2,2,2,2,1,5,2,1,1,2,5,                                
00537     12, 3,5,9,2,1,1,6,3,1,3,2,3,                                
00538     12, 1,4,1,1,1,4,1,5,5,3,3,3,                                
00539     10, 4,1,1,1,1,3,4,6,6,3,                                
00540     12, 3,1,3,1,1,3,3,1,1,4,6,1,                                
00541     11, 3,1,5,1,1,3,1,1,9,4,1,                                
00542     14, 2,1,1,7,1,4,1,1,1,1,1,1,3,5,                                
00543     11, 9,2,1,3,1,1,1,1,4,2,1,                                
00544     10, 1,14,1,1,2,2,2,10,1,2,                                
00545     10, 1,9,2,1,2,6,1,5,3,2,                                
00546     12, 1,9,9,1,2,2,3,1,1,4,3,1,                                
00547     10, 10,1,3,4,1,3,2,1,2,8,                                
00548     9, 9,1,3,5,1,1,1,2,7,                                
00549     12, 4,5,1,2,5,1,3,1,1,2,1,3,                                
00550     14, 1,1,1,1,2,6,2,3,2,1,1,2,3,1,                                
00551     11, 1,6,1,5,7,1,3,3,2,4,3,                                
00552     10, 1,2,1,2,9,1,5,2,6,2,                                
00553     8, 10,2,2,13,1,3,3,1,                                
00554     11, 2,2,1,6,2,3,3,2,2,2,1,                                
00555     12, 2,2,1,1,12,2,2,9,2,2,2,2,                                
00556     9, 5,1,2,4,1,5,11,2,2,                                
00557     3, 15,6,18,
00558   };
00559 
00565   const int p200[] =
00566     { 25, 25,
00567       // Column constraints
00568       4, 1,1,2,2,
00569       3, 5,5,7,
00570       4, 5,2,2,9,
00571       4, 3,2,3,9,
00572       5, 1,1,3,2,7,
00573       3, 3,1,5,
00574       5, 7,1,1,1,3,
00575       6, 1,2,1,1,2,1,
00576       3, 4,2,4,
00577       4, 1,2,2,2,
00578       3, 4,6,2,
00579       4, 1,2,2,1,
00580       4, 3,3,2,1,
00581       3, 4,1,15,
00582       6, 1,1,1,3,1,1,
00583       6, 2,1,1,2,2,3,
00584       4, 1,4,4,1,
00585       4, 1,4,3,2,
00586       4, 1,1,2,2,
00587       5, 7,2,3,1,1,
00588       5, 2,1,1,1,5,
00589       3, 1,2,5,
00590       4, 1,1,1,3,
00591       3, 4,2,1,
00592       1, 3,
00593       // Row constraints
00594       3, 2,2,3,
00595       5, 4,1,1,1,4,
00596       5, 4,1,2,1,1,
00597       7, 4,1,1,1,1,1,1,
00598       6, 2,1,1,2,3,5,
00599       6, 1,1,1,1,2,1,
00600       5, 3,1,5,1,2,
00601       6, 3,2,2,1,2,2,
00602       7, 2,1,4,1,1,1,1,
00603       6, 2,2,1,2,1,2,
00604       6, 1,1,1,3,2,3,
00605       5, 1,1,2,7,3,
00606       5, 1,2,2,1,5,
00607       5, 3,2,2,1,2,
00608       4, 3,2,1,2,
00609       3, 5,1,2,
00610       4, 2,2,1,2,
00611       4, 4,2,1,2,
00612       4, 6,2,3,2,
00613       4, 7,4,3,2,
00614       3, 7,4,4,
00615       3, 7,1,4,
00616       3, 6,1,4,
00617       3, 4,2,2,
00618       2, 2,1
00619     };
00620 
00621 
00622   const int *specs[] = {heart, bear, crocodile, unknown,
00623                         pinwheel, difficult, non_unique, dragonfly, 
00624                         castle, p200};
00625   const unsigned n_examples = sizeof(specs)/sizeof(int*);
00627 
00628 }
00629 
00630 // STATISTICS: example-any