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 rel(*this, abs(x1-x2) == diff, ICL_DOM);
00247 }
00248 } else if (opt.propagation() == PROPAGATION_DFA) {
00249
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 {
00269
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
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
00289
00290
00291
00292
00293 if (opt.symmetry() == SYMMETRY_CONDITIONAL) {
00294
00295 for (int r = 13; r--; ) {
00296
00297 for (int s1 = 4; s1--; ) {
00298 for (int s2 = s1; s2--; ) {
00299 int c1 = 13*s1 + r,
00300 c2 = 13*s2 + r;
00301
00302 if (c1 == 0 || c2 == 0) continue;
00303
00304 if (pile[c1] == pile[c2]) continue;
00305
00306 int o1 = c1, o2 = c2;
00307 if (pile[c1] > pile[c2] && layer[c2] >= layer[c1])
00308 std::swap(o1, o2);
00309
00310 BoolVarArgs ba;
00311
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
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
00322 BoolVar cond(*this, 0, 1);
00323 rel(*this, BOT_AND, ba, cond);
00324
00325
00326
00327 rel(*this, !cond || (y[o1] < y[o2]));
00328 }
00329 }
00330 }
00331 }
00332
00333
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
00397 generate(opt.size());
00398 Script::run<BlackHole,DFS,SizeOptions>(opt);
00399 return 0;
00400 }
00401
00402