Generated on Tue Jul 27 2010 21:59:09 for Gecode by doxygen 1.7.1

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  *  Last modified:
00012  *     $Date: 2010-07-02 10:59:05 +0200 (Fri, 02 Jul 2010) $ by $Author: schulte $
00013  *     $Revision: 11148 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include <gecode/driver.hh>
00041 #include <gecode/int.hh>
00042 #include <gecode/minimodel.hh>
00043 #include <gecode/graph.hh>
00044 
00045 #ifdef GECODE_HAS_GIST
00046 #include <QtGui>
00047 #endif
00048 
00049 using namespace Gecode;
00050 
00051 
00060 class Warnsdorff : public Brancher {
00061 protected:
00063   ViewArray<Int::IntView> x;
00065   mutable int start;
00067   class Choice : public Gecode::Choice {
00068   public:
00070     int pos;
00072     int val;
00076     Choice(const Brancher& b, int pos0, int val0)
00077       : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00079     virtual size_t size(void) const {
00080       return sizeof(Choice);
00081     }
00082   };
00083  
00085   Warnsdorff(Home home, ViewArray<Int::IntView>& xv) 
00086     : Brancher(home), x(xv), start(0) {}
00088   Warnsdorff(Space& home, bool share, Warnsdorff& b) 
00089     : Brancher(home, share, b), start(b.start) {
00090     x.update(home, share, b.x);
00091   }
00092 public:
00094   virtual bool status(const Space&) const {
00095     // A path to follow can be at most x.size() long
00096     for (int n=x.size(); n--; ) {
00097       if (!x[start].assigned()) 
00098         return true;
00099       // Follow path of assigned variables
00100       start = x[start].val();
00101     }
00102     return false;
00103   }
00105   virtual Gecode::Choice* choice(Space&) {
00106     Int::ViewValues<Int::IntView> iv(x[start]);
00107     int n = iv.val();
00108     unsigned int min = x[n].size();
00109     ++iv;
00110     // Choose the value with the fewest neighbors
00111     while (iv()) {
00112       if (x[iv.val()].size() < min) {
00113         n = iv.val();
00114         min = x[n].size();
00115       }
00116       ++iv;
00117     }
00118     return new Choice(*this, start, n);
00119   }
00121   virtual ExecStatus commit(Space& home, const Gecode::Choice& _c, 
00122                             unsigned int a) {
00123     const Choice& c = static_cast<const Choice&>(_c);
00124     if (a == 0)
00125       return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
00126     else 
00127       return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
00128   }
00130   virtual Actor* copy(Space& home, bool share) {
00131     return new (home) Warnsdorff(home, share, *this);
00132   }
00134   static void post(Home home, const IntVarArgs& x) {
00135     ViewArray<Int::IntView> xv(home, x);
00136     (void) new (home) Warnsdorff(home, xv);
00137   }
00139   virtual size_t dispose(Space&) {
00140     return sizeof(*this);
00141   }
00142 };
00143 
00144 
00146 class Knights : public Script {
00147 public:
00149   const int n;
00151   IntVarArray succ;
00153   enum {
00154     PROP_REIFIED, 
00155     PROP_CIRCUIT  
00156   };
00158   enum {
00159     BRANCH_NAIVE,      
00160     BRANCH_WARNSDORFF, 
00161   };
00163   int f(int x, int y) const {
00164     return x + y*n;
00165   }
00167   int x(int f) const {
00168     return f % n;
00169   }
00171   int y(int f) const {
00172     return f / n;
00173   }
00175   IntSet neighbors(int i) {
00176     static const int moves[8][2] = {
00177       {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
00178     };
00179     int nbs[8]; int n_nbs = 0;
00180     for (int m=0; m<8; m++) {
00181       int nx = x(i) + moves[m][0], ny = y(i) + moves[m][1];
00182       if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n))
00183         nbs[n_nbs++] = f(nx,ny);
00184     }
00185     return IntSet(nbs,n_nbs);
00186   }
00188   Knights(const SizeOptions& opt)
00189     : n(opt.size()), succ(*this,n*n,0,n*n-1) {
00190     switch (opt.branching()) {
00191     case BRANCH_NAIVE:
00192       branch(*this, succ, INT_VAR_NONE, INT_VAL_MIN);
00193       break;
00194     case BRANCH_WARNSDORFF:
00195       Warnsdorff::post(*this, succ);
00196       break;
00197     }
00198   }
00200   Knights(bool share, Knights& s) : Script(share,s), n(s.n) {
00201     succ.update(*this, share, s.succ);
00202   }
00204   virtual void
00205   print(std::ostream& os) const {
00206     int* jump = new int[n*n];
00207     {
00208       int j=0;
00209       for (int i=0; i<n*n; i++) {
00210         jump[j]=i; j=succ[j].min();
00211       }
00212     }
00213     os << "\t";
00214     for (int i = 0; i < n; i++) {
00215       for (int j = 0; j < n; j++) {
00216         os.width(3);
00217         os << jump[f(i,j)] << " ";
00218         }
00219         os << std::endl << "\t";
00220     }
00221     os << std::endl;
00222     delete [] jump;
00223   }
00224 };
00225 
00236 class KnightsReified : public Knights {
00237 public:
00238   KnightsReified(const SizeOptions& opt) : Knights(opt) {
00239     const int nn = n*n;
00240 
00241     // Map knight to its predecessor of succesor on board
00242     IntVarArgs jump(nn);
00243     IntVarArgs pred(nn);
00244 
00245     for (int i = nn; i--; ) {
00246       IntVar p(*this,0,nn-1); pred[i]=p;
00247       IntVar j(*this,0,nn-1); jump[i]=j;
00248     }
00249 
00250     // Place the first two knights
00251     rel(*this, jump[f(0,0)], IRT_EQ, 0);
00252     rel(*this, jump[f(1,2)], IRT_EQ, 1);
00253 
00254     distinct(*this, jump, opt.icl());
00255     channel(*this, succ, pred, opt.icl());
00256 
00257     for (int f = 0; f < nn; f++) {
00258       IntSet ds = neighbors(f);
00259       for (IntSetValues i(ds); i(); ++i)
00260         rel(*this,
00261             expr(*this, (jump[i.val()]-jump[f] == 1)),
00262             BOT_XOR,
00263             expr(*this, (jump[i.val()]-jump[f] == 1-nn)),
00264             expr(*this, (succ[f] == i.val())));
00265       dom(*this, pred[f], ds);
00266       dom(*this, succ[f], ds);
00267       rel(*this, succ[f], IRT_NQ, pred[f]);
00268     }
00269   }
00271   KnightsReified(bool share, KnightsReified& s) : Knights(share,s) {}
00273   virtual Space*
00274   copy(bool share) {
00275     return new KnightsReified(share,*this);
00276   }
00277 };
00278 
00289 class KnightsCircuit : public Knights {
00290 public:
00291   KnightsCircuit(const SizeOptions& opt) : Knights(opt) {
00292     // Fix the first move
00293     rel(*this, succ[0], IRT_EQ, f(1,2));
00294 
00295     circuit(*this, succ, opt.icl());
00296 
00297     for (int f = 0; f < n*n; f++)
00298       dom(*this, succ[f], neighbors(f));
00299   }
00301   KnightsCircuit(bool share, KnightsCircuit& s) : Knights(share,s) {}
00303   virtual Space*
00304   copy(bool share) {
00305     return new KnightsCircuit(share,*this);
00306   }
00307 };
00308 
00309 #ifdef GECODE_HAS_GIST
00310 
00311 class KnightsInspector : public Gist::Inspector {
00312 protected:
00314   QGraphicsScene* scene;
00316   QMainWindow* mw;
00318   static const int unit = 30;
00319 public:
00321   KnightsInspector(void) : scene(NULL), mw(NULL) {}
00323   virtual void inspect(const Space& s) {
00324     const Knights& k = static_cast<const Knights&>(s);
00325     
00326     if (!scene)
00327       initialize();
00328     QList <QGraphicsItem*> itemList = scene->items();
00329     foreach (QGraphicsItem* i, scene->items()) {
00330       scene->removeItem(i);
00331       delete i;
00332     }
00333 
00334     for (int i=0; i<k.n; i++) {
00335       for (int j=0; j<k.n; j++) {
00336         scene->addRect(i*unit,j*unit,unit,unit);
00337         
00338         QPen pen(Qt::black, 2);
00339         if (!k.succ[i*k.n+j].assigned()) {
00340           pen.setColor(Qt::red);
00341           pen.setStyle(Qt::DotLine);
00342           pen.setWidth(0);
00343         }
00344         for (IntVarValues xv(k.succ[i*k.n+j]); xv(); ++xv) {
00345           int ky = xv.val() % k.n;
00346           int kx = xv.val() / k.n;
00347           scene->addLine(i*unit+unit/2,j*unit+unit/2,
00348                          kx*unit+unit/2,ky*unit+unit/2,
00349                          pen);
00350         }
00351         
00352       }
00353     }
00354     mw->show();    
00355   }
00356   
00358   void initialize(void) {
00359     mw = new QMainWindow();
00360     scene = new QGraphicsScene();
00361     QGraphicsView* view = new QGraphicsView(scene);
00362     view->setRenderHints(QPainter::Antialiasing);
00363     mw->setCentralWidget(view);
00364     mw->setAttribute(Qt::WA_QuitOnClose, false);
00365     mw->setAttribute(Qt::WA_DeleteOnClose, false);
00366     QAction* closeWindow = new QAction("Close window", mw);
00367     closeWindow->setShortcut(QKeySequence("Ctrl+W"));
00368     mw->connect(closeWindow, SIGNAL(triggered()),
00369                 mw, SLOT(close()));
00370     mw->addAction(closeWindow);
00371   }
00372   
00374   virtual std::string name(void) { return "Board"; }
00376   virtual void finalize(void) {
00377     delete mw;
00378     mw = NULL;
00379   }
00380 };
00381 #endif GECODE_HAS_GIST
00382 
00386 int
00387 main(int argc, char* argv[]) {
00388   SizeOptions opt("Knights");
00389   opt.iterations(100);
00390   opt.size(8);
00391   opt.propagation(Knights::PROP_CIRCUIT);
00392   opt.propagation(Knights::PROP_REIFIED, "reified");
00393   opt.propagation(Knights::PROP_CIRCUIT, "circuit");
00394   opt.branching(Knights::BRANCH_NAIVE);
00395   opt.branching(Knights::BRANCH_NAIVE, "reified");
00396   opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
00397 
00398 #ifdef GECODE_HAS_GIST
00399   KnightsInspector ki;
00400   opt.inspect.click(&ki);
00401 #endif
00402 
00403   opt.parse(argc,argv);
00404 
00405   if (opt.propagation() == Knights::PROP_REIFIED) {
00406     Script::run<KnightsReified,DFS,SizeOptions>(opt);
00407   } else {
00408     Script::run<KnightsCircuit,DFS,SizeOptions>(opt);
00409   }
00410   return 0;
00411 }
00412 
00413 // STATISTICS: example-any
00414