Generated on Mon May 10 06:46:29 2010 for Gecode by doxygen 1.6.3

black-hole.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, 2006
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00011  *     $Revision: 10684 $
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 
00041 #include <vector>
00042 #include <algorithm>
00043 #include <sstream>
00044 
00045 using namespace Gecode;
00046 
00047 namespace {
00048   using std::vector;
00049 
00051   vector<vector<int> > layout;
00053   vector<int> layer, pile;
00054 
00061   void generate(int seed) {
00062     // The layout consists of 17 piles of 3 cards each
00063     layout = vector<vector<int> >(17, vector<int>(3));
00064     // Deck without the Ace of Spades
00065     vector<int> deck(51);
00066     for (int i = 51; i--; ) deck[i] = i+1;
00067     Support::RandomGenerator rnd(seed+1);
00068     std::random_shuffle(deck.begin(), deck.end(), rnd);
00069 
00070     // Place cards from deck
00071     int pos = 0;
00072     for (int i = 17; i--; )
00073       for (int j = 3; j--; )
00074         layout[i][j] = deck[pos++];
00075 
00076     // Location-information for each card
00077     layer = vector<int>(52);
00078     pile  = vector<int>(52);
00079     for (int i = 17; i--; ) {
00080       for (int j = 3; j--; ) {
00081         layer[layout[i][j]] = j;
00082         pile[ layout[i][j]] = i;
00083       }
00084     }
00085   }
00086 }
00087 
00088 
00089 
00098 class BlackHoleBranch : Brancher {
00099 protected:
00101   ViewArray<Int::IntView> x;
00103   mutable int start;
00105   class Choice : public Gecode::Choice {
00106   public:
00108     int pos;
00110     int val;
00114     Choice(const Brancher& b, int pos0, int val0)
00115       : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00117     virtual size_t size(void) const {
00118       return sizeof(Choice);
00119     }
00120   };
00121 
00123   BlackHoleBranch(Home home, ViewArray<Int::IntView>& xv)
00124     : Brancher(home), x(xv), start(0) {}
00126   BlackHoleBranch(Space& home, bool share, BlackHoleBranch& b)
00127     : Brancher(home, share, b), start(b.start) {
00128     x.update(home, share, b.x);
00129   }
00130 
00131 public:
00133   virtual bool status(const Space&) const {
00134     for (int i = start; i < x.size(); ++i)
00135       if (!x[i].assigned()) {
00136         start = i;
00137         return true;
00138       }
00139     // No non-assigned orders left
00140     return false;
00141   }
00143   virtual Choice* choice(Space&) {
00144     int val = -1;
00145     int w = 4;
00146     for (Int::ViewValues<Int::IntView> vals(x[start]); vals(); ++vals)
00147       if (layer[vals.val()] < w) {
00148         val = vals.val();
00149         if ((w = layer[vals.val()]) == 0) break;
00150       }
00151 
00152     assert(val >= 1 && val < 52);
00153     return new Choice(*this, start, val);
00154   }
00156   virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00157                             unsigned int a) {
00158     const Choice& c = static_cast<const Choice&>(_c);
00159     if (a)
00160       return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
00161     else
00162       return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
00163   }
00165   virtual Actor* copy(Space& home, bool share) {
00166     return new (home) BlackHoleBranch(home, share, *this);
00167   }
00169   static void post(Home home, IntVarArgs x) {
00170     ViewArray<Int::IntView> xv(home, x);
00171     (void) new (home) BlackHoleBranch(home, xv);
00172   }
00174   virtual size_t dispose(Space&) {
00175     return sizeof(*this);
00176   }
00177 };
00178 
00179 
00196 class BlackHole : public Script {
00197 protected:
00198   IntVarArray x, 
00199     y; 
00200 
00202   std::string
00203   card(int val) const {
00204     const char* suit = "SCHD";
00205     std::ostringstream o;
00206     o << std::setw(2) << (1 + (val%13)) << suit[val/13];
00207     return o.str();
00208   }
00209 
00210 public:
00212   enum {
00213     SYMMETRY_NONE,    
00214     SYMMETRY_CONDITIONAL 
00215   };
00217   enum {
00218     PROPAGATION_REIFIED,  
00219     PROPAGATION_DFA,      
00220     PROPAGATION_TUPLE_SET 
00221   };
00223   BlackHole(const SizeOptions& opt)
00224     : x(*this, 52, 0,51), y(*this, 52, 0,51)
00225   {
00226     // Black ace at bottom
00227     rel(*this, x[0], IRT_EQ, 0);
00228 
00229     // x is order and y is placement
00230     channel(*this, x, y, opt.icl());
00231 
00232     // The placement rules: the absolute value of the difference
00233     // between two consecutive cards is 1 or 12.
00234     if (opt.propagation() == PROPAGATION_REIFIED) {
00235       // Build table for accessing the rank of a card
00236       IntArgs modtable(52);
00237       for (int i = 0; i < 52; ++i) {
00238         modtable[i] = i%13;
00239       }
00240       for (int i = 0; i < 51; ++i) {
00241         IntVar x1(*this, 0, 12), x2(*this, 0, 12);
00242         element(*this, modtable, x[i], x1);
00243         element(*this, modtable, x[i+1], x2);
00244         const int dr[2] = {1, 12};
00245         IntVar diff(*this, IntSet(dr, 2));
00246         post(*this, abs(*this, minus(*this, x1, x2, ICL_DOM), ICL_DOM)
00247              == diff, ICL_DOM);
00248       }
00249     } else if (opt.propagation() == PROPAGATION_DFA) {
00250       // Build table for allowed tuples
00251       REG expression;
00252       for (int r = 13; r--; ) {
00253         for (int s1 = 4; s1--; ) {
00254           for (int s2 = 4; s2--; ) {
00255             for (int i = -1; i <= 1; i+=2) {
00256               REG r1 = REG(r+13*s1);
00257               REG r2 = REG((r+i+52+13*s2)%52);
00258               REG r = r1 + r2;
00259               expression |= r;
00260             }
00261           }
00262         }
00263       }
00264       DFA table(expression);
00265 
00266       for (int i = 51; i--; ) {
00267         IntVarArgs iva(2);
00268         iva[0] = x[i]; iva[1] = x[i+1];
00269         extensional(*this, iva, table);
00270       }
00271 
00272     } else { // opt.propagation() == PROPAGATION_TUPLE_SET)
00273       // Build table for allowed tuples
00274       TupleSet tupleSet;
00275       for (int r = 13; r--; )
00276         for (int s1 = 4; s1--; )
00277           for (int s2 = 4; s2--; )
00278             for (int i = -1; i <= 1; i+=2) {
00279               IntArgs t(2);
00280               t[0] = r+13*s1;
00281               t[1] = (r+i+52+13*s2)%52;
00282               tupleSet.add(t);
00283             }
00284       tupleSet.finalize();
00285       for (int i = 51; i--; ) {
00286         IntVarArgs iva(2);
00287         iva[0] = x[i]; iva[1] = x[i+1];
00288         extensional(*this, iva, tupleSet, EPK_DEF, ICL_DOM);
00289       }
00290     }
00291     // A card must be played before the one under it.
00292     for (int i = 17; i--; )
00293       for (int j = 2; j--; )
00294         post(*this, y[layout[i][j]] < y[layout[i][j+1]]);
00295 
00296     // Compute and break the conditional symmetries that are dependent
00297     // on the current layout.
00298     if (opt.symmetry() == SYMMETRY_CONDITIONAL) {
00299       // For all ranks
00300       for (int r = 13; r--; ) {
00301         // For all pairs of suits
00302         for (int s1 = 4; s1--; ) {
00303           for (int s2 = s1; s2--; ) {
00304             int c1 = 13*s1 + r,
00305               c2 = 13*s2 + r;
00306             // The ace of spades is already placed
00307             if (c1 == 0 || c2 == 0) continue;
00308             // Piles are handled by the rules of the game
00309             if (pile[c1] == pile[c2]) continue;
00310             // Get the right order of the cards
00311             int o1 = c1, o2 = c2;
00312             if (pile[c1] > pile[c2] && layer[c2] >= layer[c1])
00313               std::swap(o1, o2);
00314             // cond is the condition for the symmetry
00315             BoolVarArgs ba(4);
00316             int pos = 0;
00317             // Both cards played after the ones on top of them
00318             for (int i = 0; i < layer[o1]; ++i)
00319               ba[pos++] = post(*this, ~(y[layout[pile[o1]][i]] < y[o2]));
00320             for (int i = 0; i < layer[o2]; ++i)
00321               ba[pos++] = post(*this, ~(y[layout[pile[o2]][i]] < y[o1]));
00322             // Both cards played before the ones under them
00323             for (int i = layer[o1]+1; i < 3; ++i)
00324               ba[pos++] = post(*this, ~(y[o2] < y[layout[pile[o1]][i]]));
00325             for (int i = layer[o2]+1; i < 3; ++i)
00326               ba[pos++] = post(*this, ~(y[o1] < y[layout[pile[o2]][i]]));
00327             // Cond holds when all the above holds
00328             BoolVar cond(*this, 0, 1);
00329             rel(*this, BOT_AND, ba, cond);
00330 
00331             // If cond is fulfilled, then we can order the cards
00332             // cond -> (y[o1] < y[o2])
00333             post(*this, tt(!cond || ~(y[o1] < y[o2])));
00334           }
00335         }
00336       }
00337     }
00338 
00339     // Install custom brancher
00340     BlackHoleBranch::post(*this, x);
00341   }
00342 
00344   virtual void
00345   print(std::ostream& os) const {
00346     os << "Layout:" << std::endl;
00347     for (int i = 0; i < 17; i++) {
00348       for (int j = 0; j < 3; j++)
00349         os << card(layout[i][j]) << " ";
00350       if ((i+1) % 3 == 0)
00351         os << std::endl;
00352       else
00353         os << "  \t";
00354     }
00355     os << std::endl << std::endl;
00356 
00357     os << "Solution:" << std::endl;
00358     for (int i = 0; i < 52; ++i) {
00359       if (x[i].assigned())
00360         os << card(x[i].val()) << " ";
00361       else
00362         os << "   ";
00363       if ((i + 1) % 13 == 0)
00364         os << std::endl;
00365     }
00366     os << std::endl;
00367     os << std::endl;
00368   }
00369 
00371   BlackHole(bool share, BlackHole& s) : Script(share,s) {
00372     x.update(*this, share, s.x);
00373     y.update(*this, share, s.y);
00374   }
00376   virtual Space*
00377   copy(bool share) {
00378     return new BlackHole(share,*this);
00379   }
00380 };
00381 
00385 int
00386 main(int argc, char* argv[]) {
00387   SizeOptions opt("Black Hole patience");
00388   opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL);
00389   opt.symmetry(BlackHole::SYMMETRY_NONE,"none",
00390                "no symmetry breaking");
00391   opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL,"conditional",
00392                "break conditional symmetries");
00393   opt.propagation(BlackHole::PROPAGATION_DFA);
00394   opt.propagation(BlackHole::PROPAGATION_REIFIED,
00395                   "reified", "use reified propagation");
00396   opt.propagation(BlackHole::PROPAGATION_DFA,
00397                   "dfa", "use DFA-based extensional propagation");
00398   opt.propagation(BlackHole::PROPAGATION_TUPLE_SET,
00399                   "tuple-set", "use TupleSet-based extensional propagation");
00400   opt.icl(ICL_DOM);
00401   opt.parse(argc,argv);
00402   // Generates the new board
00403   generate(opt.size());
00404   Script::run<BlackHole,DFS,SizeOptions>(opt);
00405   return 0;
00406 }
00407 
00408 // STATISTICS: example-any