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
00104 class BlackHole : public Script {
00105 protected:
00106 IntVarArray x,
00107 y;
00108
00110 std::string
00111 card(int val) const {
00112 const char* suit = "SCHD";
00113 std::ostringstream o;
00114 o << std::setw(2) << (1 + (val%13)) << suit[val/13];
00115 return o.str();
00116 }
00117
00118 public:
00120 enum {
00121 SYMMETRY_NONE,
00122 SYMMETRY_CONDITIONAL
00123 };
00125 enum {
00126 PROPAGATION_REIFIED,
00127 PROPAGATION_DFA,
00128 PROPAGATION_TUPLE_SET
00129 };
00131 BlackHole(const SizeOptions& opt)
00132 : x(*this, 52, 0,51), y(*this, 52, 0,51)
00133 {
00134
00135 rel(*this, x[0], IRT_EQ, 0);
00136
00137
00138 channel(*this, x, y, opt.icl());
00139
00140
00141
00142 if (opt.propagation() == PROPAGATION_REIFIED) {
00143
00144 IntArgs modtable(52);
00145 for (int i = 0; i < 52; ++i) {
00146 modtable[i] = i%13;
00147 }
00148 for (int i = 0; i < 51; ++i) {
00149 IntVar x1(*this, 0, 12), x2(*this, 0, 12);
00150 element(*this, modtable, x[i], x1);
00151 element(*this, modtable, x[i+1], x2);
00152 const int dr[2] = {1, 12};
00153 IntVar diff(*this, IntSet(dr, 2));
00154 rel(*this, abs(x1-x2) == diff, ICL_DOM);
00155 }
00156 } else if (opt.propagation() == PROPAGATION_DFA) {
00157
00158 REG expression;
00159 for (int r = 13; r--; ) {
00160 for (int s1 = 4; s1--; ) {
00161 for (int s2 = 4; s2--; ) {
00162 for (int i = -1; i <= 1; i+=2) {
00163 REG r1 = REG(r+13*s1);
00164 REG r2 = REG((r+i+52+13*s2)%52);
00165 REG r = r1 + r2;
00166 expression |= r;
00167 }
00168 }
00169 }
00170 }
00171 DFA table(expression);
00172
00173 for (int i = 51; i--; )
00174 extensional(*this, IntVarArgs() << x[i] << x[i+1], table);
00175
00176 } else {
00177
00178 TupleSet tupleSet;
00179 for (int r = 13; r--; )
00180 for (int s1 = 4; s1--; )
00181 for (int s2 = 4; s2--; )
00182 for (int i = -1; i <= 1; i+=2) {
00183 tupleSet.add(IntArgs(2, r+13*s1, (r+i+52+13*s2)%52));
00184 }
00185 tupleSet.finalize();
00186
00187 for (int i = 51; i--; )
00188 extensional(*this, IntVarArgs() << x[i] << x[i+1], tupleSet);
00189 }
00190
00191
00192 for (int i = 17; i--; )
00193 for (int j = 2; j--; )
00194 rel(*this, y[layout[i][j]] < y[layout[i][j+1]]);
00195
00196
00197
00198
00199
00200
00201 if (opt.symmetry() == SYMMETRY_CONDITIONAL) {
00202
00203 for (int r = 13; r--; ) {
00204
00205 for (int s1 = 4; s1--; ) {
00206 for (int s2 = s1; s2--; ) {
00207 int c1 = 13*s1 + r,
00208 c2 = 13*s2 + r;
00209
00210 if (c1 == 0 || c2 == 0) continue;
00211
00212 if (pile[c1] == pile[c2]) continue;
00213
00214 int o1 = c1, o2 = c2;
00215 if (pile[c1] > pile[c2] && layer[c2] >= layer[c1])
00216 std::swap(o1, o2);
00217
00218 BoolVarArgs ba;
00219
00220 for (int i = 0; i < layer[o1]; ++i)
00221 ba << expr(*this, (y[layout[pile[o1]][i]] < y[o2]));
00222 for (int i = 0; i < layer[o2]; ++i)
00223 ba << expr(*this, (y[layout[pile[o2]][i]] < y[o1]));
00224
00225 for (int i = layer[o1]+1; i < 3; ++i)
00226 ba << expr(*this, (y[o2] < y[layout[pile[o1]][i]]));
00227 for (int i = layer[o2]+1; i < 3; ++i)
00228 ba << expr(*this, (y[o1] < y[layout[pile[o2]][i]]));
00229
00230 BoolVar cond(*this, 0, 1);
00231 rel(*this, BOT_AND, ba, cond);
00232
00233
00234
00235 rel(*this, !cond || (y[o1] < y[o2]));
00236 }
00237 }
00238 }
00239 }
00240
00241
00242 branch(*this, x, INT_VAR_NONE(), INT_VAL(&val));
00243 }
00245 static int val(const Space&, IntVar x, int) {
00246 int v = -1;
00247 int w = 4;
00248 for (IntVarValues vals(x); vals(); ++vals)
00249 if (layer[vals.val()] < w) {
00250 v = vals.val();
00251 if ((w = layer[vals.val()]) == 0)
00252 break;
00253 }
00254 assert(v >= 1 && v < 52);
00255 return v;
00256 }
00258 virtual void
00259 print(std::ostream& os) const {
00260 os << "Layout:" << std::endl;
00261 for (int i = 0; i < 17; i++) {
00262 for (int j = 0; j < 3; j++)
00263 os << card(layout[i][j]) << " ";
00264 if ((i+1) % 3 == 0)
00265 os << std::endl;
00266 else
00267 os << " \t";
00268 }
00269 os << std::endl << std::endl;
00270
00271 os << "Solution:" << std::endl;
00272 for (int i = 0; i < 52; ++i) {
00273 if (x[i].assigned())
00274 os << card(x[i].val()) << " ";
00275 else
00276 os << " ";
00277 if ((i + 1) % 13 == 0)
00278 os << std::endl;
00279 }
00280 os << std::endl;
00281 os << std::endl;
00282 }
00283
00285 BlackHole(bool share, BlackHole& s) : Script(share,s) {
00286 x.update(*this, share, s.x);
00287 y.update(*this, share, s.y);
00288 }
00290 virtual Space*
00291 copy(bool share) {
00292 return new BlackHole(share,*this);
00293 }
00294 };
00295
00299 int
00300 main(int argc, char* argv[]) {
00301 SizeOptions opt("Black Hole patience");
00302 opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL);
00303 opt.symmetry(BlackHole::SYMMETRY_NONE,"none",
00304 "no symmetry breaking");
00305 opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL,"conditional",
00306 "break conditional symmetries");
00307 opt.propagation(BlackHole::PROPAGATION_DFA);
00308 opt.propagation(BlackHole::PROPAGATION_REIFIED,
00309 "reified", "use reified propagation");
00310 opt.propagation(BlackHole::PROPAGATION_DFA,
00311 "dfa", "use DFA-based extensional propagation");
00312 opt.propagation(BlackHole::PROPAGATION_TUPLE_SET,
00313 "tuple-set", "use TupleSet-based extensional propagation");
00314 opt.icl(ICL_DOM);
00315 opt.parse(argc,argv);
00316
00317 generate(opt.size());
00318 Script::run<BlackHole,DFS,SizeOptions>(opt);
00319 return 0;
00320 }
00321
00322