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 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00043 #include <QtGui>
00044 #if QT_VERSION >= 0x050000
00045 #include <QtWidgets>
00046 #endif
00047 #endif
00048
00049 using namespace Gecode;
00050
00060 class Queens : public Script {
00061 public:
00063 IntVarArray q;
00065 enum {
00066 PROP_BINARY,
00067 PROP_MIXED,
00068 PROP_DISTINCT
00069 };
00071 Queens(const SizeOptions& opt)
00072 : Script(opt), q(*this,opt.size(),0,opt.size()-1) {
00073 const int n = q.size();
00074 switch (opt.propagation()) {
00075 case PROP_BINARY:
00076 for (int i = 0; i<n; i++)
00077 for (int j = i+1; j<n; j++) {
00078 rel(*this, q[i] != q[j]);
00079 rel(*this, q[i]+i != q[j]+j);
00080 rel(*this, q[i]-i != q[j]-j);
00081 }
00082 break;
00083 case PROP_MIXED:
00084 for (int i = 0; i<n; i++)
00085 for (int j = i+1; j<n; j++) {
00086 rel(*this, q[i]+i != q[j]+j);
00087 rel(*this, q[i]-i != q[j]-j);
00088 }
00089 distinct(*this, q, opt.ipl());
00090 break;
00091 case PROP_DISTINCT:
00092 distinct(*this, IntArgs::create(n,0,1), q, opt.ipl());
00093 distinct(*this, IntArgs::create(n,0,-1), q, opt.ipl());
00094 distinct(*this, q, opt.ipl());
00095 break;
00096 }
00097 branch(*this, q, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
00098 }
00099
00101 Queens(bool share, Queens& s) : Script(share,s) {
00102 q.update(*this, share, s.q);
00103 }
00104
00106 virtual Space*
00107 copy(bool share) {
00108 return new Queens(share,*this);
00109 }
00110
00112 virtual void
00113 print(std::ostream& os) const {
00114 os << "queens\t";
00115 for (int i = 0; i < q.size(); i++) {
00116 os << q[i] << ", ";
00117 if ((i+1) % 10 == 0)
00118 os << std::endl << "\t";
00119 }
00120 os << std::endl;
00121 }
00122 };
00123
00124 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00125
00126 class QueensInspector : public Gist::Inspector {
00127 protected:
00129 QGraphicsScene* scene;
00131 QMainWindow* mw;
00133 static const int unit = 20;
00134 public:
00136 QueensInspector(void) : scene(NULL), mw(NULL) {}
00138 virtual void inspect(const Space& s) {
00139 const Queens& q = static_cast<const Queens&>(s);
00140
00141 if (!scene)
00142 initialize();
00143 QList <QGraphicsItem*> itemList = scene->items();
00144 foreach (QGraphicsItem* i, scene->items()) {
00145 scene->removeItem(i);
00146 delete i;
00147 }
00148
00149 for (int i=0; i<q.q.size(); i++) {
00150 for (int j=0; j<q.q.size(); j++) {
00151 scene->addRect(i*unit,j*unit,unit,unit);
00152 }
00153 QBrush b(q.q[i].assigned() ? Qt::black : Qt::red);
00154 QPen p(q.q[i].assigned() ? Qt::black : Qt::white);
00155 for (IntVarValues xv(q.q[i]); xv(); ++xv) {
00156 scene->addEllipse(QRectF(i*unit+unit/4,xv.val()*unit+unit/4,
00157 unit/2,unit/2), p, b);
00158 }
00159 }
00160 mw->show();
00161 }
00162
00164 void initialize(void) {
00165 mw = new QMainWindow();
00166 scene = new QGraphicsScene();
00167 QGraphicsView* view = new QGraphicsView(scene);
00168 view->setRenderHints(QPainter::Antialiasing);
00169 mw->setCentralWidget(view);
00170 mw->setAttribute(Qt::WA_QuitOnClose, false);
00171 mw->setAttribute(Qt::WA_DeleteOnClose, false);
00172 QAction* closeWindow = new QAction("Close window", mw);
00173 closeWindow->setShortcut(QKeySequence("Ctrl+W"));
00174 mw->connect(closeWindow, SIGNAL(triggered()),
00175 mw, SLOT(close()));
00176 mw->addAction(closeWindow);
00177 }
00178
00180 virtual std::string name(void) { return "Board"; }
00182 virtual void finalize(void) {
00183 delete mw;
00184 mw = NULL;
00185 }
00186 };
00187
00188 #endif
00189
00193 int
00194 main(int argc, char* argv[]) {
00195 SizeOptions opt("Queens");
00196 opt.iterations(500);
00197 opt.size(100);
00198 opt.propagation(Queens::PROP_DISTINCT);
00199 opt.propagation(Queens::PROP_BINARY, "binary",
00200 "only binary disequality constraints");
00201 opt.propagation(Queens::PROP_MIXED, "mixed",
00202 "single distinct and binary disequality constraints");
00203 opt.propagation(Queens::PROP_DISTINCT, "distinct",
00204 "three distinct constraints");
00205
00206 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00207 QueensInspector ki;
00208 opt.inspect.click(&ki);
00209 #endif
00210
00211 opt.parse(argc,argv);
00212 Script::run<Queens,DFS,SizeOptions>(opt);
00213 return 0;
00214 }
00215
00216
00217