queens.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2001 00008 * 00009 * Last modified: 00010 * $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00011 * $Revision: 11473 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 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 #ifdef 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 /* GECODE_HAS_GIST */ 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 #ifdef 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 // STATISTICS: example-any 00214