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 #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 rel(*this, q[i] != q[j]);
00076 rel(*this, q[i]+i != q[j]+j);
00077 rel(*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 rel(*this, q[i]+i != q[j]+j);
00084 rel(*this, q[i]-i != q[j]-j);
00085 }
00086 distinct(*this, q, opt.icl());
00087 break;
00088 case PROP_DISTINCT:
00089 distinct(*this, IntArgs::create(n,0,1), q, opt.icl());
00090 distinct(*this, IntArgs::create(n,0,-1), q, opt.icl());
00091 distinct(*this, q, opt.icl());
00092 break;
00093 }
00094 branch(*this, q, INT_VAR_SIZE_MIN, INT_VAL_MIN);
00095 }
00096
00098 Queens(bool share, Queens& s) : Script(share,s) {
00099 q.update(*this, share, s.q);
00100 }
00101
00103 virtual Space*
00104 copy(bool share) {
00105 return new Queens(share,*this);
00106 }
00107
00109 virtual void
00110 print(std::ostream& os) const {
00111 os << "queens\t";
00112 for (int i = 0; i < q.size(); i++) {
00113 os << q[i] << ", ";
00114 if ((i+1) % 10 == 0)
00115 os << std::endl << "\t";
00116 }
00117 os << std::endl;
00118 }
00119 };
00120
00121 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00122
00123 class QueensInspector : public Gist::Inspector {
00124 protected:
00126 QGraphicsScene* scene;
00128 QMainWindow* mw;
00130 static const int unit = 20;
00131 public:
00133 QueensInspector(void) : scene(NULL), mw(NULL) {}
00135 virtual void inspect(const Space& s) {
00136 const Queens& q = static_cast<const Queens&>(s);
00137
00138 if (!scene)
00139 initialize();
00140 QList <QGraphicsItem*> itemList = scene->items();
00141 foreach (QGraphicsItem* i, scene->items()) {
00142 scene->removeItem(i);
00143 delete i;
00144 }
00145
00146 for (int i=0; i<q.q.size(); i++) {
00147 for (int j=0; j<q.q.size(); j++) {
00148 scene->addRect(i*unit,j*unit,unit,unit);
00149 }
00150 QBrush b(q.q[i].assigned() ? Qt::black : Qt::red);
00151 QPen p(q.q[i].assigned() ? Qt::black : Qt::white);
00152 for (IntVarValues xv(q.q[i]); xv(); ++xv) {
00153 scene->addEllipse(QRectF(i*unit+unit/4,xv.val()*unit+unit/4,
00154 unit/2,unit/2), p, b);
00155 }
00156 }
00157 mw->show();
00158 }
00159
00161 void initialize(void) {
00162 mw = new QMainWindow();
00163 scene = new QGraphicsScene();
00164 QGraphicsView* view = new QGraphicsView(scene);
00165 view->setRenderHints(QPainter::Antialiasing);
00166 mw->setCentralWidget(view);
00167 mw->setAttribute(Qt::WA_QuitOnClose, false);
00168 mw->setAttribute(Qt::WA_DeleteOnClose, false);
00169 QAction* closeWindow = new QAction("Close window", mw);
00170 closeWindow->setShortcut(QKeySequence("Ctrl+W"));
00171 mw->connect(closeWindow, SIGNAL(triggered()),
00172 mw, SLOT(close()));
00173 mw->addAction(closeWindow);
00174 }
00175
00177 virtual std::string name(void) { return "Board"; }
00179 virtual void finalize(void) {
00180 delete mw;
00181 mw = NULL;
00182 }
00183 };
00184
00185 #endif
00186
00190 int
00191 main(int argc, char* argv[]) {
00192 SizeOptions opt("Queens");
00193 opt.iterations(500);
00194 opt.size(100);
00195 opt.propagation(Queens::PROP_DISTINCT);
00196 opt.propagation(Queens::PROP_BINARY, "binary",
00197 "only binary disequality constraints");
00198 opt.propagation(Queens::PROP_MIXED, "mixed",
00199 "single distinct and binary disequality constraints");
00200 opt.propagation(Queens::PROP_DISTINCT, "distinct",
00201 "three distinct constraints");
00202
00203 #if defined(GECODE_HAS_QT) && defined(GECODE_HAS_GIST)
00204 QueensInspector ki;
00205 opt.inspect.click(&ki);
00206 #endif
00207
00208 opt.parse(argc,argv);
00209 Script::run<Queens,DFS,SizeOptions>(opt);
00210 return 0;
00211 }
00212
00213
00214