00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include "examples/support.hh"
00039 #include "gecode/minimodel.hh"
00040
00041 namespace {
00042
00044 extern const int* specs[];
00046 extern const unsigned int n_examples;
00047
00048 }
00049
00064 class Nonogram : public Example {
00065 protected:
00067 const int* spec;
00069 BoolVarArray b;
00070
00072 int width(void) const {
00073 return spec[0];
00074 }
00076 int height(void) const {
00077 return spec[1];
00078 }
00079
00081 BoolVar pos(int h, int w) {
00082 return b[h*width() + w];
00083 }
00084
00086 DFA line(int& spos) {
00087 REG r0(0), r1(1);
00088 REG border = *r0;
00089 REG between = +r0;
00090 int size = spec[spos++];
00091 REG r = border + r1(spec[spos],spec[spos]);
00092 spos++;
00093 for (int i=size-1; i--; spos++)
00094 r += between + r1(spec[spos],spec[spos]);
00095 return r + border;
00096 }
00097
00098
00099 public:
00101 Nonogram(const SizeOptions& opt)
00102 : spec(specs[opt.size()]), b(this,width()*height(),0,1) {
00103 int spos = 2;
00104 MiniModel::Matrix<BoolVarArray> m(b, width(), height());
00105
00106
00107 for (int w = 0; w < width(); ++w)
00108 extensional(this, m.col(w), line(spos));
00109
00110
00111 for (int h = 0; h < height(); ++h)
00112 extensional(this, m.row(h), line(spos));
00113
00114
00115 branch(this, b, INT_VAR_NONE, INT_VAL_MAX);
00116 }
00117
00119 Nonogram(bool share, Nonogram& s) : Example(share,s), spec(s.spec) {
00120 b.update(this, share, s.b);
00121 }
00122
00124 virtual Space*
00125 copy(bool share) {
00126 return new Nonogram(share,*this);
00127 }
00128
00130 virtual void
00131 print(std::ostream& os) {
00132 for (int h = 0; h < height(); ++h) {
00133 os << '\t';
00134 for (int w = 0; w < width(); ++w)
00135 os << ((pos(h,w).val() == 1) ? '#' : ' ');
00136 os << std::endl;
00137 }
00138 os << std::endl;
00139 }
00140 };
00141
00142
00146 int
00147 main(int argc, char* argv[]) {
00148 SizeOptions opt("Nonogram");
00149 opt.size(8);
00150 opt.parse(argc,argv);
00151 if (opt.size() >= n_examples) {
00152 std::cerr << "Error: size must be between 0 and "
00153 << n_examples-1 << std::endl;
00154 return 1;
00155 }
00156 Example::run<Nonogram,DFS,SizeOptions>(opt);
00157 return 0;
00158 }
00159
00160 namespace {
00161
00173
00174 const int heart[] =
00175 { 9, 9,
00176
00177 1, 3,
00178 2, 2, 3,
00179 2, 2, 2,
00180 2, 2, 2,
00181 2, 2, 2,
00182 2, 2, 2,
00183 2, 2, 2,
00184 2, 2, 3,
00185 1, 3,
00186
00187 2, 2, 2,
00188 2, 4, 4,
00189 3, 1, 3, 1,
00190 3, 2, 1, 2,
00191 2, 1, 1,
00192 2, 2, 2,
00193 2, 2, 2,
00194 1, 3,
00195 1, 1
00196 };
00197
00199 const int bear[] =
00200 { 13, 8,
00201
00202 1, 2,
00203 2, 2, 1,
00204 2, 3, 2,
00205 1, 6,
00206 2, 1, 4,
00207 1, 3,
00208 1, 4,
00209 1, 4,
00210 1, 4,
00211 1, 5,
00212 1, 4,
00213 2, 1, 3,
00214 1, 2,
00215
00216 1, 1,
00217 1, 2,
00218 2, 4, 4,
00219 1, 12,
00220 1, 8,
00221 1, 9,
00222 2, 3, 4,
00223 2, 2, 2
00224 };
00225
00227 const int crocodile[] =
00228 { 15, 9,
00229
00230 1, 3,
00231 1, 4,
00232 2, 2, 2,
00233 2, 3, 1,
00234 2, 2, 3,
00235 2, 3, 2,
00236 2, 2, 3,
00237 2, 4, 2,
00238 2, 3, 2,
00239 1, 6,
00240 2, 1, 3,
00241 2, 1, 3,
00242 2, 1, 4,
00243 1, 5,
00244 1, 5,
00245
00246 1, 3,
00247 3, 2, 3, 2,
00248 2, 10, 3,
00249 1, 15,
00250 5, 1, 1, 1, 1, 6,
00251 2, 1, 7,
00252 2, 1, 4,
00253 2, 1, 4,
00254 1, 4
00255 };
00256
00258 const int unknown[] =
00259 { 10, 10,
00260
00261 1, 3,
00262 2, 2, 1,
00263 2, 2, 2,
00264 2, 2, 1,
00265 3, 1, 2, 1,
00266 2, 1, 1,
00267 3, 1, 4, 1,
00268 3, 1, 1, 2,
00269 2, 3, 1,
00270 1, 4,
00271
00272 1, 3,
00273 2, 2, 1,
00274 2, 1, 1,
00275 2, 1, 4,
00276 4, 1, 1, 1, 1,
00277 4, 2, 1, 1, 1,
00278 3, 2, 1, 1,
00279 2, 1, 2,
00280 2, 2, 3,
00281 1, 3
00282 };
00283
00285 const int pinwheel[] =
00286 { 6, 6,
00287
00288 2, 1, 2,
00289 1, 1,
00290 1, 2,
00291 1, 2,
00292 1, 1,
00293 2, 2, 1,
00294
00295 2, 2, 1,
00296 1, 1,
00297 1, 2,
00298 1, 2,
00299 1, 1,
00300 2, 1, 2
00301 };
00302
00304 const int difficult[] =
00305 { 15, 15,
00306
00307 1, 3,
00308 1, 2,
00309 1, 2,
00310 1, 1,
00311 1, 2,
00312 1, 3,
00313 1, 2,
00314 1, 4,
00315 1, 3,
00316 1, 4,
00317 2, 2, 1,
00318 2, 1, 1,
00319 2, 1, 1,
00320 2, 1, 1,
00321 1, 3,
00322
00323 1, 3,
00324 2, 1, 1,
00325 2, 1, 1,
00326 2, 1, 1,
00327 2, 1, 2,
00328 1, 5,
00329 1, 1,
00330 1, 2,
00331 1, 1,
00332 1, 1,
00333 2, 1, 2,
00334 2, 1, 2,
00335 2, 2, 1,
00336 2, 2, 2,
00337 1, 3
00338 };
00339
00341 const int non_unique[] =
00342 { 11, 15,
00343
00344 1, 5,
00345 3, 1, 2, 4,
00346 3, 2, 1, 3,
00347 4, 2, 2, 1, 1,
00348 4, 1, 1, 1, 1,
00349 2, 1, 5,
00350 5, 2, 1, 1, 3, 2,
00351 5, 2, 1, 1, 1, 1,
00352 3, 1, 4, 1,
00353 2, 1, 1,
00354 1, 1,
00355
00356 2, 2, 2,
00357 2, 2, 2,
00358 1, 4,
00359 2, 1, 1,
00360 2, 1, 1,
00361 4, 1, 1, 1, 1,
00362 2, 1, 1,
00363 2, 1, 4,
00364 3, 1, 1, 1,
00365 3, 1, 1, 4,
00366 2, 1, 3,
00367 2, 1, 2,
00368 1, 5,
00369 2, 2, 2,
00370 2, 3, 3
00371 };
00372
00378 const int dragonfly[] =
00379 { 20, 20,
00380
00381 4, 1, 1, 1, 2,
00382 5, 3, 1, 2, 1, 1,
00383 5, 1, 4, 2, 1, 1,
00384 4, 1, 3, 2, 4,
00385 4, 1, 4, 6, 1,
00386 3, 1, 11, 1,
00387 4, 5, 1, 6, 2,
00388 1, 14,
00389 2, 7, 2,
00390 2, 7, 2,
00391 3, 6, 1, 1,
00392 2, 9, 2,
00393 4, 3, 1, 1, 1,
00394 3, 3, 1, 3,
00395 3, 2, 1, 3,
00396 3, 2, 1, 5,
00397 3, 3, 2, 2,
00398 3, 3, 3, 2,
00399 3, 2, 3, 2,
00400 2, 2, 6,
00401
00402 2, 7, 1,
00403 3, 1, 1, 2,
00404 3, 2, 1, 2,
00405 3, 1, 2, 2,
00406 3, 4, 2, 3,
00407 3, 3, 1, 4,
00408 3, 3, 1, 3,
00409 3, 2, 1, 4,
00410 2, 2, 9,
00411 3, 2, 1, 5,
00412 2, 2, 7,
00413 1, 14,
00414 2, 8, 2,
00415 3, 6, 2, 2,
00416 4, 2, 8, 1, 3,
00417 4, 1, 5, 5, 2,
00418 5, 1, 3, 2, 4, 1,
00419 5, 3, 1, 2, 4, 1,
00420 5, 1, 1, 3, 1, 3,
00421 4, 2, 1, 1, 2
00422 };
00423
00429 const int p200[] =
00430 { 25, 25,
00431
00432 4, 1,1,2,2,
00433 3, 5,5,7,
00434 4, 5,2,2,9,
00435 4, 3,2,3,9,
00436 5, 1,1,3,2,7,
00437 3, 3,1,5,
00438 5, 7,1,1,1,3,
00439 6, 1,2,1,1,2,1,
00440 3, 4,2,4,
00441 4, 1,2,2,2,
00442 3, 4,6,2,
00443 4, 1,2,2,1,
00444 4, 3,3,2,1,
00445 3, 4,1,15,
00446 6, 1,1,1,3,1,1,
00447 6, 2,1,1,2,2,3,
00448 4, 1,4,4,1,
00449 4, 1,4,3,2,
00450 4, 1,1,2,2,
00451 5, 7,2,3,1,1,
00452 5, 2,1,1,1,5,
00453 3, 1,2,5,
00454 4, 1,1,1,3,
00455 3, 4,2,1,
00456 1, 3,
00457
00458 3, 2,2,3,
00459 5, 4,1,1,1,4,
00460 5, 4,1,2,1,1,
00461 7, 4,1,1,1,1,1,1,
00462 6, 2,1,1,2,3,5,
00463 6, 1,1,1,1,2,1,
00464 5, 3,1,5,1,2,
00465 6, 3,2,2,1,2,2,
00466 7, 2,1,4,1,1,1,1,
00467 6, 2,2,1,2,1,2,
00468 6, 1,1,1,3,2,3,
00469 5, 1,1,2,7,3,
00470 5, 1,2,2,1,5,
00471 5, 3,2,2,1,2,
00472 4, 3,2,1,2,
00473 3, 5,1,2,
00474 4, 2,2,1,2,
00475 4, 4,2,1,2,
00476 4, 6,2,3,2,
00477 4, 7,4,3,2,
00478 3, 7,4,4,
00479 3, 7,1,4,
00480 3, 6,1,4,
00481 3, 4,2,2,
00482 2, 2,1
00483 };
00484
00485 const int *specs[] = {heart, bear, crocodile, unknown,
00486 pinwheel, difficult, non_unique, dragonfly, p200};
00487 const unsigned n_examples = sizeof(specs)/sizeof(int*);
00489
00490 }
00491
00492