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
00039 #include <gecode/driver.hh>
00040 #include <gecode/int.hh>
00041 #include <gecode/minimodel.hh>
00042 #include <gecode/set.hh>
00043
00044 using namespace Gecode;
00045
00050 IntSet* A;
00051
00071 class QueenArmies : public MaximizeScript {
00072 public:
00073 const int n;
00074 SetVar U,
00075 W;
00076 BoolVarArray w,
00077 b;
00078 IntVar q;
00079
00081 enum {
00082 BRANCH_NAIVE,
00083 BRANCH_SPECIFIC
00084 };
00085
00087 enum {
00088 SEARCH_BAB,
00089 SEARCH_RESTART
00090 };
00091
00093 QueenArmies(const SizeOptions& opt) :
00094 n(opt.size()),
00095 U(*this, IntSet::empty, IntSet(0, n*n)),
00096 W(*this, IntSet::empty, IntSet(0, n*n)),
00097 w(*this, n*n, 0, 1),
00098 b(*this, n*n, 0, 1),
00099 q(*this, 0, n*n)
00100 {
00101
00102 for (int i = n*n; i--; ) {
00103
00104 dom(*this, U, SRT_DISJ, A[i], w[i]);
00105
00106 post(*this, tt(!w[i] || !b[i]));
00107
00108 dom(*this, U, SRT_SUP, i, b[i]);
00109 }
00110
00111
00112 linear(*this, w, IRT_EQ, q);
00113 linear(*this, b, IRT_GQ, q);
00114
00115
00116 IntVar unknowns(*this, 0, n*n);
00117 cardinality(*this, U, unknowns);
00118 post(*this, q <= unknowns);
00119 linear(*this, b, IRT_EQ, unknowns);
00120
00121 if (opt.branching() == BRANCH_NAIVE) {
00122 branch(*this, w, INT_VAR_NONE, INT_VAL_MAX);
00123 branch(*this, b, INT_VAR_NONE, INT_VAL_MAX);
00124 } else {
00125 QueenBranch::post(*this);
00126 assign(*this, b, INT_ASSIGN_MAX);
00127 }
00128 }
00130 QueenArmies(bool share, QueenArmies& s)
00131 : MaximizeScript(share,s), n(s.n) {
00132 U.update(*this, share, s.U);
00133 W.update(*this, share, s.W);
00134 w.update(*this, share, s.w);
00135 b.update(*this, share, s.b);
00136 q.update(*this, share, s.q);
00137 }
00139 virtual Space*
00140 copy(bool share) {
00141 return new QueenArmies(share,*this);
00142 }
00144 virtual IntVar cost(void) const {
00145 return q;
00146 }
00148 virtual void
00149 print(std::ostream& os) const {
00150 os << '\t';
00151 for (int i = 0; i < n*n; ++i) {
00152 if (w[i].assigned() && w[i].val()) os << "W";
00153 else if (b[i].assigned() && b[i].val()) os << "B";
00154 else if (!w[i].assigned() && !b[i].assigned()) os << " ";
00155 else os << ".";
00156 if ((i+1)%n == 0) os << std::endl << (i!=(n*n-1)?"\t":"");
00157 }
00158 os << "Number of white queens: " << q << std::endl << std::endl;
00159 }
00160
00168 class QueenBranch : Brancher {
00169 private:
00171 mutable int start;
00173 class Choice : public Gecode::Choice {
00174 public:
00176 int pos;
00178 bool val;
00182 Choice(const Brancher& b, int pos0, bool val0)
00183 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00185 virtual size_t size(void) const {
00186 return sizeof(Choice);
00187 }
00188 };
00189
00191 QueenBranch(Home home)
00192 : Brancher(home), start(0) {}
00194 QueenBranch(Space& home, bool share, QueenBranch& b)
00195 : Brancher(home, share, b), start(b.start) {}
00196
00197 public:
00199 virtual bool status(const Space& home) const {
00200 const QueenArmies& q = static_cast<const QueenArmies&>(home);
00201 for (int i = start; i < q.n*q.n; ++i)
00202 if (!q.w[i].assigned()) {
00203 start = i;
00204 return true;
00205 }
00206
00207 return false;
00208 }
00210 virtual Gecode::Choice* choice(Space& home) {
00211 const QueenArmies& q = static_cast<const QueenArmies&>(home);
00212 int maxsize = -1;
00213 int pos = -1;
00214
00215 for (int i = start; i < q.n*q.n; ++i) {
00216 if (q.w[i].assigned()) continue;
00217 IntSetRanges ai(A[i]);
00218 SetVarUnknownRanges qU(q.U);
00219 Iter::Ranges::Inter<IntSetRanges, SetVarUnknownRanges> r(ai, qU);
00220 int size = Iter::Ranges::size(r);
00221 if (size > maxsize) {
00222 maxsize = size;
00223 pos = i;
00224 }
00225 }
00226
00227 assert(pos != -1);
00228 return new Choice(*this, pos, true);
00229 }
00233 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00234 unsigned int a) {
00235 QueenArmies& q = static_cast<QueenArmies&>(home);
00236 const Choice& c = static_cast<const Choice&>(_c);
00237 bool val = (a == 0) ? c.val : !c.val;
00238 return me_failed(Int::BoolView(q.w[c.pos]).eq(q, val))
00239 ? ES_FAILED
00240 : ES_OK;
00241 }
00243 virtual Actor* copy(Space& home, bool share) {
00244 return new (home) QueenBranch(home, share, *this);
00245 }
00247 static void post(QueenArmies& home) {
00248 (void) new (home) QueenBranch(home);
00249 }
00251 virtual size_t dispose(Space&) {
00252 return sizeof(*this);
00253 }
00254 };
00255 };
00256
00261 int pos(int i, int j, int n) {
00262 return i*n + j;
00263 }
00264
00268 int
00269 main(int argc, char* argv[]) {
00270 SizeOptions opt("QueenArmies");
00271 opt.size(6);
00272 opt.branching(QueenArmies::BRANCH_SPECIFIC);
00273 opt.branching(QueenArmies::BRANCH_NAIVE, "naive");
00274 opt.branching(QueenArmies::BRANCH_SPECIFIC, "specific");
00275 opt.search(QueenArmies::SEARCH_BAB);
00276 opt.search(QueenArmies::SEARCH_BAB, "bab");
00277 opt.search(QueenArmies::SEARCH_RESTART, "restart");
00278 opt.solutions(0);
00279 opt.parse(argc,argv);
00280
00281
00282
00283 int n = opt.size();
00284 A = new IntSet[n*n];
00285 int *p = new int[std::max(n*n, 25)];
00286 int pn = 0;
00287 for (int i = n; i--; ) {
00288 for (int j = n; j--; ) {
00289 int dir[][2] = {
00290 { 0, 1},
00291 { 1, 1},
00292 { 1, 0},
00293 { 0, -1},
00294 {-1, -1},
00295 {-1, 0},
00296 { 1, -1},
00297 {-1, 1}
00298 };
00299 p[pn++] = pos(i, j, n);
00300 for (int k = 8; k--; ) {
00301 for (int l = 0; l < n
00302 && 0 <= (i+l*dir[k][0]) && (i+l*dir[k][0]) < n
00303 && 0 <= (j+l*dir[k][1]) && (j+l*dir[k][1]) < n; ++l) {
00304 p[pn++] = pos(i+l*dir[k][0], j+l*dir[k][1], n);
00305 }
00306 }
00307
00308 A[pos(i, j, n)] = IntSet(p, pn);
00309
00310 pn = 0;
00311 }
00312 }
00313 delete [] p;
00314
00315
00316 switch (opt.search()) {
00317 case QueenArmies::SEARCH_BAB:
00318 MaximizeScript::run<QueenArmies,BAB,SizeOptions>(opt); break;
00319 case QueenArmies::SEARCH_RESTART:
00320 MaximizeScript::run<QueenArmies,Restart,SizeOptions>(opt); break;
00321 }
00322 return 0;
00323 }
00324
00325