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 #include <gecode/driver.hh>
00037 #include <gecode/int.hh>
00038 #include <gecode/minimodel.hh>
00039
00040 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00041 #include <QtGui>
00042 #if QT_VERSION >= 0x050000
00043 #include <QtWidgets>
00044 #endif
00045 #endif
00046
00047 using namespace Gecode;
00048
00049
00058 class Warnsdorff : public Brancher {
00059 protected:
00061 ViewArray<Int::IntView> x;
00063 mutable int start;
00065 class Choice : public Gecode::Choice {
00066 public:
00068 int pos;
00070 int val;
00074 Choice(const Brancher& b, int pos0, int val0)
00075 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00077 virtual void archive(Archive& e) const {
00078 Gecode::Choice::archive(e);
00079 e << pos << val;
00080 }
00081 };
00082
00084 Warnsdorff(Home home, ViewArray<Int::IntView>& xv)
00085 : Brancher(home), x(xv), start(0) {}
00087 Warnsdorff(Space& home, Warnsdorff& b)
00088 : Brancher(home, b), start(b.start) {
00089 x.update(home, b.x);
00090 }
00091 public:
00093 virtual bool status(const Space&) const {
00094
00095 for (int n=x.size(); n--; ) {
00096 if (!x[start].assigned())
00097 return true;
00098
00099 start = x[start].val();
00100 }
00101 return false;
00102 }
00104 virtual Gecode::Choice* choice(Space&) {
00105 Int::ViewValues<Int::IntView> iv(x[start]);
00106 int n = iv.val();
00107 unsigned int min = x[n].size();
00108 ++iv;
00109
00110 while (iv()) {
00111 if (x[iv.val()].size() < min) {
00112 n = iv.val();
00113 min = x[n].size();
00114 }
00115 ++iv;
00116 }
00117 return new Choice(*this, start, n);
00118 }
00120 virtual Choice* choice(const Space&, Archive& e) {
00121 int pos, val;
00122 e >> pos >> val;
00123 return new Choice(*this, pos, val);
00124 }
00126 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00127 unsigned int a) {
00128 const Choice& c = static_cast<const Choice&>(_c);
00129 if (a == 0)
00130 return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
00131 else
00132 return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
00133 }
00135 virtual void print(const Space&, const Gecode::Choice& _c,
00136 unsigned int a,
00137 std::ostream& o) const {
00138 const Choice& c = static_cast<const Choice&>(_c);
00139 o << "x[" << c.pos << "] "
00140 << ((a == 0) ? "=" : "!=")
00141 << " " << c.val;
00142 }
00144 virtual Actor* copy(Space& home) {
00145 return new (home) Warnsdorff(home, *this);
00146 }
00148 static void post(Home home, const IntVarArgs& x) {
00149 ViewArray<Int::IntView> xv(home, x);
00150 (void) new (home) Warnsdorff(home, xv);
00151 }
00153 virtual size_t dispose(Space&) {
00154 return sizeof(*this);
00155 }
00156 };
00157
00158
00160 class Knights : public Script {
00161 public:
00163 const int n;
00165 IntVarArray succ;
00167 enum {
00168 PROP_REIFIED,
00169 PROP_CIRCUIT
00170 };
00172 enum {
00173 BRANCH_NAIVE,
00174 BRANCH_WARNSDORFF,
00175 };
00177 int f(int x, int y) const {
00178 return x + y*n;
00179 }
00181 int x(int f) const {
00182 return f % n;
00183 }
00185 int y(int f) const {
00186 return f / n;
00187 }
00189 IntSet neighbors(int i) {
00190 static const int moves[8][2] = {
00191 {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
00192 };
00193 int nbs[8]; int n_nbs = 0;
00194 for (int m=0; m<8; m++) {
00195 int nx = x(i) + moves[m][0], ny = y(i) + moves[m][1];
00196 if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n))
00197 nbs[n_nbs++] = f(nx,ny);
00198 }
00199 return IntSet(nbs,n_nbs);
00200 }
00202 Knights(const SizeOptions& opt)
00203 : Script(opt), n(opt.size()), succ(*this,n*n,0,n*n-1) {
00204 switch (opt.branching()) {
00205 case BRANCH_NAIVE:
00206 branch(*this, succ, INT_VAR_NONE(), INT_VAL_MIN());
00207 break;
00208 case BRANCH_WARNSDORFF:
00209 Warnsdorff::post(*this, succ);
00210 break;
00211 }
00212 }
00214 Knights(Knights& s) : Script(s), n(s.n) {
00215 succ.update(*this, s.succ);
00216 }
00218 virtual void
00219 print(std::ostream& os) const {
00220 int* jump = new int[n*n];
00221 {
00222 int j=0;
00223 for (int i=0; i<n*n; i++) {
00224 jump[j]=i; j=succ[j].min();
00225 }
00226 }
00227 os << "\t";
00228 for (int i = 0; i < n; i++) {
00229 for (int j = 0; j < n; j++) {
00230 os.width(3);
00231 os << jump[f(i,j)] << " ";
00232 }
00233 os << std::endl << "\t";
00234 }
00235 os << std::endl;
00236 delete [] jump;
00237 }
00238 };
00239
00250 class KnightsReified : public Knights {
00251 public:
00252 KnightsReified(const SizeOptions& opt) : Knights(opt) {
00253 const int nn = n*n;
00254
00255
00256 IntVarArgs jump(nn);
00257 IntVarArgs pred(nn);
00258
00259 for (int i = nn; i--; ) {
00260 IntVar p(*this,0,nn-1); pred[i]=p;
00261 IntVar j(*this,0,nn-1); jump[i]=j;
00262 }
00263
00264
00265 rel(*this, jump[f(0,0)], IRT_EQ, 0);
00266 rel(*this, jump[f(1,2)], IRT_EQ, 1);
00267
00268 distinct(*this, jump, opt.ipl());
00269 channel(*this, succ, pred, opt.ipl());
00270
00271 for (int f = 0; f < nn; f++) {
00272 IntSet ds = neighbors(f);
00273 for (IntSetValues i(ds); i(); ++i)
00274 rel(*this,
00275 expr(*this, (jump[i.val()]-jump[f] == 1)),
00276 BOT_XOR,
00277 expr(*this, (jump[i.val()]-jump[f] == 1-nn)),
00278 expr(*this, (succ[f] == i.val())));
00279 dom(*this, pred[f], ds);
00280 dom(*this, succ[f], ds);
00281 rel(*this, succ[f], IRT_NQ, pred[f]);
00282 }
00283 }
00285 KnightsReified(KnightsReified& s) : Knights(s) {}
00287 virtual Space*
00288 copy(void) {
00289 return new KnightsReified(*this);
00290 }
00291 };
00292
00303 class KnightsCircuit : public Knights {
00304 public:
00305 KnightsCircuit(const SizeOptions& opt) : Knights(opt) {
00306
00307 rel(*this, succ[0], IRT_EQ, f(1,2));
00308
00309 circuit(*this, succ, opt.ipl());
00310
00311 for (int f = 0; f < n*n; f++)
00312 dom(*this, succ[f], neighbors(f));
00313 }
00315 KnightsCircuit(KnightsCircuit& s) : Knights(s) {}
00317 virtual Space*
00318 copy(void) {
00319 return new KnightsCircuit(*this);
00320 }
00321 };
00322
00323
00324
00325
00326
00327
00328
00329 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00330
00331 class KnightsInspector : public Gist::Inspector {
00332 protected:
00334 QGraphicsScene* scene;
00336 QMainWindow* mw;
00338 static const int unit = 30;
00339 public:
00341 KnightsInspector(void) : scene(NULL), mw(NULL) {}
00343 virtual void inspect(const Space& s) {
00344 const Knights& k = static_cast<const Knights&>(s);
00345
00346 if (!scene)
00347 initialize();
00348 QList <QGraphicsItem*> itemList = scene->items();
00349 foreach (QGraphicsItem* i, scene->items()) {
00350 scene->removeItem(i);
00351 delete i;
00352 }
00353
00354 for (int i=0; i<k.n; i++) {
00355 for (int j=0; j<k.n; j++) {
00356 scene->addRect(i*unit,j*unit,unit,unit);
00357
00358 QPen pen(Qt::black, 2);
00359 if (!k.succ[i*k.n+j].assigned()) {
00360 pen.setColor(Qt::red);
00361 pen.setStyle(Qt::DotLine);
00362 pen.setWidth(0);
00363 }
00364 for (IntVarValues xv(k.succ[i*k.n+j]); xv(); ++xv) {
00365 int ky = xv.val() % k.n;
00366 int kx = xv.val() / k.n;
00367 scene->addLine(i*unit+unit/2,j*unit+unit/2,
00368 kx*unit+unit/2,ky*unit+unit/2,
00369 pen);
00370 }
00371
00372 }
00373 }
00374 mw->show();
00375 }
00376
00378 void initialize(void) {
00379 mw = new QMainWindow();
00380 scene = new QGraphicsScene();
00381 QGraphicsView* view = new QGraphicsView(scene);
00382 view->setRenderHints(QPainter::Antialiasing);
00383 mw->setCentralWidget(view);
00384 mw->setAttribute(Qt::WA_QuitOnClose, false);
00385 mw->setAttribute(Qt::WA_DeleteOnClose, false);
00386 QAction* closeWindow = new QAction("Close window", mw);
00387 closeWindow->setShortcut(QKeySequence("Ctrl+W"));
00388 mw->connect(closeWindow, SIGNAL(triggered()),
00389 mw, SLOT(close()));
00390 mw->addAction(closeWindow);
00391 }
00392
00394 virtual std::string name(void) { return "Board"; }
00396 virtual void finalize(void) {
00397 delete mw;
00398 mw = NULL;
00399 }
00400 };
00401 #endif
00402
00406 int
00407 main(int argc, char* argv[]) {
00408 SizeOptions opt("Knights");
00409 opt.iterations(100);
00410 opt.size(8);
00411 opt.propagation(Knights::PROP_CIRCUIT);
00412 opt.propagation(Knights::PROP_REIFIED, "reified");
00413 opt.propagation(Knights::PROP_CIRCUIT, "circuit");
00414 opt.branching(Knights::BRANCH_NAIVE);
00415 opt.branching(Knights::BRANCH_NAIVE, "naive");
00416 opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
00417
00418 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00419 KnightsInspector ki;
00420 opt.inspect.click(&ki);
00421 #endif
00422
00423 opt.parse(argc,argv);
00424
00425 if (opt.propagation() == Knights::PROP_REIFIED) {
00426 Script::run<KnightsReified,DFS,SizeOptions>(opt);
00427 } else {
00428 Script::run<KnightsCircuit,DFS,SizeOptions>(opt);
00429 }
00430 return 0;
00431 }
00432
00433
00434