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