Generated on Wed Nov 5 2014 05:18:15 for Gecode by doxygen 1.7.6.1
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: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
00011  *     $Revision: 13820 $
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 
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     // Black ace at bottom
00135     rel(*this, x[0], IRT_EQ, 0);
00136 
00137     // x is order and y is placement
00138     channel(*this, x, y, opt.icl());
00139 
00140     // The placement rules: the absolute value of the difference
00141     // between two consecutive cards is 1 or 12.
00142     if (opt.propagation() == PROPAGATION_REIFIED) {
00143       // Build table for accessing the rank of a card
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       // Build table for allowed tuples
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 { // opt.propagation() == PROPAGATION_TUPLE_SET)
00177       // Build table for allowed tuples
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     // A card must be played before the one under it.
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     // Compute and break the conditional symmetries that are dependent
00197     // on the current layout.
00198     // Two cards with the same rank but different suits are symmetric
00199     // with respect to their placement in the black hole if changing
00200     // their order does not affect any other card.
00201     if (opt.symmetry() == SYMMETRY_CONDITIONAL) {
00202       // For all ranks
00203       for (int r = 13; r--; ) {
00204         // For all pairs of suits
00205         for (int s1 = 4; s1--; ) {
00206           for (int s2 = s1; s2--; ) {
00207             int c1 = 13*s1 + r,
00208               c2 = 13*s2 + r;
00209             // The ace of spades is already placed
00210             if (c1 == 0 || c2 == 0) continue;
00211             // Piles are handled by the rules of the game
00212             if (pile[c1] == pile[c2]) continue;
00213             // Fix the right order of the cards
00214             int o1 = c1, o2 = c2;
00215             if (pile[c1] > pile[c2] && layer[c2] >= layer[c1])
00216               std::swap(o1, o2);
00217             // cond is the condition for the symmetry
00218             BoolVarArgs ba;
00219             // Both cards played after the ones on top of them
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             // Both cards played before the ones under them
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             // Cond holds when all the above holds
00230             BoolVar cond(*this, 0, 1);
00231             rel(*this, BOT_AND, ba, cond);
00232 
00233             // If cond is fulfilled, then we can order the cards
00234             // cond -> (y[o1] < y[o2])
00235             rel(*this, !cond || (y[o1] < y[o2]));
00236           }
00237         }
00238       }
00239     }
00240 
00241     // Install custom brancher
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   // Generates the new board
00317   generate(opt.size());
00318   Script::run<BlackHole,DFS,SizeOptions>(opt);
00319   return 0;
00320 }
00321 
00322 // STATISTICS: example-any