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 rel(*this, w[i] == (U || A[i]));
00105
00106 rel(*this, !w[i] || !b[i]);
00107
00108 rel(*this, b[i] == (singleton(i) <= U));
00109 }
00110
00111
00112 linear(*this, w, IRT_EQ, q);
00113 linear(*this, b, IRT_GQ, q);
00114
00115
00116 IntVar unknowns = expr(*this, cardinality(U));
00117 rel(*this, q <= unknowns);
00118 linear(*this, b, IRT_EQ, unknowns);
00119
00120 if (opt.branching() == BRANCH_NAIVE) {
00121 branch(*this, w, INT_VAR_NONE, INT_VAL_MAX);
00122 branch(*this, b, INT_VAR_NONE, INT_VAL_MAX);
00123 } else {
00124 QueenBranch::post(*this);
00125 assign(*this, b, INT_ASSIGN_MAX);
00126 }
00127 }
00129 QueenArmies(bool share, QueenArmies& s)
00130 : MaximizeScript(share,s), n(s.n) {
00131 U.update(*this, share, s.U);
00132 W.update(*this, share, s.W);
00133 w.update(*this, share, s.w);
00134 b.update(*this, share, s.b);
00135 q.update(*this, share, s.q);
00136 }
00138 virtual Space*
00139 copy(bool share) {
00140 return new QueenArmies(share,*this);
00141 }
00143 virtual IntVar cost(void) const {
00144 return q;
00145 }
00147 virtual void
00148 print(std::ostream& os) const {
00149 os << '\t';
00150 for (int i = 0; i < n*n; ++i) {
00151 if (w[i].assigned() && w[i].val()) os << "W";
00152 else if (b[i].assigned() && b[i].val()) os << "B";
00153 else if (!w[i].assigned() && !b[i].assigned()) os << " ";
00154 else os << ".";
00155 if ((i+1)%n == 0) os << std::endl << (i!=(n*n-1)?"\t":"");
00156 }
00157 os << "Number of white queens: " << q << std::endl << std::endl;
00158 }
00159
00167 class QueenBranch : public Brancher {
00168 private:
00170 mutable int start;
00172 class Choice : public Gecode::Choice {
00173 public:
00175 int pos;
00177 bool val;
00181 Choice(const Brancher& b, int pos0, bool val0)
00182 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00184 virtual size_t size(void) const {
00185 return sizeof(Choice);
00186 }
00187 };
00188
00190 QueenBranch(Home home)
00191 : Brancher(home), start(0) {}
00193 QueenBranch(Space& home, bool share, QueenBranch& b)
00194 : Brancher(home, share, b), start(b.start) {}
00195
00196 public:
00198 virtual bool status(const Space& home) const {
00199 const QueenArmies& q = static_cast<const QueenArmies&>(home);
00200 for (int i = start; i < q.n*q.n; ++i)
00201 if (!q.w[i].assigned()) {
00202 start = i;
00203 return true;
00204 }
00205
00206 return false;
00207 }
00209 virtual Gecode::Choice* choice(Space& home) {
00210 const QueenArmies& q = static_cast<const QueenArmies&>(home);
00211 int maxsize = -1;
00212 int pos = -1;
00213
00214 for (int i = start; i < q.n*q.n; ++i) {
00215 if (q.w[i].assigned()) continue;
00216 IntSetRanges ai(A[i]);
00217 SetVarUnknownRanges qU(q.U);
00218 Iter::Ranges::Inter<IntSetRanges, SetVarUnknownRanges> r(ai, qU);
00219 int size = Iter::Ranges::size(r);
00220 if (size > maxsize) {
00221 maxsize = size;
00222 pos = i;
00223 }
00224 }
00225
00226 assert(pos != -1);
00227 return new Choice(*this, pos, true);
00228 }
00232 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00233 unsigned int a) {
00234 QueenArmies& q = static_cast<QueenArmies&>(home);
00235 const Choice& c = static_cast<const Choice&>(_c);
00236 bool val = (a == 0) ? c.val : !c.val;
00237 return me_failed(Int::BoolView(q.w[c.pos]).eq(q, val))
00238 ? ES_FAILED
00239 : ES_OK;
00240 }
00242 virtual Actor* copy(Space& home, bool share) {
00243 return new (home) QueenBranch(home, share, *this);
00244 }
00246 static void post(QueenArmies& home) {
00247 (void) new (home) QueenBranch(home);
00248 }
00250 virtual size_t dispose(Space&) {
00251 return sizeof(*this);
00252 }
00253 };
00254 };
00255
00260 int pos(int i, int j, int n) {
00261 return i*n + j;
00262 }
00263
00267 int
00268 main(int argc, char* argv[]) {
00269 SizeOptions opt("QueenArmies");
00270 opt.size(6);
00271 opt.branching(QueenArmies::BRANCH_SPECIFIC);
00272 opt.branching(QueenArmies::BRANCH_NAIVE, "naive");
00273 opt.branching(QueenArmies::BRANCH_SPECIFIC, "specific");
00274 opt.search(QueenArmies::SEARCH_BAB);
00275 opt.search(QueenArmies::SEARCH_BAB, "bab");
00276 opt.search(QueenArmies::SEARCH_RESTART, "restart");
00277 opt.solutions(0);
00278 opt.parse(argc,argv);
00279
00280
00281
00282 int n = opt.size();
00283 A = new IntSet[n*n];
00284 int *p = new int[std::max(n*n, 25)];
00285 int pn = 0;
00286 for (int i = n; i--; ) {
00287 for (int j = n; j--; ) {
00288 int dir[][2] = {
00289 { 0, 1},
00290 { 1, 1},
00291 { 1, 0},
00292 { 0, -1},
00293 {-1, -1},
00294 {-1, 0},
00295 { 1, -1},
00296 {-1, 1}
00297 };
00298 p[pn++] = pos(i, j, n);
00299 for (int k = 8; k--; ) {
00300 for (int l = 0; l < n
00301 && 0 <= (i+l*dir[k][0]) && (i+l*dir[k][0]) < n
00302 && 0 <= (j+l*dir[k][1]) && (j+l*dir[k][1]) < n; ++l) {
00303 p[pn++] = pos(i+l*dir[k][0], j+l*dir[k][1], n);
00304 }
00305 }
00306
00307 A[pos(i, j, n)] = IntSet(p, pn);
00308
00309 pn = 0;
00310 }
00311 }
00312 delete [] p;
00313
00314
00315 switch (opt.search()) {
00316 case QueenArmies::SEARCH_BAB:
00317 MaximizeScript::run<QueenArmies,BAB,SizeOptions>(opt); break;
00318 case QueenArmies::SEARCH_RESTART:
00319 MaximizeScript::run<QueenArmies,Restart,SizeOptions>(opt); break;
00320 }
00321 return 0;
00322 }
00323
00324