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