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