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
00039
00040
00041
00042 #include <gecode/driver.hh>
00043 #include <gecode/int.hh>
00044 #include <gecode/minimodel.hh>
00045
00046 using namespace Gecode;
00047
00056 struct TileSpec {
00057 int width, height;
00058 int amount;
00059 const char *tile;
00060 };
00061
00070 extern const TileSpec *examples[];
00075 extern const int examples_size[];
00080 extern const unsigned int n_examples;
00081
00082 namespace {
00095 int pos(int h, int w, int h1, int w1);
00097 typedef void (*tsymmfunc)(const char*, int, int, char*, int&, int&);
00099 typedef void (*bsymmfunc)(const IntVarArgs, int, int, IntVarArgs&, int&, int&);
00101 template<class CArray, class Array>
00102 void id(CArray t1, int w1, int h1, Array t2, int& w2, int&h2);
00104 template<class CArray, class Array>
00105 void rot90(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
00107 template<class CArray, class Array>
00108 void rot180(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
00110 template<class CArray, class Array>
00111 void rot270(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
00113 template<class CArray, class Array>
00114 void flipx(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
00116 template<class CArray, class Array>
00117 void flipy(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
00119 template<class CArray, class Array>
00120 void flipd1(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
00122 template<class CArray, class Array>
00123 void flipd2(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
00125 }
00126
00263 class Pentominoes : public Script {
00264 public:
00266 enum {
00267 PROPAGATION_INT,
00268 PROPAGATION_BOOLEAN,
00269 };
00271 enum {
00272 SYMMETRY_NONE,
00273 SYMMETRY_FULL,
00274 };
00275 private:
00277 const TileSpec *spec;
00279 int width, height;
00281 bool filled;
00283 int nspecs;
00285 int ntiles;
00286
00288 IntVarArray board;
00289
00291 int compute_number_of_tiles(const TileSpec* ts, int nspecs) {
00292 int res = 0;
00293 for (int i = nspecs; i--; ) {
00294 res += ts[i].amount;
00295 }
00296 return res;
00297 }
00298
00301 REG tile_reg(int twidth, int theight, const char* tile,
00302 REG mark, REG other, REG eol) {
00303 REG oe = other | eol;
00304 REG res = *oe;
00305 REG color[] = {other, mark};
00306 for (int h = 0; h < theight; ++h) {
00307 for (int w = 0; w < twidth; ++w) {
00308 int which = tile[h*twidth + w] == 'X';
00309 res += color[which];
00310 }
00311 if (h < theight-1) {
00312 res += oe(width-twidth, width-twidth);
00313 }
00314 }
00315 res += *oe + oe;
00316 return res;
00317 }
00318
00321 REG get_constraint(int t, REG mark, REG other, REG eol) {
00322
00323 REG res;
00324 char *t2 = new char[width*height];
00325 int w2, h2;
00326 tsymmfunc syms[] = {id, flipx, flipy, flipd1, flipd2, rot90, rot180, rot270};
00327 int symscnt = sizeof(syms)/sizeof(tsymmfunc);
00328 for (int i = 0; i < symscnt; ++i) {
00329 syms[i](spec[t].tile, spec[t].width, spec[t].height, t2, w2, h2);
00330 res = res | tile_reg(w2, h2, t2, mark, other, eol);
00331 }
00332 delete [] t2;
00333
00334 return res;
00335 }
00336
00337
00338 public:
00340 Pentominoes(const SizeOptions& opt)
00341 : spec(examples[opt.size()]),
00342 width(spec[0].width+1),
00343 height(spec[0].height),
00344 filled(spec[0].amount),
00345 nspecs(examples_size[opt.size()]-1),
00346 ntiles(compute_number_of_tiles(spec+1, nspecs)),
00347 board(*this, width*height, filled,ntiles+1) {
00348 spec += 1;
00349
00350
00351 for (int h = 0; h < height; ++h) {
00352 for (int w = 0; w < width-1; ++w)
00353 rel(*this, board[h*width + w], IRT_NQ, ntiles+1);
00354 rel(*this, board[h*width + width - 1], IRT_EQ, ntiles+1);
00355 }
00356
00357
00358 if (opt.propagation() == PROPAGATION_INT) {
00359 int tile = 0;
00360 for (int i = 0; i < nspecs; ++i) {
00361 for (int j = 0; j < spec[i].amount; ++j) {
00362
00363 int col = tile+1;
00364
00365 REG mark(col);
00366
00367 REG other;
00368 bool first = true;
00369 for (int j = filled; j <= ntiles; ++j) {
00370 if (j == col) continue;
00371 if (first) {
00372 other = REG(j);
00373 first = false;
00374 } else {
00375 other |= REG(j);
00376 }
00377 }
00378
00379 REG eol(ntiles+1);
00380 extensional(*this, board, get_constraint(i, mark, other, eol));
00381 ++tile;
00382 }
00383 }
00384 } else {
00385 int ncolors = ntiles + 2;
00386
00387 BoolVarArgs p(ncolors * board.size());
00388 for (int i=p.size(); i--; )
00389 p[i].init(*this,0,1);
00390
00391
00392 for (int i=board.size(); i--; ) {
00393 BoolVarArgs c(ncolors);
00394 for (int j=ncolors; j--; )
00395 c[j]=p[i*ncolors+j];
00396 channel(*this, c, board[i]);
00397 }
00398
00399
00400
00401
00402 REG other(0), mark(1);
00403 int tile = 0;
00404 for (int i = 0; i < nspecs; ++i) {
00405 for (int j = 0; j < spec[i].amount; ++j) {
00406 int col = tile+1;
00407
00408 BoolVarArgs c(board.size());
00409
00410 for (int k = board.size(); k--; ) {
00411 c[k] = p[k*ncolors+col];
00412 }
00413
00414 extensional(*this, c, get_constraint(i, mark, other, other));
00415 ++tile;
00416 }
00417 }
00418 }
00419
00420 if (opt.symmetry() == SYMMETRY_FULL) {
00421
00422 IntVarArgs orig(board.size()-height), symm(board.size()-height);
00423 int pos = 0;
00424 for (int i = 0; i < board.size(); ++i) {
00425 if ((i+1)%width==0) continue;
00426 orig[pos++] = board[i];
00427 }
00428
00429 int w2, h2;
00430 bsymmfunc syms[] = {flipx, flipy, flipd1, flipd2, rot90, rot180, rot270};
00431 int symscnt = sizeof(syms)/sizeof(bsymmfunc);
00432 for (int i = 0; i < symscnt; ++i) {
00433 syms[i](orig, width-1, height, symm, w2, h2);
00434 if (width-1 == w2 && height == h2)
00435 rel(*this, orig, IRT_LQ, symm);
00436 }
00437 }
00438
00439
00440 branch(*this, board, INT_VAR_NONE, INT_VAL_MIN);
00441 }
00442
00444 Pentominoes(bool share, Pentominoes& s) :
00445 Script(share,s), spec(s.spec), width(s.width), height(s.height),
00446 filled(s.filled), nspecs(s.nspecs) {
00447 board.update(*this, share, s.board);
00448 }
00449
00451 virtual Space*
00452 copy(bool share) {
00453 return new Pentominoes(share,*this);
00454 }
00455
00457 virtual void
00458 print(std::ostream& os) const {
00459 for (int h = 0; h < height; ++h) {
00460 os << "\t";
00461 for (int w = 0; w < width-1; ++w) {
00462 int val = board[h*width + w].val();
00463 char c = val < 10 ? '0'+val : 'A' + (val-10);
00464 os << c;
00465 }
00466 os << std::endl;
00467 }
00468 os << std::endl;
00469 }
00470 };
00471
00472
00476 int
00477 main(int argc, char* argv[]) {
00478 SizeOptions opt("Pentominoes");
00479 opt.size(1);
00480 opt.symmetry(Pentominoes::SYMMETRY_FULL);
00481 opt.symmetry(Pentominoes::SYMMETRY_NONE,
00482 "none", "do not remove symmetric solutions");
00483 opt.symmetry(Pentominoes::SYMMETRY_FULL,
00484 "full", "remove symmetric solutions");
00485
00486 opt.propagation(Pentominoes::PROPAGATION_BOOLEAN);
00487 opt.propagation(Pentominoes::PROPAGATION_INT,
00488 "int", "use integer propagators");
00489 opt.propagation(Pentominoes::PROPAGATION_BOOLEAN,
00490 "bool", "use Boolean propagators");
00491
00492 opt.parse(argc,argv);
00493 if (opt.size() >= n_examples) {
00494 std::cerr << "Error: size must be between 0 and "
00495 << n_examples-1 << std::endl;
00496 return 1;
00497 }
00498 Script::run<Pentominoes,DFS,SizeOptions>(opt);
00499 return 0;
00500 }
00501
00502
00508
00509 static const TileSpec puzzle0[] =
00510 {
00511
00512 {4, 4, true, ""},
00513 {2, 3, 1,
00514 "XX"
00515 "X "
00516 "X "},
00517 {2, 1, 1,
00518 "XX"},
00519 {3, 3, 1,
00520 " XX"
00521 " X"
00522 "XXX"},
00523 {1, 1, 1,
00524 "X"},
00525 {3, 1, 1,
00526 "XXX"}
00527 };
00529 static const TileSpec puzzle1[] =
00530 {
00531
00532 {8, 8, true, ""},
00533 {3, 3, 1,
00534 "XXX"
00535 "XXX"
00536 "XX "},
00537 {5, 3, 1,
00538 " XXX"
00539 " X "
00540 "XXX "},
00541 {3, 4, 1,
00542 "XXX"
00543 "XXX"
00544 " X"
00545 " X"},
00546 {3, 4, 1,
00547 "XXX"
00548 " X"
00549 " X"
00550 " X"},
00551 {2, 5, 1,
00552 " X"
00553 " X"
00554 " X"
00555 "XX"
00556 "XX"},
00557 {4, 2, 1,
00558 "XX "
00559 "XXXX"},
00560 {3, 3, 1,
00561 "XXX"
00562 " X"
00563 " X"},
00564 {2, 3, 1,
00565 "XX"
00566 "X "
00567 "X "},
00568 {2, 4, 1,
00569 "XX"
00570 "XX"
00571 "XX"
00572 "XX"},
00573 {3, 2, 1,
00574 "XX "
00575 "XXX"}
00576 };
00577
00578
00579 static const TileSpec square2[] =
00580 {
00581
00582 {10, 10, true, ""},
00583 {6, 6, 1,
00584 "XXXXXX"
00585 "XXXXXX"
00586 "XXXXXX"
00587 "XXXXXX"
00588 "XXXXXX"
00589 "XXXXXX"
00590 },
00591 {4, 4, 3,
00592 "XXXX"
00593 "XXXX"
00594 "XXXX"
00595 "XXXX"},
00596 {2, 2, 4,
00597 "XX"
00598 "XX"}
00599 };
00600
00601
00602 static const TileSpec square3[] =
00603 {
00604
00605 {20, 20, true, ""},
00606 {9, 9, 1,
00607 "XXXXXXXXX"
00608 "XXXXXXXXX"
00609 "XXXXXXXXX"
00610 "XXXXXXXXX"
00611 "XXXXXXXXX"
00612 "XXXXXXXXX"
00613 "XXXXXXXXX"
00614 "XXXXXXXXX"
00615 "XXXXXXXXX"
00616 },
00617 {8, 8, 2,
00618 "XXXXXXXX"
00619 "XXXXXXXX"
00620 "XXXXXXXX"
00621 "XXXXXXXX"
00622 "XXXXXXXX"
00623 "XXXXXXXX"
00624 "XXXXXXXX"
00625 "XXXXXXXX"
00626 },
00627 {7, 7, 1,
00628 "XXXXXXX"
00629 "XXXXXXX"
00630 "XXXXXXX"
00631 "XXXXXXX"
00632 "XXXXXXX"
00633 "XXXXXXX"
00634 "XXXXXXX"
00635 },
00636 {5, 5, 1,
00637 "XXXXX"
00638 "XXXXX"
00639 "XXXXX"
00640 "XXXXX"
00641 "XXXXX"
00642 },
00643 {4, 4, 5,
00644 "XXXX"
00645 "XXXX"
00646 "XXXX"
00647 "XXXX"},
00648 {3, 3, 3,
00649 "XXX"
00650 "XXX"
00651 "XXX"},
00652 {2, 2, 2,
00653 "XX"
00654 "XX"},
00655 {1, 1, 2,
00656 "X"}
00657 };
00658
00659 static const TileSpec pentomino6x10[] =
00660 {
00661
00662 {10, 6, true, ""},
00663 {2, 4, 1,
00664 "X "
00665 "X "
00666 "X "
00667 "XX"},
00668 {3,3, 1,
00669 "XX "
00670 " XX"
00671 " X "},
00672 {3,3, 1,
00673 "XXX"
00674 " X "
00675 " X "},
00676 {3,3, 1,
00677 " X"
00678 " XX"
00679 "XX "},
00680 {2,4, 1,
00681 " X"
00682 "XX"
00683 " X"
00684 " X"},
00685 {5,1, 1,
00686 "XXXXX"},
00687 {3,3, 1,
00688 "X "
00689 "XXX"
00690 " X"},
00691 {4,2, 1,
00692 " XXX"
00693 "XX "},
00694 {2,3, 1,
00695 "XX"
00696 "XX"
00697 " X"},
00698 {3,2, 1,
00699 "X X"
00700 "XXX"},
00701 {3,3, 1,
00702 " X "
00703 "XXX"
00704 " X "},
00705 {3,3, 1,
00706 " X"
00707 " X"
00708 "XXX"}
00709 };
00710
00711 static const TileSpec pentomino5x12[] =
00712 {
00713
00714 {12, 5, true, ""},
00715 {2, 4, 1,
00716 "X "
00717 "X "
00718 "X "
00719 "XX"},
00720 {3,3, 1,
00721 "XX "
00722 " XX"
00723 " X "},
00724 {3,3, 1,
00725 "XXX"
00726 " X "
00727 " X "},
00728 {3,3, 1,
00729 " X"
00730 " XX"
00731 "XX "},
00732 {2,4, 1,
00733 " X"
00734 "XX"
00735 " X"
00736 " X"},
00737 {5,1, 1,
00738 "XXXXX"},
00739 {3,3, 1,
00740 "X "
00741 "XXX"
00742 " X"},
00743 {4,2, 1,
00744 " XXX"
00745 "XX "},
00746 {2,3, 1,
00747 "XX"
00748 "XX"
00749 " X"},
00750 {3,2, 1,
00751 "X X"
00752 "XXX"},
00753 {3,3, 1,
00754 " X "
00755 "XXX"
00756 " X "},
00757 {3,3, 1,
00758 " X"
00759 " X"
00760 "XXX"}
00761 };
00762
00763 static const TileSpec pentomino4x15[] =
00764 {
00765
00766 {15, 4, true, ""},
00767 {2, 4, 1,
00768 "X "
00769 "X "
00770 "X "
00771 "XX"},
00772 {3,3, 1,
00773 "XX "
00774 " XX"
00775 " X "},
00776 {3,3, 1,
00777 "XXX"
00778 " X "
00779 " X "},
00780 {3,3, 1,
00781 " X"
00782 " XX"
00783 "XX "},
00784 {2,4, 1,
00785 " X"
00786 "XX"
00787 " X"
00788 " X"},
00789 {5,1, 1,
00790 "XXXXX"},
00791 {3,3, 1,
00792 "X "
00793 "XXX"
00794 " X"},
00795 {4,2, 1,
00796 " XXX"
00797 "XX "},
00798 {2,3, 1,
00799 "XX"
00800 "XX"
00801 " X"},
00802 {3,2, 1,
00803 "X X"
00804 "XXX"},
00805 {3,3, 1,
00806 " X "
00807 "XXX"
00808 " X "},
00809 {3,3, 1,
00810 " X"
00811 " X"
00812 "XXX"}
00813 };
00814
00815 static const TileSpec pentomino3x20[] =
00816 {
00817
00818 {20, 3, true, ""},
00819 {2, 4, 1,
00820 "X "
00821 "X "
00822 "X "
00823 "XX"},
00824 {3,3, 1,
00825 "XX "
00826 " XX"
00827 " X "},
00828 {3,3, 1,
00829 "XXX"
00830 " X "
00831 " X "},
00832 {3,3, 1,
00833 " X"
00834 " XX"
00835 "XX "},
00836 {2,4, 1,
00837 " X"
00838 "XX"
00839 " X"
00840 " X"},
00841 {5,1, 1,
00842 "XXXXX"},
00843 {3,3, 1,
00844 "X "
00845 "XXX"
00846 " X"},
00847 {4,2, 1,
00848 " XXX"
00849 "XX "},
00850 {2,3, 1,
00851 "XX"
00852 "XX"
00853 " X"},
00854 {3,2, 1,
00855 "X X"
00856 "XXX"},
00857 {3,3, 1,
00858 " X "
00859 "XXX"
00860 " X "},
00861 {3,3, 1,
00862 " X"
00863 " X"
00864 "XXX"}
00865 };
00866
00868 const TileSpec *examples[] = {puzzle0, puzzle1, square2, square3,
00869 pentomino6x10,pentomino5x12,
00870 pentomino4x15,pentomino3x20};
00871 const int examples_size[] = {sizeof(puzzle0)/sizeof(TileSpec),
00872 sizeof(puzzle1)/sizeof(TileSpec),
00873 sizeof(square2)/sizeof(TileSpec),
00874 sizeof(square3)/sizeof(TileSpec),
00875 sizeof(pentomino6x10)/sizeof(TileSpec),
00876 sizeof(pentomino5x12)/sizeof(TileSpec),
00877 sizeof(pentomino4x15)/sizeof(TileSpec),
00878 sizeof(pentomino3x20)/sizeof(TileSpec)};
00879
00881 const unsigned n_examples = sizeof(examples)/sizeof(TileSpec*);
00883
00884
00885 namespace {
00886 int pos(int h, int w, int h1, int w1) {
00887 if (!(0 <= h && h < h1) ||
00888 !(0 <= w && w < w1)) {
00889 std::cerr << "Cannot place (" << h << "," << w
00890 << ") on board of size " << h1 << "x" << w1 << std::endl;
00891 }
00892 return h * w1 + w;
00893 }
00894 template<class CArray, class Array>
00895 void id(CArray t1, int w1, int h1, Array t2, int& w2, int&h2) {
00896 w2 = w1; h2 = h1;
00897 for (int h = 0; h < h1; ++h)
00898 for (int w = 0; w < w1; ++w)
00899 t2[pos(h, w, h2, w2)] = t1[pos(h, w, h1, w1)];
00900 }
00901 template<class CArray, class Array>
00902 void rot90(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
00903 w2 = h1; h2 = w1;
00904 for (int h = 0; h < h1; ++h)
00905 for (int w = 0; w < w1; ++w)
00906 t2[pos(w, w2-h-1, h2, w2)] = t1[pos(h, w, h1, w1)];
00907 }
00908 template<class CArray, class Array>
00909 void rot180(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
00910 w2 = w1; h2 = h1;
00911 for (int h = 0; h < h1; ++h)
00912 for (int w = 0; w < w1; ++w)
00913 t2[pos(h2-h-1, w2-w-1, h2, w2)] = t1[pos(h, w, h1, w1)];
00914 }
00915 template<class CArray, class Array>
00916 void rot270(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
00917 w2 = h1; h2 = w1;
00918 for (int h = 0; h < h1; ++h)
00919 for (int w = 0; w < w1; ++w)
00920 t2[pos(h2-w-1, h, h2, w2)] = t1[pos(h, w, h1, w1)];
00921 }
00922 template<class CArray, class Array>
00923 void flipx(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
00924 w2 = w1; h2 = h1;
00925 for (int h = 0; h < h1; ++h)
00926 for (int w = 0; w < w1; ++w)
00927 t2[pos(h, w2-w-1, h2, w2)] = t1[pos(h, w, h1, w1)];
00928 }
00929 template<class CArray, class Array>
00930 void flipy(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
00931 w2 = w1; h2 = h1;
00932 for (int h = 0; h < h1; ++h)
00933 for (int w = 0; w < w1; ++w)
00934 t2[pos(h2-h-1, w, h2, w2)] = t1[pos(h, w, h1, w1)];
00935 }
00936 template<class CArray, class Array>
00937 void flipd1(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
00938 w2 = h1; h2 = w1;
00939 for (int h = 0; h < h1; ++h)
00940 for (int w = 0; w < w1; ++w)
00941 t2[pos(w, h, h2, w2)] = t1[pos(h, w, h1, w1)];
00942 }
00943 template<class CArray, class Array>
00944 void flipd2(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
00945 w2 = h1; h2 = w1;
00946 for (int h = 0; h < h1; ++h)
00947 for (int w = 0; w < w1; ++w)
00948 t2[pos(h2-w-1, w2-h-1, h2, w2)] = t1[pos(h, w, h1, w1)];
00949 }
00950 }
00951
00952