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
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
00063 layout = vector<vector<int> >(17, vector<int>(3));
00064
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
00071 int pos = 0;
00072 for (int i = 17; i--; )
00073 for (int j = 3; j--; )
00074 layout[i][j] = deck[pos++];
00075
00076
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
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
00227 rel(*this, x[0], IRT_EQ, 0);
00228
00229
00230 channel(*this, x, y, opt.icl());
00231
00232
00233
00234 if (opt.propagation() == PROPAGATION_REIFIED) {
00235
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
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 {
00273
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
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
00297
00298 if (opt.symmetry() == SYMMETRY_CONDITIONAL) {
00299
00300 for (int r = 13; r--; ) {
00301
00302 for (int s1 = 4; s1--; ) {
00303 for (int s2 = s1; s2--; ) {
00304 int c1 = 13*s1 + r,
00305 c2 = 13*s2 + r;
00306
00307 if (c1 == 0 || c2 == 0) continue;
00308
00309 if (pile[c1] == pile[c2]) continue;
00310
00311 int o1 = c1, o2 = c2;
00312 if (pile[c1] > pile[c2] && layer[c2] >= layer[c1])
00313 std::swap(o1, o2);
00314
00315 BoolVarArgs ba(4);
00316 int pos = 0;
00317
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
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
00328 BoolVar cond(*this, 0, 1);
00329 rel(*this, BOT_AND, ba, cond);
00330
00331
00332
00333 post(*this, tt(!cond || ~(y[o1] < y[o2])));
00334 }
00335 }
00336 }
00337 }
00338
00339
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
00403 generate(opt.size());
00404 Script::run<BlackHole,DFS,SizeOptions>(opt);
00405 return 0;
00406 }
00407
00408