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: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00011 * $Revision: 11473 $ 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 00043 using namespace Gecode; 00044 00045 namespace { 00046 00048 extern const int* specs[]; 00050 extern const unsigned int n_examples; 00051 00053 struct Slack { 00054 int slack, n; 00055 bool row; 00056 bool operator<(const Slack& rhs) const { return slack < rhs.slack; } 00057 }; 00058 } 00059 00077 class Nonogram : public Script { 00078 protected: 00080 const int* spec; 00082 BoolVarArray b; 00083 00085 int width(void) const { 00086 return spec[0]; 00087 } 00089 int height(void) const { 00090 return spec[1]; 00091 } 00092 00094 DFA line(int& spos) { 00095 REG r0(0), r1(1); 00096 REG border = *r0; 00097 REG between = +r0; 00098 int hints = spec[spos++]; 00099 REG r = border; 00100 if (hints > 0) { 00101 r += r1(spec[spos],spec[spos]); 00102 spos++; 00103 for (int i=hints-1; i--; spos++) 00104 r += between + r1(spec[spos],spec[spos]); 00105 } 00106 return r + border; 00107 } 00108 00109 public: 00110 // Branching variants 00111 enum { 00112 BRANCH_NONE, 00113 BRANCH_AFC, 00114 }; 00115 00117 Nonogram(const SizeOptions& opt) 00118 : spec(specs[opt.size()]), b(*this,width()*height(),0,1) { 00119 Matrix<BoolVarArray> m(b, width(), height()); 00120 00121 { 00122 int spos = 2; 00123 // Post constraints for columns 00124 for (int w=0; w<width(); w++) 00125 extensional(*this, m.col(w), line(spos)); 00126 // Post constraints for rows 00127 for (int h=0; h<height(); h++) 00128 extensional(*this, m.row(h), line(spos)); 00129 } 00130 00131 00132 00133 switch (opt.branching()) { 00134 case BRANCH_NONE: 00135 { 00136 /* 00137 * The following branches either by columns or rows, depending on 00138 * whether there are more hints relative to the height or width 00139 * for columns or rows. 00140 * 00141 * This idea is due to Pascal Van Hentenryck and has been suggested 00142 * to us by Hakan Kjellerstrand. 00143 */ 00144 00145 // Number of hints for columns 00146 int cols = 0; 00147 // Number of hints for rows 00148 int rows = 0; 00149 int spos = 2; 00150 for (int w=0; w<width(); w++) { 00151 int hint = spec[spos++]; 00152 cols += hint; spos += hint; 00153 } 00154 for (int h=0; h<height(); h++) { 00155 int hint = spec[spos++]; 00156 rows += hint; spos += hint; 00157 } 00158 00159 if (rows*width() > cols*height()) { 00160 for (int w=0; w<width(); w++) 00161 branch(*this, m.col(w), INT_VAR_NONE, INT_VAL_MAX); 00162 } else { 00163 for (int h=0; h<height(); h++) 00164 branch(*this, m.row(h), INT_VAR_NONE, INT_VAL_MAX); 00165 } 00166 } 00167 break; 00168 case BRANCH_AFC: 00169 /* 00170 * The following just uses the AFC for branching. This is 00171 * equivalent to SIZE/AFC in this case since the variables are 00172 * binary. 00173 */ 00174 branch(*this, b, INT_VAR_AFC_MAX, INT_VAL_MAX); 00175 break; 00176 } 00177 } 00178 00180 Nonogram(bool share, Nonogram& s) : Script(share,s), spec(s.spec) { 00181 b.update(*this, share, s.b); 00182 } 00183 00185 virtual Space* 00186 copy(bool share) { 00187 return new Nonogram(share,*this); 00188 } 00189 00191 virtual void 00192 print(std::ostream& os) const { 00193 Matrix<BoolVarArray> m(b, width(), height()); 00194 for (int h = 0; h < height(); ++h) { 00195 os << '\t'; 00196 for (int w = 0; w < width(); ++w) 00197 os << ((m(w,h).val() == 1) ? '#' : ' '); 00198 os << std::endl; 00199 } 00200 os << std::endl; 00201 } 00202 }; 00203 00204 00208 int 00209 main(int argc, char* argv[]) { 00210 SizeOptions opt("Nonogram"); 00211 opt.size(8); 00212 opt.branching(Nonogram::BRANCH_AFC); 00213 opt.branching(Nonogram::BRANCH_NONE, "none", 00214 "Branch on rows/columns in order"); 00215 opt.branching(Nonogram::BRANCH_AFC, "afc", 00216 "Use AFC for branching"); 00217 opt.parse(argc,argv); 00218 if (opt.size() >= n_examples) { 00219 std::cerr << "Error: size must be between 0 and " 00220 << n_examples-1 << std::endl; 00221 return 1; 00222 } 00223 Script::run<Nonogram,DFS,SizeOptions>(opt); 00224 return 0; 00225 } 00226 00227 namespace { 00228 00240 00241 const int heart[] = 00242 { 9, 9, 00243 // Column constraints. 00244 1, 3, 00245 2, 2, 3, 00246 2, 2, 2, 00247 2, 2, 2, 00248 2, 2, 2, 00249 2, 2, 2, 00250 2, 2, 2, 00251 2, 2, 3, 00252 1, 3, 00253 // Row constraints 00254 2, 2, 2, 00255 2, 4, 4, 00256 3, 1, 3, 1, 00257 3, 2, 1, 2, 00258 2, 1, 1, 00259 2, 2, 2, 00260 2, 2, 2, 00261 1, 3, 00262 1, 1 00263 }; 00264 00266 const int bear[] = 00267 { 13, 8, 00268 // Column constraints 00269 1, 2, 00270 2, 2, 1, 00271 2, 3, 2, 00272 1, 6, 00273 2, 1, 4, 00274 1, 3, 00275 1, 4, 00276 1, 4, 00277 1, 4, 00278 1, 5, 00279 1, 4, 00280 2, 1, 3, 00281 1, 2, 00282 // Row constraints 00283 1, 1, 00284 1, 2, 00285 2, 4, 4, 00286 1, 12, 00287 1, 8, 00288 1, 9, 00289 2, 3, 4, 00290 2, 2, 2 00291 }; 00292 00294 const int crocodile[] = 00295 { 15, 9, 00296 // Column constraints 00297 1, 3, 00298 1, 4, 00299 2, 2, 2, 00300 2, 3, 1, 00301 2, 2, 3, 00302 2, 3, 2, 00303 2, 2, 3, 00304 2, 4, 2, 00305 2, 3, 2, 00306 1, 6, 00307 2, 1, 3, 00308 2, 1, 3, 00309 2, 1, 4, 00310 1, 5, 00311 1, 5, 00312 // Row constraints 00313 1, 3, 00314 3, 2, 3, 2, 00315 2, 10, 3, 00316 1, 15, 00317 5, 1, 1, 1, 1, 6, 00318 2, 1, 7, 00319 2, 1, 4, 00320 2, 1, 4, 00321 1, 4 00322 }; 00323 00325 const int unknown[] = 00326 { 10, 10, 00327 // Column constraints 00328 1, 3, 00329 2, 2, 1, 00330 2, 2, 2, 00331 2, 2, 1, 00332 3, 1, 2, 1, 00333 2, 1, 1, 00334 3, 1, 4, 1, 00335 3, 1, 1, 2, 00336 2, 3, 1, 00337 1, 4, 00338 // Row constraints 00339 1, 3, 00340 2, 2, 1, 00341 2, 1, 1, 00342 2, 1, 4, 00343 4, 1, 1, 1, 1, 00344 4, 2, 1, 1, 1, 00345 3, 2, 1, 1, 00346 2, 1, 2, 00347 2, 2, 3, 00348 1, 3 00349 }; 00350 00352 const int pinwheel[] = 00353 { 6, 6, 00354 // Column constraints 00355 2, 1, 2, 00356 1, 1, 00357 1, 2, 00358 1, 2, 00359 1, 1, 00360 2, 2, 1, 00361 // Row constraints 00362 2, 2, 1, 00363 1, 1, 00364 1, 2, 00365 1, 2, 00366 1, 1, 00367 2, 1, 2 00368 }; 00369 00371 const int difficult[] = 00372 { 15, 15, 00373 // Column constraints 00374 1, 3, 00375 1, 2, 00376 1, 2, 00377 1, 1, 00378 1, 2, 00379 1, 3, 00380 1, 2, 00381 1, 4, 00382 1, 3, 00383 1, 4, 00384 2, 2, 1, 00385 2, 1, 1, 00386 2, 1, 1, 00387 2, 1, 1, 00388 1, 3, 00389 // Row constraints 00390 1, 3, 00391 2, 1, 1, 00392 2, 1, 1, 00393 2, 1, 1, 00394 2, 1, 2, 00395 1, 5, 00396 1, 1, 00397 1, 2, 00398 1, 1, 00399 1, 1, 00400 2, 1, 2, 00401 2, 1, 2, 00402 2, 2, 1, 00403 2, 2, 2, 00404 1, 3 00405 }; 00406 00408 const int non_unique[] = 00409 { 11, 15, 00410 // Column constraints 00411 1, 5, 00412 3, 1, 2, 4, 00413 3, 2, 1, 3, 00414 4, 2, 2, 1, 1, 00415 4, 1, 1, 1, 1, 00416 2, 1, 5, 00417 5, 2, 1, 1, 3, 2, 00418 5, 2, 1, 1, 1, 1, 00419 3, 1, 4, 1, 00420 2, 1, 1, 00421 1, 1, 00422 // Row constraints 00423 2, 2, 2, 00424 2, 2, 2, 00425 1, 4, 00426 2, 1, 1, 00427 2, 1, 1, 00428 4, 1, 1, 1, 1, 00429 2, 1, 1, 00430 2, 1, 4, 00431 3, 1, 1, 1, 00432 3, 1, 1, 4, 00433 2, 1, 3, 00434 2, 1, 2, 00435 1, 5, 00436 2, 2, 2, 00437 2, 3, 3 00438 }; 00439 00445 const int dragonfly[] = 00446 { 20, 20, 00447 // Column constraints. 00448 4, 1, 1, 1, 2, 00449 5, 3, 1, 2, 1, 1, 00450 5, 1, 4, 2, 1, 1, 00451 4, 1, 3, 2, 4, 00452 4, 1, 4, 6, 1, 00453 3, 1, 11, 1, 00454 4, 5, 1, 6, 2, 00455 1, 14, 00456 2, 7, 2, 00457 2, 7, 2, 00458 3, 6, 1, 1, 00459 2, 9, 2, 00460 4, 3, 1, 1, 1, 00461 3, 3, 1, 3, 00462 3, 2, 1, 3, 00463 3, 2, 1, 5, 00464 3, 3, 2, 2, 00465 3, 3, 3, 2, 00466 3, 2, 3, 2, 00467 2, 2, 6, 00468 // Row constraints 00469 2, 7, 1, 00470 3, 1, 1, 2, 00471 3, 2, 1, 2, 00472 3, 1, 2, 2, 00473 3, 4, 2, 3, 00474 3, 3, 1, 4, 00475 3, 3, 1, 3, 00476 3, 2, 1, 4, 00477 2, 2, 9, 00478 3, 2, 1, 5, 00479 2, 2, 7, 00480 1, 14, 00481 2, 8, 2, 00482 3, 6, 2, 2, 00483 4, 2, 8, 1, 3, 00484 4, 1, 5, 5, 2, 00485 5, 1, 3, 2, 4, 1, 00486 5, 3, 1, 2, 4, 1, 00487 5, 1, 1, 3, 1, 3, 00488 4, 2, 1, 1, 2 00489 }; 00490 00492 const int castle[] = { 00493 60, 35, 00494 // Column constraints 00495 7, 2,3,1,5,1,7,1, 00496 7, 2,4,2,3,2,3,5, 00497 8, 2,6,3,1,1,5,1,5, 00498 10, 2,4,2,1,1,1,4,1,1,2, 00499 7, 2,8,2,1,5,2,5, 00500 7, 3,1,6,2,5,1,5, 00501 9, 3,3,3,1,1,6,1,1,1, 00502 9, 3,2,2,2,2,8,1,1,3, 00503 7, 1,4,4,3,7,1,1, 00504 7, 1,2,2,2,3,7,9, 00505 8, 1,2,3,1,1,5,2,2, 00506 7, 2,2,3,1,1,6,1, 00507 6, 1,3,1,5,4,1, 00508 8, 1,3,1,1,6,1,3,1, 00509 8, 3,3,4,5,1,4,2,1, 00510 6, 2,3,3,9,7,1, 00511 8, 2,3,2,2,1,1,3,5, 00512 8, 4,2,1,1,1,1,2,3, 00513 7, 4,2,2,1,4,3,2, 00514 4, 4,3,16,2, 00515 5, 1,2,5,7,1, 00516 6, 4,3,2,2,7,1, 00517 5, 2,3,1,10,1, 00518 6, 2,4,2,1,4,1, 00519 5, 1,6,7,3,1, 00520 4, 3,11,3,1, 00521 5, 7,1,11,2,1, 00522 7, 2,2,2,2,2,2,2, 00523 7, 3,1,1,1,1,2,1, 00524 7, 2,2,2,2,1,1,1, 00525 7, 1,1,1,1,2,1,2, 00526 8, 2,2,2,2,1,1,1,1, 00527 5, 4,1,1,2,2, 00528 5, 5,2,17,2,1, 00529 6, 9,2,3,1,4,2, 00530 6, 9,4,2,1,1,1, 00531 5, 5,4,2,1,4, 00532 7, 11,1,2,1,4,1,2, 00533 5, 3,4,2,4,4, 00534 8, 2,1,4,1,2,1,5,2, 00535 5, 8,4,1,1,2, 00536 5, 1,1,3,2,3, 00537 6, 1,3,1,8,1,6, 00538 4, 2,1,7,14, 00539 7, 1,2,4,4,1,2,3, 00540 10, 1,1,4,2,1,1,1,1,1,4, 00541 6, 3,5,3,1,1,4, 00542 6, 2,4,2,2,1,2, 00543 5, 4,2,3,8,4, 00544 5, 4,15,2,2,4, 00545 6, 4,1,10,2,1,2, 00546 6, 2,12,6,1,2,4, 00547 7, 3,1,3,1,3,3,4, 00548 6, 3,1,2,3,4,1, 00549 7, 5,2,2,2,3,3,3, 00550 9, 1,2,2,2,2,4,1,1,3, 00551 7, 2,1,4,2,7,1,1, 00552 6, 5,2,2,3,6,3, 00553 7, 3,3,2,2,3,2,3, 00554 7, 4,1,2,1,1,2,1, 00555 00556 // Row constraints 00557 4, 12,1,1,1, 00558 5, 8,6,3,1,3, 00559 6, 5,8,4,3,1,5, 00560 8, 7,3,4,1,3,5,1,7, 00561 13, 2,2,4,9,1,5,1,1,1,1,1,1,1, 00562 8, 4,5,10,2,1,8,7,1, 00563 7, 5,1,3,3,16,1,2, 00564 8, 8,5,1,2,4,9,1,3, 00565 12, 4,5,3,14,1,1,1,1,4,1,1,3, 00566 19, 3,3,2,2,2,4,1,1,1,1,1,1,1,1,3,1,1,3,2, 00567 11, 8,2,7,2,1,1,2,1,1,3,3, 00568 13, 1,5,9,12,2,1,1,3,1,1,2,2,1, 00569 17, 3,2,2,1,1,1,1,4,1,1,1,3,3,1,1,2,2, 00570 12, 5,2,2,2,2,1,5,2,1,1,2,5, 00571 12, 3,5,9,2,1,1,6,3,1,3,2,3, 00572 12, 1,4,1,1,1,4,1,5,5,3,3,3, 00573 10, 4,1,1,1,1,3,4,6,6,3, 00574 12, 3,1,3,1,1,3,3,1,1,4,6,1, 00575 11, 3,1,5,1,1,3,1,1,9,4,1, 00576 14, 2,1,1,7,1,4,1,1,1,1,1,1,3,5, 00577 11, 9,2,1,3,1,1,1,1,4,2,1, 00578 10, 1,14,1,1,2,2,2,10,1,2, 00579 10, 1,9,2,1,2,6,1,5,3,2, 00580 12, 1,9,9,1,2,2,3,1,1,4,3,1, 00581 10, 10,1,3,4,1,3,2,1,2,8, 00582 9, 9,1,3,5,1,1,1,2,7, 00583 12, 4,5,1,2,5,1,3,1,1,2,1,3, 00584 14, 1,1,1,1,2,6,2,3,2,1,1,2,3,1, 00585 11, 1,6,1,5,7,1,3,3,2,4,3, 00586 10, 1,2,1,2,9,1,5,2,6,2, 00587 8, 10,2,2,13,1,3,3,1, 00588 11, 2,2,1,6,2,3,3,2,2,2,1, 00589 12, 2,2,1,1,12,2,2,9,2,2,2,2, 00590 9, 5,1,2,4,1,5,11,2,2, 00591 3, 15,6,18, 00592 }; 00593 00599 const int p200[] = 00600 { 25, 25, 00601 // Column constraints 00602 4, 1,1,2,2, 00603 3, 5,5,7, 00604 4, 5,2,2,9, 00605 4, 3,2,3,9, 00606 5, 1,1,3,2,7, 00607 3, 3,1,5, 00608 5, 7,1,1,1,3, 00609 6, 1,2,1,1,2,1, 00610 3, 4,2,4, 00611 4, 1,2,2,2, 00612 3, 4,6,2, 00613 4, 1,2,2,1, 00614 4, 3,3,2,1, 00615 3, 4,1,15, 00616 6, 1,1,1,3,1,1, 00617 6, 2,1,1,2,2,3, 00618 4, 1,4,4,1, 00619 4, 1,4,3,2, 00620 4, 1,1,2,2, 00621 5, 7,2,3,1,1, 00622 5, 2,1,1,1,5, 00623 3, 1,2,5, 00624 4, 1,1,1,3, 00625 3, 4,2,1, 00626 1, 3, 00627 // Row constraints 00628 3, 2,2,3, 00629 5, 4,1,1,1,4, 00630 5, 4,1,2,1,1, 00631 7, 4,1,1,1,1,1,1, 00632 6, 2,1,1,2,3,5, 00633 6, 1,1,1,1,2,1, 00634 5, 3,1,5,1,2, 00635 6, 3,2,2,1,2,2, 00636 7, 2,1,4,1,1,1,1, 00637 6, 2,2,1,2,1,2, 00638 6, 1,1,1,3,2,3, 00639 5, 1,1,2,7,3, 00640 5, 1,2,2,1,5, 00641 5, 3,2,2,1,2, 00642 4, 3,2,1,2, 00643 3, 5,1,2, 00644 4, 2,2,1,2, 00645 4, 4,2,1,2, 00646 4, 6,2,3,2, 00647 4, 7,4,3,2, 00648 3, 7,4,4, 00649 3, 7,1,4, 00650 3, 6,1,4, 00651 3, 4,2,2, 00652 2, 2,1 00653 }; 00654 00655 // The following instances are from the http://webpbn.com site and 00656 // are all designed by Jan Wolter. 00657 // See also the survey at http://webpbn.com/survey/ 00658 00660 const int webpbn436[]= 00661 { 40, 35, 00662 // Column constraints 00663 1, 1, 00664 2, 3, 2, 00665 3, 2, 3, 3, 00666 3, 3, 3, 3, 00667 4, 3, 3, 3, 3, 00668 4, 4, 2, 2, 2, 00669 4, 3, 3, 2, 3, 00670 4, 3, 2, 2, 2, 00671 3, 3, 2, 6, 00672 2, 2, 9, 00673 3, 2, 3, 3, 00674 5, 4, 4, 3, 2, 4, 00675 5, 7, 2, 5, 2, 6, 00676 6, 12, 2, 3, 2, 3, 2, 00677 6, 3, 1, 2, 2, 2, 3, 00678 6, 2, 2, 3, 2, 2, 2, 00679 6, 6, 2, 6, 2, 2, 2, 00680 5, 12, 4, 3, 2, 2, 00681 4, 12, 2, 2, 2, 00682 3, 2, 6, 2, 00683 4, 2, 6, 5, 2, 00684 4, 10, 9, 2, 2, 00685 5, 12, 3, 3, 2, 2, 00686 7, 6, 2, 2, 2, 2, 2, 2, 00687 6, 2, 2, 3, 2, 2, 2, 00688 6, 4, 3, 2, 2, 2, 3, 00689 6, 7, 3, 3, 2, 3, 2, 00690 5, 5, 3, 5, 2, 6, 00691 5, 4, 3, 3, 3, 4, 00692 3, 3, 5, 3, 00693 2, 3, 9, 00694 3, 4, 2, 6, 00695 4, 4, 2, 2, 2, 00696 4, 4, 2, 2, 3, 00697 4, 3, 2, 2, 3, 00698 3, 3, 3, 3, 00699 3, 3, 3, 3, 00700 3, 4, 3, 3, 00701 3, 2, 3, 3, 00702 2, 2, 1, 00703 // Row constraints 00704 2, 2, 2, 00705 3, 2, 3, 2, 00706 4, 3, 3, 3, 2, 00707 4, 3, 3, 3, 3, 00708 6, 2, 3, 3, 3, 3, 2, 00709 6, 3, 3, 3, 3, 3, 3, 00710 6, 4, 2, 3, 2, 2, 4, 00711 7, 4, 2, 2, 2, 2, 3, 1, 00712 7, 3, 1, 2, 2, 2, 3, 3, 00713 7, 3, 2, 2, 2, 2, 2, 4, 00714 5, 3, 2, 15, 2, 4, 00715 3, 5, 19, 4, 00716 4, 6, 4, 3, 3, 00717 3, 6, 4, 4, 00718 4, 2, 4, 6, 2, 00719 6, 2, 2, 3, 3, 3, 2, 00720 6, 9, 2, 2, 2, 3, 9, 00721 7, 10, 2, 2, 2, 2, 2, 10, 00722 9, 4, 2, 3, 3, 2, 2, 3, 2, 5, 00723 5, 2, 5, 2, 4, 2, 00724 5, 5, 3, 2, 2, 5, 00725 5, 6, 3, 2, 3, 7, 00726 4, 6, 8, 9, 7, 00727 4, 4, 8, 7, 5, 00728 1, 4, 00729 1, 2, 00730 1, 2, 00731 1, 14, 00732 1, 16, 00733 2, 3, 3, 00734 2, 2, 2, 00735 2, 2, 2, 00736 2, 4, 4, 00737 1, 16, 00738 1, 12, 00739 }; 00740 00742 const int webpbn21[]= 00743 { 14, 25, 00744 // Column constraints 00745 1, 2, 00746 2, 4, 6, 00747 4, 9, 4, 4, 2, 00748 4, 1, 6, 2, 6, 00749 3, 1, 5, 2, 00750 2, 1, 6, 00751 2, 1, 5, 00752 2, 1, 4, 00753 2, 1, 4, 00754 3, 1, 4, 2, 00755 3, 1, 4, 6, 00756 5, 1, 6, 4, 4, 2, 00757 3, 9, 2, 6, 00758 2, 4, 2, 00759 // Row constraints 00760 1, 9, 00761 2, 1, 1, 00762 3, 1, 1, 1, 00763 3, 1, 3, 1, 00764 1, 13, 00765 1, 13, 00766 1, 13, 00767 1, 13, 00768 2, 2, 2, 00769 2, 2, 2, 00770 0, 00771 2, 2, 2, 00772 2, 2, 2, 00773 2, 2, 2, 00774 2, 2, 2, 00775 2, 2, 2, 00776 2, 2, 2, 00777 2, 2, 2, 00778 2, 2, 2, 00779 2, 2, 2, 00780 2, 2, 2, 00781 2, 2, 2, 00782 2, 2, 2, 00783 2, 2, 2, 00784 2, 2, 2, 00785 }; 00786 00788 const int webpbn27[]= 00789 { 27, 23, 00790 // Column constraints 00791 2, 4, 12, 00792 3, 6, 1, 1, 00793 3, 8, 1, 1, 00794 5, 3, 2, 2, 1, 1, 00795 6, 2, 1, 1, 2, 1, 6, 00796 4, 1, 1, 1, 1, 00797 6, 3, 1, 1, 2, 1, 1, 00798 5, 3, 2, 3, 1, 1, 00799 3, 10, 1, 1, 00800 5, 4, 2, 2, 1, 1, 00801 6, 3, 1, 1, 2, 1, 1, 00802 4, 2, 1, 1, 1, 00803 6, 3, 1, 1, 2, 1, 1, 00804 5, 3, 2, 3, 1, 6, 00805 3, 10, 1, 1, 00806 5, 4, 2, 2, 1, 1, 00807 6, 3, 1, 1, 2, 1, 1, 00808 4, 1, 1, 1, 9, 00809 6, 2, 1, 1, 2, 1, 1, 00810 5, 2, 2, 3, 1, 3, 00811 3, 8, 1, 5, 00812 3, 6, 1, 1, 00813 3, 4, 9, 1, 00814 2, 1, 1, 00815 2, 2, 1, 00816 2, 1, 1, 00817 1, 4, 00818 // Row constraints 00819 1, 11, 00820 1, 17, 00821 4, 3, 5, 5, 3, 00822 4, 2, 2, 2, 1, 00823 7, 2, 1, 3, 1, 3, 1, 4, 00824 4, 3, 3, 3, 3, 00825 7, 5, 1, 3, 1, 3, 1, 3, 00826 4, 3, 2, 2, 4, 00827 4, 5, 5, 5, 5, 00828 1, 23, 00829 0, 00830 1, 23, 00831 2, 1, 1, 00832 2, 1, 1, 00833 3, 1, 2, 1, 00834 4, 1, 1, 1, 1, 00835 4, 1, 1, 1, 1, 00836 5, 1, 10, 1, 2, 1, 00837 7, 1, 1, 1, 1, 1, 1, 3, 00838 8, 1, 1, 1, 1, 1, 1, 1, 1, 00839 7, 1, 1, 1, 1, 1, 1, 1, 00840 6, 1, 1, 1, 1, 2, 2, 00841 3, 5, 5, 3, 00842 }; 00843 00845 const int webpbn1[]= 00846 { 5, 10, 00847 // Column constraints 00848 2, 2, 1, 00849 3, 2, 1, 3, 00850 1, 7, 00851 2, 1, 3, 00852 2, 2, 1, 00853 // Row constraints 00854 1, 2, 00855 2, 2, 1, 00856 2, 1, 1, 00857 1, 3, 00858 2, 1, 1, 00859 2, 1, 1, 00860 1, 2, 00861 2, 1, 1, 00862 2, 1, 2, 00863 1, 2, 00864 }; 00865 00867 const int webpbn6[]= 00868 { 20, 20, 00869 // Column constraints 00870 1, 5, 00871 2, 5, 3, 00872 3, 2, 3, 4, 00873 3, 1, 7, 2, 00874 1, 8, 00875 1, 9, 00876 1, 9, 00877 1, 8, 00878 1, 7, 00879 1, 8, 00880 1, 9, 00881 1, 10, 00882 1, 13, 00883 2, 6, 2, 00884 1, 4, 00885 1, 6, 00886 1, 6, 00887 1, 5, 00888 1, 6, 00889 1, 6, 00890 // Row constraints 00891 1, 2, 00892 1, 2, 00893 1, 1, 00894 1, 1, 00895 2, 1, 3, 00896 2, 2, 5, 00897 4, 1, 7, 1, 1, 00898 4, 1, 8, 2, 2, 00899 3, 1, 9, 5, 00900 2, 2, 16, 00901 2, 1, 17, 00902 2, 7, 11, 00903 3, 5, 5, 3, 00904 2, 5, 4, 00905 2, 3, 3, 00906 2, 2, 2, 00907 2, 2, 1, 00908 2, 1, 1, 00909 2, 2, 2, 00910 2, 2, 2, 00911 }; 00912 00914 const int webpbn23[]= 00915 { 10, 11, 00916 // Column constraints 00917 1, 1, 00918 1, 3, 00919 1, 1, 00920 2, 2, 2, 00921 1, 2, 00922 1, 4, 00923 1, 1, 00924 1, 3, 00925 1, 3, 00926 1, 1, 00927 // Row constraints 00928 1, 1, 00929 1, 3, 00930 1, 1, 00931 1, 2, 00932 1, 1, 00933 1, 3, 00934 1, 3, 00935 1, 1, 00936 1, 2, 00937 1, 2, 00938 1, 4, 00939 }; 00940 00942 const int webpbn16[]= 00943 { 34, 34, 00944 // Column constraints 00945 2, 1, 1, 00946 2, 2, 2, 00947 2, 3, 3, 00948 4, 2, 1, 1, 2, 00949 4, 2, 1, 1, 2, 00950 4, 1, 1, 1, 1, 00951 4, 1, 1, 1, 1, 00952 1, 18, 00953 6, 2, 1, 1, 1, 1, 2, 00954 6, 1, 1, 1, 1, 1, 1, 00955 6, 1, 1, 1, 1, 1, 1, 00956 1, 26, 00957 8, 2, 1, 1, 1, 1, 1, 1, 2, 00958 8, 2, 1, 1, 2, 2, 1, 1, 2, 00959 8, 2, 1, 1, 2, 2, 1, 1, 2, 00960 2, 14, 14, 00961 4, 1, 1, 1, 1, 00962 4, 1, 1, 1, 1, 00963 2, 14, 14, 00964 8, 2, 1, 1, 2, 2, 1, 1, 2, 00965 8, 2, 1, 1, 2, 2, 1, 1, 2, 00966 8, 2, 1, 1, 1, 1, 1, 1, 2, 00967 1, 26, 00968 6, 1, 1, 1, 1, 1, 1, 00969 6, 1, 1, 1, 1, 1, 1, 00970 6, 2, 1, 1, 1, 1, 2, 00971 1, 18, 00972 4, 1, 1, 1, 1, 00973 4, 1, 1, 1, 1, 00974 4, 2, 1, 1, 2, 00975 4, 2, 1, 1, 2, 00976 2, 3, 3, 00977 2, 2, 2, 00978 2, 1, 1, 00979 // Row constraints 00980 2, 1, 1, 00981 2, 2, 2, 00982 2, 3, 3, 00983 4, 2, 1, 1, 2, 00984 4, 2, 1, 1, 2, 00985 4, 1, 1, 1, 1, 00986 4, 1, 1, 1, 1, 00987 1, 18, 00988 6, 2, 1, 1, 1, 1, 2, 00989 6, 1, 1, 1, 1, 1, 1, 00990 6, 1, 1, 1, 1, 1, 1, 00991 1, 26, 00992 8, 2, 1, 1, 1, 1, 1, 1, 2, 00993 8, 2, 1, 1, 2, 2, 1, 1, 2, 00994 8, 2, 1, 1, 2, 2, 1, 1, 2, 00995 2, 14, 14, 00996 4, 1, 1, 1, 1, 00997 4, 1, 1, 1, 1, 00998 2, 14, 14, 00999 8, 2, 1, 1, 2, 2, 1, 1, 2, 01000 8, 2, 1, 1, 2, 2, 1, 1, 2, 01001 8, 2, 1, 1, 1, 1, 1, 1, 2, 01002 1, 26, 01003 6, 1, 1, 1, 1, 1, 1, 01004 6, 1, 1, 1, 1, 1, 1, 01005 6, 2, 1, 1, 1, 1, 2, 01006 1, 18, 01007 4, 1, 1, 1, 1, 01008 4, 1, 1, 1, 1, 01009 4, 2, 1, 1, 2, 01010 4, 2, 1, 1, 2, 01011 2, 3, 3, 01012 2, 2, 2, 01013 2, 1, 1, 01014 }; 01015 01017 const int webpbn529[]= 01018 { 45, 45, 01019 // Column constraints 01020 6, 7, 1, 1, 1, 1, 1, 01021 13, 2, 2, 4, 1, 4, 1, 5, 1, 4, 1, 4, 1, 2, 01022 10, 3, 1, 4, 1, 4, 1, 14, 4, 1, 2, 01023 8, 1, 1, 5, 1, 2, 3, 4, 1, 01024 4, 3, 13, 1, 10, 01025 3, 1, 9, 4, 01026 4, 6, 7, 2, 2, 01027 4, 8, 4, 1, 4, 01028 6, 2, 8, 3, 2, 5, 3, 01029 5, 10, 1, 3, 7, 2, 01030 6, 8, 6, 2, 8, 1, 2, 01031 7, 1, 1, 2, 2, 8, 1, 1, 01032 11, 2, 1, 1, 1, 2, 1, 3, 1, 3, 3, 1, 01033 8, 2, 1, 1, 1, 5, 4, 2, 1, 01034 8, 2, 1, 1, 1, 1, 7, 2, 1, 01035 8, 2, 1, 1, 2, 9, 1, 2, 1, 01036 5, 4, 6, 12, 1, 3, 01037 4, 16, 13, 3, 2, 01038 3, 12, 21, 2, 01039 3, 2, 13, 23, 01040 3, 2, 14, 19, 01041 4, 2, 14, 20, 2, 01042 6, 2, 13, 7, 2, 8, 2, 01043 5, 12, 8, 1, 7, 2, 01044 9, 5, 1, 1, 1, 2, 8, 1, 5, 2, 01045 8, 2, 1, 1, 1, 9, 1, 1, 4, 01046 8, 2, 1, 1, 1, 6, 1, 3, 5, 01047 6, 2, 2, 1, 5, 6, 2, 01048 8, 2, 1, 3, 1, 3, 7, 3, 2, 01049 9, 2, 3, 2, 1, 1, 2, 4, 4, 2, 01050 9, 2, 2, 1, 1, 2, 3, 1, 8, 2, 01051 5, 9, 3, 1, 7, 2, 01052 5, 12, 4, 1, 6, 2, 01053 5, 7, 4, 1, 2, 5, 01054 5, 2, 6, 6, 5, 6, 01055 4, 8, 8, 6, 3, 01056 5, 3, 10, 8, 4, 2, 01057 5, 5, 11, 9, 5, 2, 01058 5, 3, 1, 12, 16, 2, 01059 4, 3, 1, 12, 16, 01060 4, 5, 2, 13, 21, 01061 6, 6, 1, 3, 3, 1, 1, 01062 14, 5, 1, 3, 1, 3, 1, 1, 2, 1, 4, 1, 3, 1, 3, 01063 13, 5, 1, 3, 1, 3, 1, 4, 1, 4, 1, 3, 1, 3, 01064 6, 1, 1, 1, 1, 1, 1, 01065 // Row constraints 01066 6, 7, 1, 1, 1, 1, 1, 01067 13, 3, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2, 01068 14, 1, 1, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2, 01069 9, 2, 1, 2, 1, 1, 1, 1, 6, 2, 01070 4, 3, 30, 1, 5, 01071 9, 1, 5, 8, 1, 1, 7, 1, 1, 3, 01072 7, 3, 4, 8, 1, 5, 1, 2, 01073 4, 3, 20, 6, 6, 01074 6, 3, 3, 7, 2, 5, 1, 01075 9, 3, 3, 1, 1, 9, 1, 1, 5, 6, 01076 7, 2, 3, 8, 1, 3, 4, 2, 01077 7, 5, 3, 1, 10, 4, 5, 2, 01078 6, 1, 2, 3, 8, 4, 6, 01079 5, 2, 2, 3, 11, 10, 01080 5, 2, 2, 3, 10, 7, 01081 6, 2, 3, 1, 7, 12, 2, 01082 6, 2, 3, 1, 4, 11, 2, 01083 6, 4, 1, 2, 1, 11, 2, 01084 4, 9, 1, 2, 9, 01085 5, 6, 2, 1, 4, 11, 01086 6, 2, 5, 1, 2, 6, 6, 01087 5, 6, 2, 4, 8, 4, 01088 4, 4, 2, 16, 1, 01089 4, 2, 2, 15, 2, 01090 4, 3, 2, 15, 4, 01091 4, 3, 3, 13, 4, 01092 3, 4, 12, 9, 01093 3, 1, 9, 10, 01094 5, 2, 1, 17, 7, 2, 01095 6, 2, 2, 8, 3, 8, 2, 01096 6, 2, 3, 6, 3, 8, 2, 01097 6, 2, 4, 5, 4, 7, 2, 01098 5, 2, 5, 5, 4, 6, 01099 5, 4, 4, 5, 4, 9, 01100 5, 1, 4, 6, 4, 4, 01101 6, 4, 3, 6, 4, 3, 2, 01102 7, 2, 1, 2, 7, 4, 4, 2, 01103 7, 2, 2, 2, 9, 5, 5, 2, 01104 6, 2, 2, 2, 10, 6, 6, 01105 5, 3, 2, 1, 9, 18, 01106 3, 8, 4, 23, 01107 9, 1, 2, 1, 2, 2, 1, 1, 1, 2, 01108 12, 2, 1, 4, 2, 1, 4, 1, 5, 1, 3, 1, 2, 01109 11, 2, 1, 5, 4, 4, 1, 5, 1, 3, 1, 2, 01110 5, 1, 10, 1, 1, 1, 01111 }; 01112 01113 01115 const int webpbn65[]= 01116 { 34, 40, 01117 // Column constraints 01118 1, 5, 01119 3, 3, 2, 1, 01120 4, 3, 2, 2, 1, 01121 5, 3, 2, 2, 2, 2, 01122 6, 3, 2, 2, 2, 2, 3, 01123 7, 1, 2, 2, 2, 2, 2, 16, 01124 9, 1, 2, 2, 2, 2, 2, 2, 1, 2, 01125 9, 1, 2, 2, 2, 2, 2, 2, 13, 1, 01126 10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1, 01127 9, 6, 5, 2, 2, 2, 2, 6, 1, 1, 01128 11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1, 01129 12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 01130 11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1, 01131 6, 1, 7, 2, 16, 1, 1, 01132 11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 01133 11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1, 01134 9, 2, 7, 1, 1, 11, 1, 1, 1, 1, 01135 9, 2, 7, 1, 1, 11, 1, 1, 1, 1, 01136 11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1, 01137 11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 01138 6, 1, 7, 2, 16, 1, 1, 01139 11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1, 01140 12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 01141 11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1, 01142 9, 6, 5, 2, 2, 2, 2, 6, 1, 1, 01143 10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1, 01144 9, 1, 2, 2, 2, 2, 2, 2, 13, 1, 01145 9, 1, 2, 2, 2, 2, 2, 2, 1, 2, 01146 7, 1, 2, 2, 2, 2, 2, 16, 01147 6, 3, 2, 2, 2, 2, 3, 01148 5, 3, 2, 2, 2, 2, 01149 4, 3, 2, 2, 1, 01150 3, 3, 2, 1, 01151 1, 5, 01152 // Row constraints 01153 1, 12, 01154 3, 5, 2, 5, 01155 4, 5, 2, 2, 5, 01156 7, 1, 2, 2, 2, 2, 2, 1, 01157 7, 4, 2, 2, 4, 2, 2, 4, 01158 7, 4, 2, 2, 4, 2, 2, 4, 01159 7, 1, 2, 2, 2, 2, 2, 1, 01160 7, 6, 2, 2, 2, 2, 2, 6, 01161 7, 6, 2, 2, 2, 2, 2, 6, 01162 3, 1, 14, 1, 01163 2, 10, 10, 01164 4, 8, 3, 3, 8, 01165 8, 1, 1, 2, 1, 1, 2, 1, 1, 01166 6, 9, 2, 2, 2, 2, 9, 01167 2, 9, 9, 01168 6, 1, 1, 1, 1, 1, 1, 01169 3, 12, 2, 12, 01170 2, 12, 12, 01171 5, 1, 1, 4, 1, 1, 01172 2, 14, 14, 01173 2, 12, 12, 01174 5, 2, 1, 4, 1, 2, 01175 3, 9, 4, 9, 01176 5, 1, 7, 4, 7, 1, 01177 7, 1, 1, 1, 4, 1, 1, 1, 01178 5, 1, 7, 4, 7, 1, 01179 5, 1, 7, 4, 7, 1, 01180 7, 1, 2, 1, 2, 1, 2, 1, 01181 5, 1, 7, 2, 7, 1, 01182 7, 1, 1, 6, 2, 6, 1, 1, 01183 9, 1, 1, 1, 1, 2, 1, 1, 1, 1, 01184 7, 1, 1, 6, 2, 6, 1, 1, 01185 6, 1, 1, 5, 5, 1, 1, 01186 7, 1, 1, 1, 8, 1, 1, 1, 01187 6, 1, 1, 4, 4, 1, 1, 01188 5, 1, 2, 6, 2, 1, 01189 4, 2, 4, 4, 2, 01190 3, 2, 6, 2, 01191 2, 4, 4, 01192 1, 6, 01193 }; 01194 01195 01196 const int *specs[] = {heart, bear, crocodile, unknown, 01197 pinwheel, difficult, non_unique, dragonfly, 01198 castle, p200, 01199 // From the webpbn survey 01200 webpbn1, // 10 01201 webpbn6, // 11 01202 webpbn21, // 12 01203 webpbn27, // 13 01204 webpbn23, // 14 01205 webpbn16, // 15 01206 webpbn529, // 16 01207 webpbn65, // 17 01208 webpbn436, // 18 01209 }; 01210 const unsigned n_examples = sizeof(specs)/sizeof(int*); 01212 01213 } 01214 01215 // STATISTICS: example-any