00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
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
00096 for (int n=x.size(); n--; ) {
00097 if (!x[start].assigned())
00098 return true;
00099
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
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
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
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
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
00310
00311
00312
00313
00314
00315 #ifdef GECODE_HAS_GIST
00316
00317 class KnightsInspector : public Gist::Inspector {
00318 protected:
00320 QGraphicsScene* scene;
00322 QMainWindow* mw;
00324 static const int unit = 30;
00325 public:
00327 KnightsInspector(void) : scene(NULL), mw(NULL) {}
00329 virtual void inspect(const Space& s) {
00330 const Knights& k = static_cast<const Knights&>(s);
00331
00332 if (!scene)
00333 initialize();
00334 QList <QGraphicsItem*> itemList = scene->items();
00335 foreach (QGraphicsItem* i, scene->items()) {
00336 scene->removeItem(i);
00337 delete i;
00338 }
00339
00340 for (int i=0; i<k.n; i++) {
00341 for (int j=0; j<k.n; j++) {
00342 scene->addRect(i*unit,j*unit,unit,unit);
00343
00344 QPen pen(Qt::black, 2);
00345 if (!k.succ[i*k.n+j].assigned()) {
00346 pen.setColor(Qt::red);
00347 pen.setStyle(Qt::DotLine);
00348 pen.setWidth(0);
00349 }
00350 for (IntVarValues xv(k.succ[i*k.n+j]); xv(); ++xv) {
00351 int ky = xv.val() % k.n;
00352 int kx = xv.val() / k.n;
00353 scene->addLine(i*unit+unit/2,j*unit+unit/2,
00354 kx*unit+unit/2,ky*unit+unit/2,
00355 pen);
00356 }
00357
00358 }
00359 }
00360 mw->show();
00361 }
00362
00364 void initialize(void) {
00365 mw = new QMainWindow();
00366 scene = new QGraphicsScene();
00367 QGraphicsView* view = new QGraphicsView(scene);
00368 view->setRenderHints(QPainter::Antialiasing);
00369 mw->setCentralWidget(view);
00370 mw->setAttribute(Qt::WA_QuitOnClose, false);
00371 mw->setAttribute(Qt::WA_DeleteOnClose, false);
00372 QAction* closeWindow = new QAction("Close window", mw);
00373 closeWindow->setShortcut(QKeySequence("Ctrl+W"));
00374 mw->connect(closeWindow, SIGNAL(triggered()),
00375 mw, SLOT(close()));
00376 mw->addAction(closeWindow);
00377 }
00378
00380 virtual std::string name(void) { return "Board"; }
00382 virtual void finalize(void) {
00383 delete mw;
00384 mw = NULL;
00385 }
00386 };
00387 #endif
00388
00392 int
00393 main(int argc, char* argv[]) {
00394 SizeOptions opt("Knights");
00395 opt.iterations(100);
00396 opt.size(8);
00397 opt.propagation(Knights::PROP_CIRCUIT);
00398 opt.propagation(Knights::PROP_REIFIED, "reified");
00399 opt.propagation(Knights::PROP_CIRCUIT, "circuit");
00400 opt.branching(Knights::BRANCH_NAIVE);
00401 opt.branching(Knights::BRANCH_NAIVE, "reified");
00402 opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
00403
00404 #ifdef GECODE_HAS_GIST
00405 KnightsInspector ki;
00406 opt.inspect.click(&ki);
00407 #endif
00408
00409 opt.parse(argc,argv);
00410
00411 if (opt.propagation() == Knights::PROP_REIFIED) {
00412 Script::run<KnightsReified,DFS,SizeOptions>(opt);
00413 } else {
00414 Script::run<KnightsCircuit,DFS,SizeOptions>(opt);
00415 }
00416 return 0;
00417 }
00418
00419
00420