Generated on Fri Oct 19 11:24:48 2018 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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/driver.hh>
00035 #include <gecode/int.hh>
00036 
00037 #include <vector>
00038 #include <algorithm>
00039 #include <sstream>
00040 
00041 using namespace Gecode;
00042 
00043 namespace {
00044   using std::vector;
00045 
00047   vector<vector<int> > layout;
00049   vector<int> layer, pile;
00050 
00057   void generate(int seed) {
00058     // The layout consists of 17 piles of 3 cards each
00059     layout = vector<vector<int> >(17, vector<int>(3));
00060     // Deck without the Ace of Spades
00061     vector<int> deck(51);
00062     for (int i = 51; i--; ) deck[i] = i+1;
00063     Support::RandomGenerator rnd(seed+1);
00064     std::random_shuffle(deck.begin(), deck.end(), rnd);
00065 
00066     // Place cards from deck
00067     int pos = 0;
00068     for (int i = 17; i--; )
00069       for (int j = 3; j--; )
00070         layout[i][j] = deck[pos++];
00071 
00072     // Location-information for each card
00073     layer = vector<int>(52);
00074     pile  = vector<int>(52);
00075     for (int i = 17; i--; ) {
00076       for (int j = 3; j--; ) {
00077         layer[layout[i][j]] = j;
00078         pile[ layout[i][j]] = i;
00079       }
00080     }
00081   }
00082 }
00083 
00100 class BlackHole : public Script {
00101 protected:
00102   IntVarArray x, 
00103     y; 
00104 
00106   std::string
00107   card(int val) const {
00108     const char* suit = "SCHD";
00109     std::ostringstream o;
00110     o << std::setw(2) << (1 + (val%13)) << suit[val/13];
00111     return o.str();
00112   }
00113 
00114 public:
00116   enum {
00117     SYMMETRY_NONE,       
00118     SYMMETRY_CONDITIONAL 
00119   };
00121   enum {
00122     PROPAGATION_REIFIED,  
00123     PROPAGATION_DFA,      
00124     PROPAGATION_TUPLE_SET 
00125   };
00127   BlackHole(const SizeOptions& opt)
00128     : Script(opt), x(*this, 52, 0,51), y(*this, 52, 0,51) {
00129     // Black ace at bottom
00130     rel(*this, x[0], IRT_EQ, 0);
00131 
00132     // x is order and y is placement
00133     channel(*this, x, y, opt.ipl());
00134 
00135     // The placement rules: the absolute value of the difference
00136     // between two consecutive cards is 1 or 12.
00137     if (opt.propagation() == PROPAGATION_REIFIED) {
00138       // Build table for accessing the rank of a card
00139       IntArgs modtable(52);
00140       for (int i = 0; i < 52; ++i) {
00141         modtable[i] = i%13;
00142       }
00143       for (int i = 0; i < 51; ++i) {
00144         IntVar x1(*this, 0, 12), x2(*this, 0, 12);
00145         element(*this, modtable, x[i], x1);
00146         element(*this, modtable, x[i+1], x2);
00147         const int dr[2] = {1, 12};
00148         IntVar diff(*this, IntSet(dr, 2));
00149         rel(*this, abs(x1-x2) == diff, IPL_DOM);
00150       }
00151     } else if (opt.propagation() == PROPAGATION_DFA) {
00152       // Build table for allowed tuples
00153       REG expression;
00154       for (int r = 13; r--; ) {
00155         for (int s1 = 4; s1--; ) {
00156           for (int s2 = 4; s2--; ) {
00157             for (int i = -1; i <= 1; i+=2) {
00158               REG r1 = REG(r+13*s1);
00159               REG r2 = REG((r+i+52+13*s2)%52);
00160               REG r = r1 + r2;
00161               expression |= r;
00162             }
00163           }
00164         }
00165       }
00166       DFA table(expression);
00167 
00168       for (int i = 51; i--; )
00169         extensional(*this, IntVarArgs({x[i],x[i+1]}), table);
00170 
00171     } else { // opt.propagation() == PROPAGATION_TUPLE_SET)
00172       // Build table for allowed tuples
00173       TupleSet ts(2);
00174       for (int r = 13; r--; )
00175         for (int s1 = 4; s1--; )
00176           for (int s2 = 4; s2--; )
00177             for (int i = -1; i <= 1; i+=2)
00178               ts.add({r+13*s1, (r+i+52+13*s2)%52});
00179       ts.finalize();
00180 
00181       for (int i = 51; i--; )
00182         extensional(*this, IntVarArgs({x[i],x[i+1]}), ts);
00183     }
00184 
00185     // A card must be played before the one under it.
00186     for (int i = 17; i--; )
00187       for (int j = 2; j--; )
00188         rel(*this, y[layout[i][j]] < y[layout[i][j+1]]);
00189 
00190     // Compute and break the conditional symmetries that are dependent
00191     // on the current layout.
00192     // Two cards with the same rank but different suits are symmetric
00193     // with respect to their placement in the black hole if changing
00194     // their order does not affect any other card.
00195     if (opt.symmetry() == SYMMETRY_CONDITIONAL) {
00196       // For all ranks
00197       for (int r = 13; r--; ) {
00198         // For all pairs of suits
00199         for (int s1 = 4; s1--; ) {
00200           for (int s2 = s1; s2--; ) {
00201             int c1 = 13*s1 + r,
00202               c2 = 13*s2 + r;
00203             // The ace of spades is already placed
00204             if (c1 == 0 || c2 == 0) continue;
00205             // Piles are handled by the rules of the game
00206             if (pile[c1] == pile[c2]) continue;
00207             // Fix the right order of the cards
00208             int o1 = c1, o2 = c2;
00209             if (pile[c1] > pile[c2] && layer[c2] >= layer[c1])
00210               std::swap(o1, o2);
00211             // cond is the condition for the symmetry
00212             BoolVarArgs ba;
00213             // Both cards played after the ones on top of them
00214             for (int i = 0; i < layer[o1]; ++i)
00215               ba << expr(*this, (y[layout[pile[o1]][i]] < y[o2]));
00216             for (int i = 0; i < layer[o2]; ++i)
00217               ba << expr(*this, (y[layout[pile[o2]][i]] < y[o1]));
00218             // Both cards played before the ones under them
00219             for (int i = layer[o1]+1; i < 3; ++i)
00220               ba << expr(*this, (y[o2] < y[layout[pile[o1]][i]]));
00221             for (int i = layer[o2]+1; i < 3; ++i)
00222               ba << expr(*this, (y[o1] < y[layout[pile[o2]][i]]));
00223             // Cond holds when all the above holds
00224             BoolVar cond(*this, 0, 1);
00225             rel(*this, BOT_AND, ba, cond);
00226 
00227             // If cond is fulfilled, then we can order the cards
00228             // cond -> (y[o1] < y[o2])
00229             rel(*this, !cond || (y[o1] < y[o2]));
00230           }
00231         }
00232       }
00233     }
00234 
00235     // Install custom brancher
00236     branch(*this, x, INT_VAR_NONE(), INT_VAL(&val));
00237   }
00239   static int val(const Space&, IntVar x, int) {
00240     int v = -1;
00241     int w = 4;
00242     for (IntVarValues vals(x); vals(); ++vals)
00243       if (layer[vals.val()] < w) {
00244         v = vals.val();
00245         if ((w = layer[vals.val()]) == 0)
00246           break;
00247       }
00248     assert(v >= 1 && v < 52);
00249     return v;
00250   }
00252   virtual void
00253   print(std::ostream& os) const {
00254     os << "Layout:" << std::endl;
00255     for (int i = 0; i < 17; i++) {
00256       for (int j = 0; j < 3; j++)
00257         os << card(layout[i][j]) << " ";
00258       if ((i+1) % 3 == 0)
00259         os << std::endl;
00260       else
00261         os << "  \t";
00262     }
00263     os << std::endl << std::endl;
00264 
00265     os << "Solution:" << std::endl;
00266     for (int i = 0; i < 52; ++i) {
00267       if (x[i].assigned())
00268         os << card(x[i].val()) << " ";
00269       else
00270         os << "   ";
00271       if ((i + 1) % 13 == 0)
00272         os << std::endl;
00273     }
00274     os << std::endl;
00275     os << std::endl;
00276   }
00277 
00279   BlackHole(BlackHole& s) : Script(s) {
00280     x.update(*this, s.x);
00281     y.update(*this, s.y);
00282   }
00284   virtual Space*
00285   copy(void) {
00286     return new BlackHole(*this);
00287   }
00288 };
00289 
00293 int
00294 main(int argc, char* argv[]) {
00295   SizeOptions opt("Black Hole patience");
00296   opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL);
00297   opt.symmetry(BlackHole::SYMMETRY_NONE,"none",
00298                "no symmetry breaking");
00299   opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL,"conditional",
00300                "break conditional symmetries");
00301   opt.propagation(BlackHole::PROPAGATION_TUPLE_SET);
00302   opt.propagation(BlackHole::PROPAGATION_REIFIED,
00303                   "reified", "use reified propagation");
00304   opt.propagation(BlackHole::PROPAGATION_DFA,
00305                   "dfa", "use DFA-based extensional propagation");
00306   opt.propagation(BlackHole::PROPAGATION_TUPLE_SET,
00307                   "tuple-set", "use TupleSet-based extensional propagation");
00308   opt.ipl(IPL_DOM);
00309   opt.parse(argc,argv);
00310   // Generates the new board
00311   generate(opt.size());
00312   Script::run<BlackHole,DFS,SizeOptions>(opt);
00313   return 0;
00314 }
00315 
00316 // STATISTICS: example-any