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 <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
00109 for (int w=0; w<width(); w++)
00110 extensional(*this, m.col(w), line(spos));
00111
00112 for (int h=0; h<height(); h++)
00113 extensional(*this, m.row(h), line(spos));
00114 }
00115
00116
00117 int cols = 0;
00118
00119 int rows = 0;
00120
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
00135
00136
00137
00138
00139
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
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
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
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
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
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
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
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
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
00321 2, 1, 2,
00322 1, 1,
00323 1, 2,
00324 1, 2,
00325 1, 1,
00326 2, 2, 1,
00327
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
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
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
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
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
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
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
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
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
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
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