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
00044 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00045 #include <QtGui>
00046 #if QT_VERSION >= 0x050000
00047 #include <QtWidgets>
00048 #endif
00049 #endif
00050
00051 using namespace Gecode;
00052
00053
00062 class Warnsdorff : public Brancher {
00063 protected:
00065 ViewArray<Int::IntView> x;
00067 mutable int start;
00069 class Choice : public Gecode::Choice {
00070 public:
00072 int pos;
00074 int val;
00078 Choice(const Brancher& b, int pos0, int val0)
00079 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00081 virtual size_t size(void) const {
00082 return sizeof(Choice);
00083 }
00085 virtual void archive(Archive& e) const {
00086 Gecode::Choice::archive(e);
00087 e << pos << val;
00088 }
00089 };
00090
00092 Warnsdorff(Home home, ViewArray<Int::IntView>& xv)
00093 : Brancher(home), x(xv), start(0) {}
00095 Warnsdorff(Space& home, bool share, Warnsdorff& b)
00096 : Brancher(home, share, b), start(b.start) {
00097 x.update(home, share, b.x);
00098 }
00099 public:
00101 virtual bool status(const Space&) const {
00102
00103 for (int n=x.size(); n--; ) {
00104 if (!x[start].assigned())
00105 return true;
00106
00107 start = x[start].val();
00108 }
00109 return false;
00110 }
00112 virtual Gecode::Choice* choice(Space&) {
00113 Int::ViewValues<Int::IntView> iv(x[start]);
00114 int n = iv.val();
00115 unsigned int min = x[n].size();
00116 ++iv;
00117
00118 while (iv()) {
00119 if (x[iv.val()].size() < min) {
00120 n = iv.val();
00121 min = x[n].size();
00122 }
00123 ++iv;
00124 }
00125 return new Choice(*this, start, n);
00126 }
00128 virtual Choice* choice(const Space&, Archive& e) {
00129 int pos, val;
00130 e >> pos >> val;
00131 return new Choice(*this, pos, val);
00132 }
00134 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00135 unsigned int a) {
00136 const Choice& c = static_cast<const Choice&>(_c);
00137 if (a == 0)
00138 return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
00139 else
00140 return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
00141 }
00143 virtual void print(const Space&, const Gecode::Choice& _c,
00144 unsigned int a,
00145 std::ostream& o) const {
00146 const Choice& c = static_cast<const Choice&>(_c);
00147 o << "x[" << c.pos << "] "
00148 << ((a == 0) ? "=" : "!=")
00149 << " " << c.val;
00150 }
00152 virtual Actor* copy(Space& home, bool share) {
00153 return new (home) Warnsdorff(home, share, *this);
00154 }
00156 static void post(Home home, const IntVarArgs& x) {
00157 ViewArray<Int::IntView> xv(home, x);
00158 (void) new (home) Warnsdorff(home, xv);
00159 }
00161 virtual size_t dispose(Space&) {
00162 return sizeof(*this);
00163 }
00164 };
00165
00166
00168 class Knights : public Script {
00169 public:
00171 const int n;
00173 IntVarArray succ;
00175 enum {
00176 PROP_REIFIED,
00177 PROP_CIRCUIT
00178 };
00180 enum {
00181 BRANCH_NAIVE,
00182 BRANCH_WARNSDORFF,
00183 };
00185 int f(int x, int y) const {
00186 return x + y*n;
00187 }
00189 int x(int f) const {
00190 return f % n;
00191 }
00193 int y(int f) const {
00194 return f / n;
00195 }
00197 IntSet neighbors(int i) {
00198 static const int moves[8][2] = {
00199 {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
00200 };
00201 int nbs[8]; int n_nbs = 0;
00202 for (int m=0; m<8; m++) {
00203 int nx = x(i) + moves[m][0], ny = y(i) + moves[m][1];
00204 if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n))
00205 nbs[n_nbs++] = f(nx,ny);
00206 }
00207 return IntSet(nbs,n_nbs);
00208 }
00210 Knights(const SizeOptions& opt)
00211 : Script(opt), n(opt.size()), succ(*this,n*n,0,n*n-1) {
00212 switch (opt.branching()) {
00213 case BRANCH_NAIVE:
00214 branch(*this, succ, INT_VAR_NONE(), INT_VAL_MIN());
00215 break;
00216 case BRANCH_WARNSDORFF:
00217 Warnsdorff::post(*this, succ);
00218 break;
00219 }
00220 }
00222 Knights(bool share, Knights& s) : Script(share,s), n(s.n) {
00223 succ.update(*this, share, s.succ);
00224 }
00226 virtual void
00227 print(std::ostream& os) const {
00228 int* jump = new int[n*n];
00229 {
00230 int j=0;
00231 for (int i=0; i<n*n; i++) {
00232 jump[j]=i; j=succ[j].min();
00233 }
00234 }
00235 os << "\t";
00236 for (int i = 0; i < n; i++) {
00237 for (int j = 0; j < n; j++) {
00238 os.width(3);
00239 os << jump[f(i,j)] << " ";
00240 }
00241 os << std::endl << "\t";
00242 }
00243 os << std::endl;
00244 delete [] jump;
00245 }
00246 };
00247
00258 class KnightsReified : public Knights {
00259 public:
00260 KnightsReified(const SizeOptions& opt) : Knights(opt) {
00261 const int nn = n*n;
00262
00263
00264 IntVarArgs jump(nn);
00265 IntVarArgs pred(nn);
00266
00267 for (int i = nn; i--; ) {
00268 IntVar p(*this,0,nn-1); pred[i]=p;
00269 IntVar j(*this,0,nn-1); jump[i]=j;
00270 }
00271
00272
00273 rel(*this, jump[f(0,0)], IRT_EQ, 0);
00274 rel(*this, jump[f(1,2)], IRT_EQ, 1);
00275
00276 distinct(*this, jump, opt.ipl());
00277 channel(*this, succ, pred, opt.ipl());
00278
00279 for (int f = 0; f < nn; f++) {
00280 IntSet ds = neighbors(f);
00281 for (IntSetValues i(ds); i(); ++i)
00282 rel(*this,
00283 expr(*this, (jump[i.val()]-jump[f] == 1)),
00284 BOT_XOR,
00285 expr(*this, (jump[i.val()]-jump[f] == 1-nn)),
00286 expr(*this, (succ[f] == i.val())));
00287 dom(*this, pred[f], ds);
00288 dom(*this, succ[f], ds);
00289 rel(*this, succ[f], IRT_NQ, pred[f]);
00290 }
00291 }
00293 KnightsReified(bool share, KnightsReified& s) : Knights(share,s) {}
00295 virtual Space*
00296 copy(bool share) {
00297 return new KnightsReified(share,*this);
00298 }
00299 };
00300
00311 class KnightsCircuit : public Knights {
00312 public:
00313 KnightsCircuit(const SizeOptions& opt) : Knights(opt) {
00314
00315 rel(*this, succ[0], IRT_EQ, f(1,2));
00316
00317 circuit(*this, succ, opt.ipl());
00318
00319 for (int f = 0; f < n*n; f++)
00320 dom(*this, succ[f], neighbors(f));
00321 }
00323 KnightsCircuit(bool share, KnightsCircuit& s) : Knights(share,s) {}
00325 virtual Space*
00326 copy(bool share) {
00327 return new KnightsCircuit(share,*this);
00328 }
00329 };
00330
00331
00332
00333
00334
00335
00336
00337 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00338
00339 class KnightsInspector : public Gist::Inspector {
00340 protected:
00342 QGraphicsScene* scene;
00344 QMainWindow* mw;
00346 static const int unit = 30;
00347 public:
00349 KnightsInspector(void) : scene(NULL), mw(NULL) {}
00351 virtual void inspect(const Space& s) {
00352 const Knights& k = static_cast<const Knights&>(s);
00353
00354 if (!scene)
00355 initialize();
00356 QList <QGraphicsItem*> itemList = scene->items();
00357 foreach (QGraphicsItem* i, scene->items()) {
00358 scene->removeItem(i);
00359 delete i;
00360 }
00361
00362 for (int i=0; i<k.n; i++) {
00363 for (int j=0; j<k.n; j++) {
00364 scene->addRect(i*unit,j*unit,unit,unit);
00365
00366 QPen pen(Qt::black, 2);
00367 if (!k.succ[i*k.n+j].assigned()) {
00368 pen.setColor(Qt::red);
00369 pen.setStyle(Qt::DotLine);
00370 pen.setWidth(0);
00371 }
00372 for (IntVarValues xv(k.succ[i*k.n+j]); xv(); ++xv) {
00373 int ky = xv.val() % k.n;
00374 int kx = xv.val() / k.n;
00375 scene->addLine(i*unit+unit/2,j*unit+unit/2,
00376 kx*unit+unit/2,ky*unit+unit/2,
00377 pen);
00378 }
00379
00380 }
00381 }
00382 mw->show();
00383 }
00384
00386 void initialize(void) {
00387 mw = new QMainWindow();
00388 scene = new QGraphicsScene();
00389 QGraphicsView* view = new QGraphicsView(scene);
00390 view->setRenderHints(QPainter::Antialiasing);
00391 mw->setCentralWidget(view);
00392 mw->setAttribute(Qt::WA_QuitOnClose, false);
00393 mw->setAttribute(Qt::WA_DeleteOnClose, false);
00394 QAction* closeWindow = new QAction("Close window", mw);
00395 closeWindow->setShortcut(QKeySequence("Ctrl+W"));
00396 mw->connect(closeWindow, SIGNAL(triggered()),
00397 mw, SLOT(close()));
00398 mw->addAction(closeWindow);
00399 }
00400
00402 virtual std::string name(void) { return "Board"; }
00404 virtual void finalize(void) {
00405 delete mw;
00406 mw = NULL;
00407 }
00408 };
00409 #endif
00410
00414 int
00415 main(int argc, char* argv[]) {
00416 SizeOptions opt("Knights");
00417 opt.iterations(100);
00418 opt.size(8);
00419 opt.propagation(Knights::PROP_CIRCUIT);
00420 opt.propagation(Knights::PROP_REIFIED, "reified");
00421 opt.propagation(Knights::PROP_CIRCUIT, "circuit");
00422 opt.branching(Knights::BRANCH_NAIVE);
00423 opt.branching(Knights::BRANCH_NAIVE, "naive");
00424 opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
00425
00426 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00427 KnightsInspector ki;
00428 opt.inspect.click(&ki);
00429 #endif
00430
00431 opt.parse(argc,argv);
00432
00433 if (opt.propagation() == Knights::PROP_REIFIED) {
00434 Script::run<KnightsReified,DFS,SizeOptions>(opt);
00435 } else {
00436 Script::run<KnightsCircuit,DFS,SizeOptions>(opt);
00437 }
00438 return 0;
00439 }
00440
00441
00442