Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
12 kB · 434 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Mikael Lagerkvist <lagerkvist@gecode.org> * Christian Schulte <schulte@gecode.org> * * Copyright: * Mikael Lagerkvist, 2008 * Christian Schulte, 2001 * * This file is part of Gecode, the generic constraint * development environment: * http://www.gecode.org * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */
#include <gecode/driver.hh>#include <gecode/int.hh>#include <gecode/minimodel.hh>
#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)#include <QtGui>#if QT_VERSION >= 0x050000#include <QtWidgets>#endif#endif
using namespace Gecode;
/** \brief Custom brancher for knight's tours using Warnsdorff's rule * * This class implements Warnsdorff's rule for finding knight's * tours. The next position is choosen by taking the jump that * minimizes the number of alternatives in the next step. * * \relates Knights */class Warnsdorff : public Brancher {protected: /// Views of the brancher ViewArray<Int::IntView> x; /// Next variable to branch on mutable int start; /// %Choice class Choice : public Gecode::Choice { public: /// Position of variable int pos; /// Value of variable int val; /** Initialize choice for brancher \a b, position \a pos0, * and value \a val0. */ Choice(const Brancher& b, int pos0, int val0) : Gecode::Choice(b,2), pos(pos0), val(val0) {} /// Archive into \a e virtual void archive(Archive& e) const { Gecode::Choice::archive(e); e << pos << val; } };
/// Construct brancher Warnsdorff(Home home, ViewArray<Int::IntView>& xv) : Brancher(home), x(xv), start(0) {} /// Copy constructor Warnsdorff(Space& home, Warnsdorff& b) : Brancher(home, b), start(b.start) { x.update(home, b.x); }public: /// Check status of brancher, return true if alternatives left virtual bool status(const Space&) const { // A path to follow can be at most x.size() long for (int n=x.size(); n--; ) { if (!x[start].assigned()) return true; // Follow path of assigned variables start = x[start].val(); } return false; } /// Return choice virtual Gecode::Choice* choice(Space&) { Int::ViewValues<Int::IntView> iv(x[start]); int n = iv.val(); unsigned int min = x[n].size(); ++iv; // Choose the value with the fewest neighbors while (iv()) { if (x[iv.val()].size() < min) { n = iv.val(); min = x[n].size(); } ++iv; } return new Choice(*this, start, n); } /// Return choice virtual Choice* choice(const Space&, Archive& e) { int pos, val; e >> pos >> val; return new Choice(*this, pos, val); } /// Perform commit for choice \a _c and alternative \a a virtual ExecStatus commit(Space& home, const Gecode::Choice& _c, unsigned int a) { const Choice& c = static_cast<const Choice&>(_c); if (a == 0) return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK; else return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK; } /// Print explanation virtual void print(const Space&, const Gecode::Choice& _c, unsigned int a, std::ostream& o) const { const Choice& c = static_cast<const Choice&>(_c); o << "x[" << c.pos << "] " << ((a == 0) ? "=" : "!=") << " " << c.val; } /// Copy brancher virtual Actor* copy(Space& home) { return new (home) Warnsdorff(home, *this); } /// Post brancher static void post(Home home, const IntVarArgs& x) { ViewArray<Int::IntView> xv(home, x); (void) new (home) Warnsdorff(home, xv); } /// Delete brancher and return its size virtual size_t dispose(Space&) { return sizeof(*this); }};
/// Base-class for knight's tour exampleclass Knights : public Script {public: /// Size of board const int n; /// Maps board field to successor field IntVarArray succ; /// Propagation to use for model enum { PROP_REIFIED, ///< Use reified constraints PROP_CIRCUIT ///< Use single circuit constraints }; /// Branching to use for model enum { BRANCH_NAIVE, ///< Use naive, lexicographical branching BRANCH_WARNSDORFF, ///< Use Warnsdorff's rule }; /// Return field at position \a x, \a y int f(int x, int y) const { return x + y*n; } /// Return x coordinate at field \a f int x(int f) const { return f % n; } /// Return y coordinate at field \a f int y(int f) const { return f / n; } /// Compute set of neighbour fields IntSet neighbors(int i) { static const int moves[8][2] = { {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1} }; int nbs[8]; int n_nbs = 0; for (int m=0; m<8; m++) { int nx = x(i) + moves[m][0], ny = y(i) + moves[m][1]; if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n)) nbs[n_nbs++] = f(nx,ny); } return IntSet(nbs,n_nbs); } /// Constructor Knights(const SizeOptions& opt) : Script(opt), n(opt.size()), succ(*this,n*n,0,n*n-1) { switch (opt.branching()) { case BRANCH_NAIVE: branch(*this, succ, INT_VAR_NONE(), INT_VAL_MIN()); break; case BRANCH_WARNSDORFF: Warnsdorff::post(*this, succ); break; } } /// Constructor for cloning \a s Knights(Knights& s) : Script(s), n(s.n) { succ.update(*this, s.succ); } /// Print board virtual void print(std::ostream& os) const { int* jump = new int[n*n]; { int j=0; for (int i=0; i<n*n; i++) { jump[j]=i; j=succ[j].min(); } } os << "\t"; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { os.width(3); os << jump[f(i,j)] << " "; } os << std::endl << "\t"; } os << std::endl; delete [] jump; }};
/** * \brief %Example: n-Knight's tour (simple model) * * Fill an n times n chess board with knight's moves such that * the knight does a full tour (last move reaches first move * again). The formulation is due to Gert Smolka. * * \ingroup Example * */class KnightsReified : public Knights {public: KnightsReified(const SizeOptions& opt) : Knights(opt) { const int nn = n*n;
// Map knight to its predecessor of succesor on board IntVarArgs jump(nn); IntVarArgs pred(nn);
for (int i = nn; i--; ) { IntVar p(*this,0,nn-1); pred[i]=p; IntVar j(*this,0,nn-1); jump[i]=j; }
// Place the first two knights rel(*this, jump[f(0,0)], IRT_EQ, 0); rel(*this, jump[f(1,2)], IRT_EQ, 1);
distinct(*this, jump, opt.ipl()); channel(*this, succ, pred, opt.ipl());
for (int f = 0; f < nn; f++) { IntSet ds = neighbors(f); for (IntSetValues i(ds); i(); ++i) rel(*this, expr(*this, (jump[i.val()]-jump[f] == 1)), BOT_XOR, expr(*this, (jump[i.val()]-jump[f] == 1-nn)), expr(*this, (succ[f] == i.val()))); dom(*this, pred[f], ds); dom(*this, succ[f], ds); rel(*this, succ[f], IRT_NQ, pred[f]); } } /// Constructor for cloning \a s KnightsReified(KnightsReified& s) : Knights(s) {} /// Copy during cloning virtual Space* copy(void) { return new KnightsReified(*this); }};
/** * \brief %Example: n-%Knights tour (model using circuit) * * Fill an n times n chess board with knights such that the * knights do a full tour by knights move (last knight reaches * first knight again). * * \ingroup Example * */class KnightsCircuit : public Knights {public: KnightsCircuit(const SizeOptions& opt) : Knights(opt) { // Fix the first move rel(*this, succ[0], IRT_EQ, f(1,2));
circuit(*this, succ, opt.ipl());
for (int f = 0; f < n*n; f++) dom(*this, succ[f], neighbors(f)); } /// Constructor for cloning \a s KnightsCircuit(KnightsCircuit& s) : Knights(s) {} /// Copy during cloning virtual Space* copy(void) { return new KnightsCircuit(*this); }};
/* * Just to fool some scripts: * \brief %Example: n-Knight's tour * */
#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)/// Inspector showing knight moves on a chess boardclass KnightsInspector : public Gist::Inspector {protected: /// The graphics scene displaying the board QGraphicsScene* scene; /// The window containing the graphics scene QMainWindow* mw; /// The size of a field on the board static const int unit = 30;public: /// Constructor KnightsInspector(void) : scene(nullptr), mw(nullptr) {} /// Inspect space \a s virtual void inspect(const Space& s) { const Knights& k = static_cast<const Knights&>(s);
if (!scene) initialize(); QList <QGraphicsItem*> itemList = scene->items(); foreach (QGraphicsItem* i, scene->items()) { scene->removeItem(i); delete i; }
for (int i=0; i<k.n; i++) { for (int j=0; j<k.n; j++) { scene->addRect(i*unit,j*unit,unit,unit);
QPen pen(Qt::black, 2); if (!k.succ[i*k.n+j].assigned()) { pen.setColor(Qt::red); pen.setStyle(Qt::DotLine); pen.setWidth(0); } for (IntVarValues xv(k.succ[i*k.n+j]); xv(); ++xv) { int ky = xv.val() % k.n; int kx = xv.val() / k.n; scene->addLine(i*unit+unit/2,j*unit+unit/2, kx*unit+unit/2,ky*unit+unit/2, pen); }
} } mw->show(); }
/// Set up main window void initialize(void) { mw = new QMainWindow(); scene = new QGraphicsScene(); QGraphicsView* view = new QGraphicsView(scene); view->setRenderHints(QPainter::Antialiasing); mw->setCentralWidget(view); mw->setAttribute(Qt::WA_QuitOnClose, false); mw->setAttribute(Qt::WA_DeleteOnClose, false); QAction* closeWindow = new QAction("Close window", mw); closeWindow->setShortcut(QKeySequence("Ctrl+W")); mw->connect(closeWindow, SIGNAL(triggered()), mw, SLOT(close())); mw->addAction(closeWindow); }
/// Name of the inspector virtual std::string name(void) { return "Board"; } /// Finalize inspector virtual void finalize(void) { delete mw; mw = nullptr; }};#endif
/** \brief Main-function * \relates Knights */intmain(int argc, char* argv[]) { SizeOptions opt("Knights"); opt.iterations(100); opt.size(8); opt.propagation(Knights::PROP_CIRCUIT); opt.propagation(Knights::PROP_REIFIED, "reified"); opt.propagation(Knights::PROP_CIRCUIT, "circuit"); opt.branching(Knights::BRANCH_NAIVE); opt.branching(Knights::BRANCH_NAIVE, "naive"); opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
#if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST) KnightsInspector ki; opt.inspect.click(&ki);#endif
opt.parse(argc,argv);
if (opt.propagation() == Knights::PROP_REIFIED) { Script::run<KnightsReified,DFS,SizeOptions>(opt); } else { Script::run<KnightsCircuit,DFS,SizeOptions>(opt); } return 0;}
// STATISTICS: example-any