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-05-09 23:44:58 +0200 (Sun, 09 May 2010) $ by $Author: tack $ 00011 * $Revision: 10911 $ 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 rel(*this, abs(x1-x2) == diff, ICL_DOM); 00247 } 00248 } else if (opt.propagation() == PROPAGATION_DFA) { 00249 // Build table for allowed tuples 00250 REG expression; 00251 for (int r = 13; r--; ) { 00252 for (int s1 = 4; s1--; ) { 00253 for (int s2 = 4; s2--; ) { 00254 for (int i = -1; i <= 1; i+=2) { 00255 REG r1 = REG(r+13*s1); 00256 REG r2 = REG((r+i+52+13*s2)%52); 00257 REG r = r1 + r2; 00258 expression |= r; 00259 } 00260 } 00261 } 00262 } 00263 DFA table(expression); 00264 00265 for (int i = 51; i--; ) 00266 extensional(*this, IntVarArgs() << x[i] << x[i+1], table); 00267 00268 } else { // opt.propagation() == PROPAGATION_TUPLE_SET) 00269 // Build table for allowed tuples 00270 TupleSet tupleSet; 00271 for (int r = 13; r--; ) 00272 for (int s1 = 4; s1--; ) 00273 for (int s2 = 4; s2--; ) 00274 for (int i = -1; i <= 1; i+=2) { 00275 tupleSet.add(IntArgs(2, r+13*s1, (r+i+52+13*s2)%52)); 00276 } 00277 tupleSet.finalize(); 00278 00279 for (int i = 51; i--; ) 00280 extensional(*this, IntVarArgs() << x[i] << x[i+1], tupleSet); 00281 } 00282 00283 // A card must be played before the one under it. 00284 for (int i = 17; i--; ) 00285 for (int j = 2; j--; ) 00286 rel(*this, y[layout[i][j]] < y[layout[i][j+1]]); 00287 00288 // Compute and break the conditional symmetries that are dependent 00289 // on the current layout. 00290 // Two cards with the same rank but different suits are symmetric 00291 // with respect to their placement in the black hole if changing 00292 // their order does not affect any other card. 00293 if (opt.symmetry() == SYMMETRY_CONDITIONAL) { 00294 // For all ranks 00295 for (int r = 13; r--; ) { 00296 // For all pairs of suits 00297 for (int s1 = 4; s1--; ) { 00298 for (int s2 = s1; s2--; ) { 00299 int c1 = 13*s1 + r, 00300 c2 = 13*s2 + r; 00301 // The ace of spades is already placed 00302 if (c1 == 0 || c2 == 0) continue; 00303 // Piles are handled by the rules of the game 00304 if (pile[c1] == pile[c2]) continue; 00305 // Fix the right order of the cards 00306 int o1 = c1, o2 = c2; 00307 if (pile[c1] > pile[c2] && layer[c2] >= layer[c1]) 00308 std::swap(o1, o2); 00309 // cond is the condition for the symmetry 00310 BoolVarArgs ba; 00311 // Both cards played after the ones on top of them 00312 for (int i = 0; i < layer[o1]; ++i) 00313 ba << expr(*this, (y[layout[pile[o1]][i]] < y[o2])); 00314 for (int i = 0; i < layer[o2]; ++i) 00315 ba << expr(*this, (y[layout[pile[o2]][i]] < y[o1])); 00316 // Both cards played before the ones under them 00317 for (int i = layer[o1]+1; i < 3; ++i) 00318 ba << expr(*this, (y[o2] < y[layout[pile[o1]][i]])); 00319 for (int i = layer[o2]+1; i < 3; ++i) 00320 ba << expr(*this, (y[o1] < y[layout[pile[o2]][i]])); 00321 // Cond holds when all the above holds 00322 BoolVar cond(*this, 0, 1); 00323 rel(*this, BOT_AND, ba, cond); 00324 00325 // If cond is fulfilled, then we can order the cards 00326 // cond -> (y[o1] < y[o2]) 00327 rel(*this, !cond || (y[o1] < y[o2])); 00328 } 00329 } 00330 } 00331 } 00332 00333 // Install custom brancher 00334 BlackHoleBranch::post(*this, x); 00335 } 00336 00338 virtual void 00339 print(std::ostream& os) const { 00340 os << "Layout:" << std::endl; 00341 for (int i = 0; i < 17; i++) { 00342 for (int j = 0; j < 3; j++) 00343 os << card(layout[i][j]) << " "; 00344 if ((i+1) % 3 == 0) 00345 os << std::endl; 00346 else 00347 os << " \t"; 00348 } 00349 os << std::endl << std::endl; 00350 00351 os << "Solution:" << std::endl; 00352 for (int i = 0; i < 52; ++i) { 00353 if (x[i].assigned()) 00354 os << card(x[i].val()) << " "; 00355 else 00356 os << " "; 00357 if ((i + 1) % 13 == 0) 00358 os << std::endl; 00359 } 00360 os << std::endl; 00361 os << std::endl; 00362 } 00363 00365 BlackHole(bool share, BlackHole& s) : Script(share,s) { 00366 x.update(*this, share, s.x); 00367 y.update(*this, share, s.y); 00368 } 00370 virtual Space* 00371 copy(bool share) { 00372 return new BlackHole(share,*this); 00373 } 00374 }; 00375 00379 int 00380 main(int argc, char* argv[]) { 00381 SizeOptions opt("Black Hole patience"); 00382 opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL); 00383 opt.symmetry(BlackHole::SYMMETRY_NONE,"none", 00384 "no symmetry breaking"); 00385 opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL,"conditional", 00386 "break conditional symmetries"); 00387 opt.propagation(BlackHole::PROPAGATION_DFA); 00388 opt.propagation(BlackHole::PROPAGATION_REIFIED, 00389 "reified", "use reified propagation"); 00390 opt.propagation(BlackHole::PROPAGATION_DFA, 00391 "dfa", "use DFA-based extensional propagation"); 00392 opt.propagation(BlackHole::PROPAGATION_TUPLE_SET, 00393 "tuple-set", "use TupleSet-based extensional propagation"); 00394 opt.icl(ICL_DOM); 00395 opt.parse(argc,argv); 00396 // Generates the new board 00397 generate(opt.size()); 00398 Script::run<BlackHole,DFS,SizeOptions>(opt); 00399 return 0; 00400 } 00401 00402 // STATISTICS: example-any