Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

picture-puzzle.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Mikael Lagerkvist, 2005
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-10-20 15:28:46 +0200 (Thu, 20 Oct 2005) $ by $Author: zayenz $
00010  *     $Revision: 2391 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "examples/support.hh"
00023 #include "minimodel.hh"
00024 
00025 extern const int *specs[];
00026 extern const unsigned int n_examples;
00027 
00040 class PicturePuzzle : public Example {
00041 private:
00042   const int *spec;
00043   int width, height;
00044   BoolVarArray b;
00045   
00047   BoolVar pos(int h, int w) {
00048     return b[h*width + w];
00049   }
00050 
00052   REG get_constraint(int& spos) {
00053     // Useful to check that a new specification was entered correctly.
00054     const bool print_spec = false;
00055     REG r = *REG(0);
00056     int size = spec[spos++];
00057     if (print_spec) std::cout << size << "(" << spos << "): ";
00058     for (int i = 0; i < size; ++i, ++spos) {
00059       if (i) r = r + +REG(0);
00060       if (print_spec) std::cout << spec[spos] << " ";
00061       r = r + REG(1)(spec[spos],spec[spos]);
00062     }
00063     if (print_spec) std::cout << std::endl;
00064     r = r + *REG(0);
00065 
00066     return r;
00067   }
00068 
00069 
00070 public:
00072   PicturePuzzle(const Options& o)
00073     : spec(specs[o.size]), width(spec[0]), height(spec[1]),
00074       b(this,width*height,0,1) {
00075     int spos = 2;
00076     MiniModel::Matrix<BoolVarArray> m(b, width, height);
00077 
00078     // Post constraints for columns
00079     for (int w = 0; w < width; ++w) {
00080       // Post constraint
00081       REG r = get_constraint(spos);
00082       DFA d = r;
00083       regular(this, m.col(w), d);
00084     }
00085 
00086     // Post constraints for rows
00087     for (int h = 0; h < height; ++h) {
00088       // Post constraint
00089       REG r = get_constraint(spos);
00090       DFA d = r;
00091       regular(this, m.row(h), d);
00092     }
00093 
00094     // Install branchings
00095     branch(this, b, BVAR_NONE, BVAL_MAX);
00096   }
00097 
00099   PicturePuzzle(bool share, PicturePuzzle& s) : 
00100     Example(share,s), spec(s.spec), width(s.width), height(s.height) {
00101     b.update(this, share, s.b);
00102   }
00103 
00105   virtual Space*
00106   copy(bool share) {
00107     return new PicturePuzzle(share,*this);
00108   }
00109 
00111   virtual void
00112   print(void) {
00113     for (int h = 0; h < height; ++h) {
00114       std::cout << '\t';
00115       for (int w = 0; w < width; ++w) {
00116         if (pos(h,w).val() == 1) {
00117           std::cout << "#";
00118         } else {
00119           std::cout << " ";
00120         }
00121       }
00122       std::cout << std::endl;
00123     }
00124     std::cout << std::endl;
00125   }
00126 };
00127 
00128 
00132 int
00133 main(int argc, char** argv) {
00134   Options o("PicturePuzzle");
00135   o.size  = 8;
00136   o.parse(argc,argv);
00137   if (o.size >= n_examples) {
00138     std::cerr << "Error: size must be between 0 and " 
00139               << n_examples-1 << std::endl;
00140     return 1;
00141   }
00142   Example::run<PicturePuzzle,DFS>(o);
00143   return 0;
00144 }
00145 
00146 
00158 
00159 static const int heart[] =
00160   { 9, 9,
00161     // Column constraints.
00162     1, 3,
00163     2, 2, 3,
00164     2, 2, 2,
00165     2, 2, 2,
00166     2, 2, 2,
00167     2, 2, 2,
00168     2, 2, 2,
00169     2, 2, 3,
00170     1, 3,
00171     // Row constraints
00172     2, 2, 2,
00173     2, 4, 4,
00174     3, 1, 3, 1,
00175     3, 2, 1, 2,
00176     2, 1, 1,
00177     2, 2, 2,
00178     2, 2, 2,
00179     1, 3,
00180     1, 1
00181   };
00182 
00184 static const int bear[] = 
00185   { 13, 8,
00186     // Column constraints
00187     1, 2,
00188     2, 2, 1,
00189     2, 3, 2,
00190     1, 6,
00191     2, 1, 4,
00192     1, 3,
00193     1, 4,
00194     1, 4,
00195     1, 4,
00196     1, 5,
00197     1, 4,
00198     2, 1, 3,
00199     1, 2,
00200     // Row constraints
00201     1, 1,
00202     1, 2,
00203     2, 4, 4,
00204     1, 12,
00205     1, 8,
00206     1, 9,
00207     2, 3, 4,
00208     2, 2, 2
00209   };
00210 
00212 static const int crocodile[] =
00213   { 15, 9,
00214     // Column constraints
00215     1, 3,
00216     1, 4,
00217     2, 2, 2,
00218     2, 3, 1,
00219     2, 2, 3,
00220     2, 3, 2,
00221     2, 2, 3,
00222     2, 4, 2,
00223     2, 3, 2,
00224     1, 6,
00225     2, 1, 3,
00226     2, 1, 3,
00227     2, 1, 4,
00228     1, 5,
00229     1, 5,
00230     // Row constraints
00231     1, 3,
00232     3, 2, 3, 2,
00233     2, 10, 3,
00234     1, 15,
00235     5, 1, 1, 1, 1, 6,
00236     2, 1, 7,
00237     2, 1, 4,
00238     2, 1, 4,
00239     1, 4
00240   };
00241 
00243 static const int unknown[] = 
00244   { 10, 10,
00245     // Column constraints
00246     1, 3,
00247     2, 2, 1,
00248     2, 2, 2,
00249     2, 2, 1,
00250     3, 1, 2, 1,
00251     2, 1, 1,
00252     3, 1, 4, 1,
00253     3, 1, 1, 2,
00254     2, 3, 1,
00255     1, 4,
00256     // Row constraints
00257     1, 3,
00258     2, 2, 1,
00259     2, 1, 1,
00260     2, 1, 4,
00261     4, 1, 1, 1, 1,
00262     4, 2, 1, 1, 1,
00263     3, 2, 1, 1,
00264     2, 1, 2,
00265     2, 2, 3,
00266     1, 3
00267   };
00268 
00270 static const int pinwheel[] = 
00271   { 6, 6,
00272     // Column constraints
00273     2, 1, 2,
00274     1, 1,
00275     1, 2,
00276     1, 2,
00277     1, 1,
00278     2, 2, 1,
00279     // Row constraints
00280     2, 2, 1,
00281     1, 1,
00282     1, 2,
00283     1, 2,
00284     1, 1,
00285     2, 1, 2    
00286   };
00287 
00289 static const int difficult[] = 
00290   { 15, 15,
00291     // Column constraints
00292     1, 3,
00293     1, 2,
00294     1, 2,
00295     1, 1,
00296     1, 2,
00297     1, 3,
00298     1, 2,
00299     1, 4,
00300     1, 3,
00301     1, 4,
00302     2, 2, 1,
00303     2, 1, 1,
00304     2, 1, 1,
00305     2, 1, 1,
00306     1, 3,
00307     // Row constraints
00308     1, 3,
00309     2, 1, 1,
00310     2, 1, 1,
00311     2, 1, 1,
00312     2, 1, 2,
00313     1, 5,
00314     1, 1,
00315     1, 2,
00316     1, 1,
00317     1, 1,
00318     2, 1, 2,
00319     2, 1, 2,
00320     2, 2, 1,
00321     2, 2, 2,
00322     1, 3
00323   };
00324 
00326 static const int non_unique[] = 
00327   { 11, 15,
00328     // Column constraints
00329     1, 5,
00330     3, 1, 2, 4,
00331     3, 2, 1, 3,
00332     4, 2, 2, 1, 1,
00333     4, 1, 1, 1, 1,
00334     2, 1, 5,
00335     5, 2, 1, 1, 3, 2,
00336     5, 2, 1, 1, 1, 1,
00337     3, 1, 4, 1,
00338     2, 1, 1,
00339     1, 1,
00340     // Row constraints
00341     2, 2, 2,
00342     2, 2, 2,
00343     1, 4,
00344     2, 1, 1,
00345     2, 1, 1,
00346     4, 1, 1, 1, 1,
00347     2, 1, 1,
00348     2, 1, 4,
00349     3, 1, 1, 1,
00350     3, 1, 1, 4,
00351     2, 1, 3,
00352     2, 1, 2,
00353     1, 5,
00354     2, 2, 2,
00355     2, 3, 3
00356   };
00357 
00363 static const int dragonfly[] =
00364   { 20, 20,
00365     // Column constraints.
00366     4, 1, 1, 1, 2,
00367     5, 3, 1, 2, 1, 1,
00368     5, 1, 4, 2, 1, 1,
00369     4, 1, 3, 2, 4,
00370     4, 1, 4, 6, 1,
00371     3, 1, 11, 1,
00372     4, 5, 1, 6, 2,
00373     1, 14,
00374     2, 7, 2,
00375     2, 7, 2,
00376     3, 6, 1, 1,
00377     2, 9, 2,
00378     4, 3, 1, 1, 1,
00379     3, 3, 1, 3,
00380     3, 2, 1, 3,
00381     3, 2, 1, 5,
00382     3, 3, 2, 2,
00383     3, 3, 3, 2,
00384     3, 2, 3, 2,
00385     2, 2, 6,
00386     // Row constraints
00387     2, 7, 1,
00388     3, 1, 1, 2,
00389     3, 2, 1, 2,
00390     3, 1, 2, 2,
00391     3, 4, 2, 3,
00392     3, 3, 1, 4,
00393     3, 3, 1, 3,
00394     3, 2, 1, 4,
00395     2, 2, 9,
00396     3, 2, 1, 5,
00397     2, 2, 7,
00398     1, 14,
00399     2, 8, 2,
00400     3, 6, 2, 2,
00401     4, 2, 8, 1, 3,
00402     4, 1, 5, 5, 2,
00403     5, 1, 3, 2, 4, 1,
00404     5, 3, 1, 2, 4, 1,
00405     5, 1, 1, 3, 1, 3,
00406     4, 2, 1, 1, 2
00407   };
00408 
00414 static const int p200[] = 
00415   { 25, 25,
00416     // Column constraints
00417     4, 1,1,2,2,
00418     3, 5,5,7,
00419     4, 5,2,2,9,
00420     4, 3,2,3,9,
00421     5, 1,1,3,2,7,
00422     3, 3,1,5,
00423     5, 7,1,1,1,3,
00424     6, 1,2,1,1,2,1,
00425     3, 4,2,4,
00426     4, 1,2,2,2,
00427     3, 4,6,2,
00428     4, 1,2,2,1,
00429     4, 3,3,2,1,
00430     3, 4,1,15,
00431     6, 1,1,1,3,1,1,
00432     6, 2,1,1,2,2,3,
00433     4, 1,4,4,1,
00434     4, 1,4,3,2,
00435     4, 1,1,2,2,
00436     5, 7,2,3,1,1,
00437     5, 2,1,1,1,5,
00438     3, 1,2,5,
00439     4, 1,1,1,3,
00440     3, 4,2,1,
00441     1, 3,
00442     // Row constraints
00443     3, 2,2,3,
00444     5, 4,1,1,1,4,
00445     5, 4,1,2,1,1,
00446     7, 4,1,1,1,1,1,1,
00447     6, 2,1,1,2,3,5,
00448     6, 1,1,1,1,2,1,
00449     5, 3,1,5,1,2,
00450     6, 3,2,2,1,2,2,
00451     7, 2,1,4,1,1,1,1,
00452     6, 2,2,1,2,1,2,
00453     6, 1,1,1,3,2,3,
00454     5, 1,1,2,7,3,
00455     5, 1,2,2,1,5,
00456     5, 3,2,2,1,2,
00457     4, 3,2,1,2,
00458     3, 5,1,2,
00459     4, 2,2,1,2,
00460     4, 4,2,1,2,
00461     4, 6,2,3,2,
00462     4, 7,4,3,2,
00463     3, 7,4,4,
00464     3, 7,1,4,
00465     3, 6,1,4,
00466     3, 4,2,2,
00467     2, 2,1
00468   };
00469 
00471 const int *specs[] = {heart, bear, crocodile, unknown, 
00472                       pinwheel, difficult, non_unique, dragonfly, p200};
00474 const unsigned n_examples = sizeof(specs)/sizeof(int*);
00476 
00477 // STATISTICS: example-any