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