Generated on Fri Oct 19 11:24:48 2018 for Gecode by doxygen 1.6.3

knights.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  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Mikael Lagerkvist, 2008
00009  *     Christian Schulte, 2001
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #include <gecode/driver.hh>
00037 #include <gecode/int.hh>
00038 #include <gecode/minimodel.hh>
00039 
00040 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00041 #include <QtGui>
00042 #if QT_VERSION >= 0x050000
00043 #include <QtWidgets>
00044 #endif
00045 #endif
00046 
00047 using namespace Gecode;
00048 
00049 
00058 class Warnsdorff : public Brancher {
00059 protected:
00061   ViewArray<Int::IntView> x;
00063   mutable int start;
00065   class Choice : public Gecode::Choice {
00066   public:
00068     int pos;
00070     int val;
00074     Choice(const Brancher& b, int pos0, int val0)
00075       : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00077     virtual void archive(Archive& e) const {
00078       Gecode::Choice::archive(e);
00079       e << pos << val;
00080     }
00081   };
00082 
00084   Warnsdorff(Home home, ViewArray<Int::IntView>& xv)
00085     : Brancher(home), x(xv), start(0) {}
00087   Warnsdorff(Space& home, Warnsdorff& b)
00088     : Brancher(home, b), start(b.start) {
00089     x.update(home, b.x);
00090   }
00091 public:
00093   virtual bool status(const Space&) const {
00094     // A path to follow can be at most x.size() long
00095     for (int n=x.size(); n--; ) {
00096       if (!x[start].assigned())
00097         return true;
00098       // Follow path of assigned variables
00099       start = x[start].val();
00100     }
00101     return false;
00102   }
00104   virtual Gecode::Choice* choice(Space&) {
00105     Int::ViewValues<Int::IntView> iv(x[start]);
00106     int n = iv.val();
00107     unsigned int min = x[n].size();
00108     ++iv;
00109     // Choose the value with the fewest neighbors
00110     while (iv()) {
00111       if (x[iv.val()].size() < min) {
00112         n = iv.val();
00113         min = x[n].size();
00114       }
00115       ++iv;
00116     }
00117     return new Choice(*this, start, n);
00118   }
00120   virtual Choice* choice(const Space&, Archive& e) {
00121     int pos, val;
00122     e >> pos >> val;
00123     return new Choice(*this, pos, val);
00124   }
00126   virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00127                             unsigned int a) {
00128     const Choice& c = static_cast<const Choice&>(_c);
00129     if (a == 0)
00130       return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
00131     else
00132       return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
00133   }
00135   virtual void print(const Space&, const Gecode::Choice& _c,
00136                      unsigned int a,
00137                      std::ostream& o) const {
00138     const Choice& c = static_cast<const Choice&>(_c);
00139     o << "x[" << c.pos << "] "
00140       << ((a == 0) ? "=" : "!=")
00141       << " " << c.val;
00142   }
00144   virtual Actor* copy(Space& home) {
00145     return new (home) Warnsdorff(home, *this);
00146   }
00148   static void post(Home home, const IntVarArgs& x) {
00149     ViewArray<Int::IntView> xv(home, x);
00150     (void) new (home) Warnsdorff(home, xv);
00151   }
00153   virtual size_t dispose(Space&) {
00154     return sizeof(*this);
00155   }
00156 };
00157 
00158 
00160 class Knights : public Script {
00161 public:
00163   const int n;
00165   IntVarArray succ;
00167   enum {
00168     PROP_REIFIED, 
00169     PROP_CIRCUIT  
00170   };
00172   enum {
00173     BRANCH_NAIVE,      
00174     BRANCH_WARNSDORFF, 
00175   };
00177   int f(int x, int y) const {
00178     return x + y*n;
00179   }
00181   int x(int f) const {
00182     return f % n;
00183   }
00185   int y(int f) const {
00186     return f / n;
00187   }
00189   IntSet neighbors(int i) {
00190     static const int moves[8][2] = {
00191       {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
00192     };
00193     int nbs[8]; int n_nbs = 0;
00194     for (int m=0; m<8; m++) {
00195       int nx = x(i) + moves[m][0], ny = y(i) + moves[m][1];
00196       if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n))
00197         nbs[n_nbs++] = f(nx,ny);
00198     }
00199     return IntSet(nbs,n_nbs);
00200   }
00202   Knights(const SizeOptions& opt)
00203     : Script(opt), n(opt.size()), succ(*this,n*n,0,n*n-1) {
00204     switch (opt.branching()) {
00205     case BRANCH_NAIVE:
00206       branch(*this, succ, INT_VAR_NONE(), INT_VAL_MIN());
00207       break;
00208     case BRANCH_WARNSDORFF:
00209       Warnsdorff::post(*this, succ);
00210       break;
00211     }
00212   }
00214   Knights(Knights& s) : Script(s), n(s.n) {
00215     succ.update(*this, s.succ);
00216   }
00218   virtual void
00219   print(std::ostream& os) const {
00220     int* jump = new int[n*n];
00221     {
00222       int j=0;
00223       for (int i=0; i<n*n; i++) {
00224         jump[j]=i; j=succ[j].min();
00225       }
00226     }
00227     os << "\t";
00228     for (int i = 0; i < n; i++) {
00229       for (int j = 0; j < n; j++) {
00230         os.width(3);
00231         os << jump[f(i,j)] << " ";
00232         }
00233         os << std::endl << "\t";
00234     }
00235     os << std::endl;
00236     delete [] jump;
00237   }
00238 };
00239 
00250 class KnightsReified : public Knights {
00251 public:
00252   KnightsReified(const SizeOptions& opt) : Knights(opt) {
00253     const int nn = n*n;
00254 
00255     // Map knight to its predecessor of succesor on board
00256     IntVarArgs jump(nn);
00257     IntVarArgs pred(nn);
00258 
00259     for (int i = nn; i--; ) {
00260       IntVar p(*this,0,nn-1); pred[i]=p;
00261       IntVar j(*this,0,nn-1); jump[i]=j;
00262     }
00263 
00264     // Place the first two knights
00265     rel(*this, jump[f(0,0)], IRT_EQ, 0);
00266     rel(*this, jump[f(1,2)], IRT_EQ, 1);
00267 
00268     distinct(*this, jump, opt.ipl());
00269     channel(*this, succ, pred, opt.ipl());
00270 
00271     for (int f = 0; f < nn; f++) {
00272       IntSet ds = neighbors(f);
00273       for (IntSetValues i(ds); i(); ++i)
00274         rel(*this,
00275             expr(*this, (jump[i.val()]-jump[f] == 1)),
00276             BOT_XOR,
00277             expr(*this, (jump[i.val()]-jump[f] == 1-nn)),
00278             expr(*this, (succ[f] == i.val())));
00279       dom(*this, pred[f], ds);
00280       dom(*this, succ[f], ds);
00281       rel(*this, succ[f], IRT_NQ, pred[f]);
00282     }
00283   }
00285   KnightsReified(KnightsReified& s) : Knights(s) {}
00287   virtual Space*
00288   copy(void) {
00289     return new KnightsReified(*this);
00290   }
00291 };
00292 
00303 class KnightsCircuit : public Knights {
00304 public:
00305   KnightsCircuit(const SizeOptions& opt) : Knights(opt) {
00306     // Fix the first move
00307     rel(*this, succ[0], IRT_EQ, f(1,2));
00308 
00309     circuit(*this, succ, opt.ipl());
00310 
00311     for (int f = 0; f < n*n; f++)
00312       dom(*this, succ[f], neighbors(f));
00313   }
00315   KnightsCircuit(KnightsCircuit& s) : Knights(s) {}
00317   virtual Space*
00318   copy(void) {
00319     return new KnightsCircuit(*this);
00320   }
00321 };
00322 
00323 /*
00324  * Just to fool some scripts:
00325  * \brief %Example: n-Knight's tour
00326  *
00327  */
00328 
00329 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00330 
00331 class KnightsInspector : public Gist::Inspector {
00332 protected:
00334   QGraphicsScene* scene;
00336   QMainWindow* mw;
00338   static const int unit = 30;
00339 public:
00341   KnightsInspector(void) : scene(NULL), mw(NULL) {}
00343   virtual void inspect(const Space& s) {
00344     const Knights& k = static_cast<const Knights&>(s);
00345 
00346     if (!scene)
00347       initialize();
00348     QList <QGraphicsItem*> itemList = scene->items();
00349     foreach (QGraphicsItem* i, scene->items()) {
00350       scene->removeItem(i);
00351       delete i;
00352     }
00353 
00354     for (int i=0; i<k.n; i++) {
00355       for (int j=0; j<k.n; j++) {
00356         scene->addRect(i*unit,j*unit,unit,unit);
00357 
00358         QPen pen(Qt::black, 2);
00359         if (!k.succ[i*k.n+j].assigned()) {
00360           pen.setColor(Qt::red);
00361           pen.setStyle(Qt::DotLine);
00362           pen.setWidth(0);
00363         }
00364         for (IntVarValues xv(k.succ[i*k.n+j]); xv(); ++xv) {
00365           int ky = xv.val() % k.n;
00366           int kx = xv.val() / k.n;
00367           scene->addLine(i*unit+unit/2,j*unit+unit/2,
00368                          kx*unit+unit/2,ky*unit+unit/2,
00369                          pen);
00370         }
00371 
00372       }
00373     }
00374     mw->show();
00375   }
00376 
00378   void initialize(void) {
00379     mw = new QMainWindow();
00380     scene = new QGraphicsScene();
00381     QGraphicsView* view = new QGraphicsView(scene);
00382     view->setRenderHints(QPainter::Antialiasing);
00383     mw->setCentralWidget(view);
00384     mw->setAttribute(Qt::WA_QuitOnClose, false);
00385     mw->setAttribute(Qt::WA_DeleteOnClose, false);
00386     QAction* closeWindow = new QAction("Close window", mw);
00387     closeWindow->setShortcut(QKeySequence("Ctrl+W"));
00388     mw->connect(closeWindow, SIGNAL(triggered()),
00389                 mw, SLOT(close()));
00390     mw->addAction(closeWindow);
00391   }
00392 
00394   virtual std::string name(void) { return "Board"; }
00396   virtual void finalize(void) {
00397     delete mw;
00398     mw = NULL;
00399   }
00400 };
00401 #endif
00402 
00406 int
00407 main(int argc, char* argv[]) {
00408   SizeOptions opt("Knights");
00409   opt.iterations(100);
00410   opt.size(8);
00411   opt.propagation(Knights::PROP_CIRCUIT);
00412   opt.propagation(Knights::PROP_REIFIED, "reified");
00413   opt.propagation(Knights::PROP_CIRCUIT, "circuit");
00414   opt.branching(Knights::BRANCH_NAIVE);
00415   opt.branching(Knights::BRANCH_NAIVE, "naive");
00416   opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
00417 
00418 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00419   KnightsInspector ki;
00420   opt.inspect.click(&ki);
00421 #endif
00422 
00423   opt.parse(argc,argv);
00424 
00425   if (opt.propagation() == Knights::PROP_REIFIED) {
00426     Script::run<KnightsReified,DFS,SizeOptions>(opt);
00427   } else {
00428     Script::run<KnightsCircuit,DFS,SizeOptions>(opt);
00429   }
00430   return 0;
00431 }
00432 
00433 // STATISTICS: example-any
00434