Generated on Mon Nov 30 23:53:17 2009 for Gecode by doxygen 1.6.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: 2009-10-07 11:13:58 +0200 (Wed, 07 Oct 2009) $ by $Author: tack $
00013  *     $Revision: 9848 $
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 using namespace Gecode;
00046 
00047 
00056 class Warnsdorff : public Brancher {
00057 protected:
00059   ViewArray<Int::IntView> x;
00061   mutable int start;
00063   class Choice : public Gecode::Choice {
00064   public:
00066     int pos;
00068     int val;
00072     Choice(const Brancher& b, int pos0, int val0)
00073       : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00075     virtual size_t size(void) const {
00076       return sizeof(Choice);
00077     }
00078   };
00079  
00081   Warnsdorff(Space& home, ViewArray<Int::IntView>& xv) 
00082     : Brancher(home), x(xv), start(0) {}
00084   Warnsdorff(Space& home, bool share, Warnsdorff& b) 
00085     : Brancher(home, share, b), start(b.start) {
00086     x.update(home, share, b.x);
00087   }
00088 public:
00090   virtual bool status(const Space&) const {
00091     // Follow path of assigned variables
00092     while (true) {
00093       if (!x[start].assigned()) 
00094         return true;
00095       start = x[start].val();
00096       if (start == 0) 
00097         return false;
00098     }
00099   }
00101   virtual Gecode::Choice* choice(Space&) {
00102     Int::ViewValues<Int::IntView> iv(x[start]);
00103     int n = iv.val();
00104     unsigned int min = x[n].size();
00105     ++iv;
00106     // Choose the value with the fewest neighbours
00107     while (iv()) {
00108       if (x[iv.val()].size() < min) {
00109         n = iv.val();
00110         min = x[n].size();
00111       }
00112       ++iv;
00113     }
00114     return new Choice(*this, start, n);
00115   }
00117   virtual ExecStatus commit(Space& home, const Gecode::Choice& _c, 
00118                             unsigned int a) {
00119     const Choice& c = static_cast<const Choice&>(_c);
00120     if (a == 0)
00121       return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
00122     else 
00123       return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
00124   }
00126   virtual Actor* copy(Space& home, bool share) {
00127     return new (home) Warnsdorff(home, share, *this);
00128   }
00130   static void post(Space& home, const IntVarArgs& x) {
00131     ViewArray<Int::IntView> xv(home, x);
00132     (void) new (home) Warnsdorff(home, xv);
00133   }
00135   virtual size_t dispose(Space&) {
00136     return sizeof(*this);
00137   }
00138 };
00139 
00140 
00142 class Knights : public Script {
00143 protected:
00145   const int n;
00147   IntVarArray succ;
00148 public:
00150   enum {
00151     PROP_REIFIED, 
00152     PROP_CIRCUIT  
00153   };
00155   enum {
00156     BRANCH_NAIVE,      
00157     BRANCH_WARNSDORFF, 
00158   };
00160   int
00161   field(int x, int y) const {
00162     return x*n+y;
00163   }
00165   void
00166   neighbours(int f, int nbs[8], int& n_nbs) {
00167     n_nbs=0;
00168     int x = f / n;
00169     int y = f % n;
00170     for (int i=0;i<8;i++) {
00171       static const int moves[8][2] = {
00172         {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
00173       };
00174       int nx=x+moves[i][0];
00175       int ny=y+moves[i][1];
00176       if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n))
00177         nbs[n_nbs++]=field(nx,ny);
00178     }
00179   }
00181   Knights(const SizeOptions& opt)
00182     : n(opt.size()), succ(*this,n*n,0,n*n-1) {
00183     switch (opt.branching()) {
00184     case BRANCH_NAIVE:
00185       branch(*this, succ, INT_VAR_NONE, INT_VAL_MIN);
00186       break;
00187     case BRANCH_WARNSDORFF:
00188       Warnsdorff::post(*this, succ);
00189       break;
00190     }
00191   }
00193   Knights(bool share, Knights& s) : Script(share,s), n(s.n) {
00194     succ.update(*this, share, s.succ);
00195   }
00197   virtual void
00198   print(std::ostream& os) const {
00199     int* jump = new int[n*n];
00200     {
00201       int j=0;
00202       for (int i=0; i<n*n; i++) {
00203         jump[j]=i; j=succ[j].min();
00204       }
00205     }
00206     os << "\t";
00207     for (int i = 0; i < n; i++) {
00208       for (int j = 0; j < n; j++) {
00209         os.width(3);
00210         os << jump[field(i,j)] << " ";
00211         }
00212         os << std::endl << "\t";
00213     }
00214     os << std::endl;
00215     delete [] jump;
00216   }
00217 };
00218 
00229 class KnightsReified : public Knights {
00230 public:
00231   KnightsReified(const SizeOptions& opt) : Knights(opt) {
00232     const int nn = n*n;
00233 
00234     // Map knight to its predecessor of succesor on board
00235     IntVarArgs jump(nn);
00236     IntVarArgs pred(nn);
00237 
00238     for (int i = nn; i--; ) {
00239       IntVar p(*this,0,nn-1); pred[i]=p;
00240       IntVar j(*this,0,nn-1); jump[i]=j;
00241     }
00242 
00243     // Place the first two knights
00244     rel(*this, jump[field(0,0)], IRT_EQ, 0);
00245     rel(*this, jump[field(1,2)], IRT_EQ, 1);
00246 
00247     distinct(*this, jump, opt.icl());
00248     channel(*this, succ, pred, opt.icl());
00249 
00250     for (int f = 0; f < nn; f++) {
00251       // Array of neighbours
00252       int nbs[8]; int n_nbs = 0;
00253       neighbours(f, nbs, n_nbs);
00254       for (int i=n_nbs; i--; )
00255         rel(*this,
00256             post(*this, ~(jump[nbs[i]]-jump[f] == 1)),
00257             BOT_XOR,
00258             post(*this, ~(jump[nbs[i]]-jump[f] == 1-nn)),
00259             post(*this, ~(succ[f] == nbs[i])));
00260 
00261       IntSet ds(nbs, n_nbs);
00262       dom(*this, pred[f], ds);
00263       dom(*this, succ[f], ds);
00264       rel(*this, succ[f], IRT_NQ, pred[f]);
00265     }
00266   }
00268   KnightsReified(bool share, KnightsReified& s) : Knights(share,s) {}
00270   virtual Space*
00271   copy(bool share) {
00272     return new KnightsReified(share,*this);
00273   }
00274 };
00275 
00286 class KnightsCircuit : public Knights {
00287 public:
00288   KnightsCircuit(const SizeOptions& opt) : Knights(opt) {
00289     // Fix the first move
00290     rel(*this, succ[0], IRT_EQ, field(1,2));
00291 
00292     circuit(*this, succ, opt.icl());
00293 
00294     for (int f = 0; f < n*n; f++) {
00295       // Array of neighbours
00296       int nbs[8]; int n_nbs = 0;
00297       neighbours(f, nbs, n_nbs);
00298       IntSet ds(nbs, n_nbs);
00299       dom(*this, succ[f], ds);
00300     }
00301   }
00303   KnightsCircuit(bool share, KnightsCircuit& s) : Knights(share,s) {}
00305   virtual Space*
00306   copy(bool share) {
00307     return new KnightsCircuit(share,*this);
00308   }
00309 };
00310 
00314 int
00315 main(int argc, char* argv[]) {
00316   SizeOptions opt("Knights");
00317   opt.iterations(100);
00318   opt.size(8);
00319   opt.propagation(Knights::PROP_CIRCUIT);
00320   opt.propagation(Knights::PROP_REIFIED, "reified");
00321   opt.propagation(Knights::PROP_CIRCUIT, "circuit");
00322   opt.branching(Knights::BRANCH_NAIVE);
00323   opt.branching(Knights::BRANCH_NAIVE, "reified");
00324   opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
00325   opt.parse(argc,argv);
00326   if (opt.propagation() == Knights::PROP_REIFIED) {
00327     Script::run<KnightsReified,DFS,SizeOptions>(opt);
00328   } else {
00329     Script::run<KnightsCircuit,DFS,SizeOptions>(opt);
00330   }
00331   return 0;
00332 }
00333 
00334 // STATISTICS: example-any
00335