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 IntMaximizeScript {
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 QueenArmies(const SizeOptions& opt) :
00088 n(opt.size()),
00089 U(*this, IntSet::empty, IntSet(0, n*n)),
00090 W(*this, IntSet::empty, IntSet(0, n*n)),
00091 w(*this, n*n, 0, 1),
00092 b(*this, n*n, 0, 1),
00093 q(*this, 0, n*n)
00094 {
00095
00096 for (int i = n*n; i--; ) {
00097
00098 rel(*this, w[i] == (U || A[i]));
00099
00100 rel(*this, !w[i] || !b[i]);
00101
00102 rel(*this, b[i] == (singleton(i) <= U));
00103 }
00104
00105
00106 linear(*this, w, IRT_EQ, q);
00107 linear(*this, b, IRT_GQ, q);
00108
00109
00110 IntVar unknowns = expr(*this, cardinality(U));
00111 rel(*this, q <= unknowns);
00112 linear(*this, b, IRT_EQ, unknowns);
00113
00114 if (opt.branching() == BRANCH_NAIVE) {
00115 branch(*this, w, INT_VAR_NONE(), INT_VAL_MAX());
00116 branch(*this, b, INT_VAR_NONE(), INT_VAL_MAX());
00117 } else {
00118 QueenBranch::post(*this);
00119 assign(*this, b, INT_ASSIGN_MAX());
00120 }
00121 }
00123 QueenArmies(bool share, QueenArmies& s)
00124 : IntMaximizeScript(share,s), n(s.n) {
00125 U.update(*this, share, s.U);
00126 W.update(*this, share, s.W);
00127 w.update(*this, share, s.w);
00128 b.update(*this, share, s.b);
00129 q.update(*this, share, s.q);
00130 }
00132 virtual Space*
00133 copy(bool share) {
00134 return new QueenArmies(share,*this);
00135 }
00137 virtual IntVar cost(void) const {
00138 return q;
00139 }
00141 virtual void
00142 print(std::ostream& os) const {
00143 os << '\t';
00144 for (int i = 0; i < n*n; ++i) {
00145 if (w[i].assigned() && w[i].val()) os << "W";
00146 else if (b[i].assigned() && b[i].val()) os << "B";
00147 else if (!w[i].assigned() && !b[i].assigned()) os << " ";
00148 else os << ".";
00149 if ((i+1)%n == 0) os << std::endl << (i!=(n*n-1)?"\t":"");
00150 }
00151 os << "Number of white queens: " << q << std::endl << std::endl;
00152 }
00153
00161 class QueenBranch : public Brancher {
00162 private:
00164 mutable int start;
00166 class Choice : public Gecode::Choice {
00167 public:
00169 int pos;
00171 bool val;
00175 Choice(const Brancher& b, int pos0, bool val0)
00176 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00178 virtual size_t size(void) const {
00179 return sizeof(Choice);
00180 }
00182 virtual void archive(Archive& e) const {
00183 Gecode::Choice::archive(e);
00184 e << pos << val;
00185 }
00186 };
00187
00189 QueenBranch(Home home)
00190 : Brancher(home), start(0) {}
00192 QueenBranch(Space& home, bool share, QueenBranch& b)
00193 : Brancher(home, share, b), start(b.start) {}
00194
00195 public:
00197 virtual bool status(const Space& home) const {
00198 const QueenArmies& q = static_cast<const QueenArmies&>(home);
00199 for (int i = start; i < q.n*q.n; ++i)
00200 if (!q.w[i].assigned()) {
00201 start = i;
00202 return true;
00203 }
00204
00205 return false;
00206 }
00208 virtual Gecode::Choice* choice(Space& home) {
00209 const QueenArmies& q = static_cast<const QueenArmies&>(home);
00210 int maxsize = -1;
00211 int pos = -1;
00212
00213 for (int i = start; i < q.n*q.n; ++i) {
00214 if (q.w[i].assigned()) continue;
00215 IntSetRanges ai(A[i]);
00216 SetVarUnknownRanges qU(q.U);
00217 Iter::Ranges::Inter<IntSetRanges, SetVarUnknownRanges> r(ai, qU);
00218 int size = Iter::Ranges::size(r);
00219 if (size > maxsize) {
00220 maxsize = size;
00221 pos = i;
00222 }
00223 }
00224
00225 assert(pos != -1);
00226 return new Choice(*this, pos, true);
00227 }
00229 virtual Choice* choice(const Space&, Archive& e) {
00230 int pos, val;
00231 e >> pos >> val;
00232 return new Choice(*this, pos, val);
00233 }
00237 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00238 unsigned int a) {
00239 QueenArmies& q = static_cast<QueenArmies&>(home);
00240 const Choice& c = static_cast<const Choice&>(_c);
00241 bool val = (a == 0) ? c.val : !c.val;
00242 return me_failed(Int::BoolView(q.w[c.pos]).eq(q, val))
00243 ? ES_FAILED
00244 : ES_OK;
00245 }
00247 virtual void print(const Space&, const Gecode::Choice& _c,
00248 unsigned int a,
00249 std::ostream& o) const {
00250 const Choice& c = static_cast<const Choice&>(_c);
00251 bool val = (a == 0) ? c.val : !c.val;
00252 o << "w[" << c.pos << "] = " << val;
00253 }
00255 virtual Actor* copy(Space& home, bool share) {
00256 return new (home) QueenBranch(home, share, *this);
00257 }
00259 static BrancherHandle post(QueenArmies& home) {
00260 return *new (home) QueenBranch(home);
00261 }
00263 virtual size_t dispose(Space&) {
00264 return sizeof(*this);
00265 }
00266 };
00267 };
00268
00273 int pos(int i, int j, int n) {
00274 return i*n + j;
00275 }
00276
00280 int
00281 main(int argc, char* argv[]) {
00282 SizeOptions opt("QueenArmies");
00283 opt.size(6);
00284 opt.branching(QueenArmies::BRANCH_SPECIFIC);
00285 opt.branching(QueenArmies::BRANCH_NAIVE, "naive");
00286 opt.branching(QueenArmies::BRANCH_SPECIFIC, "specific");
00287 opt.solutions(0);
00288 opt.parse(argc,argv);
00289
00290
00291
00292 int n = opt.size();
00293 A = new IntSet[n*n];
00294 int *p = new int[std::max(n*n, 25)];
00295 int pn = 0;
00296 for (int i = n; i--; ) {
00297 for (int j = n; j--; ) {
00298 int dir[][2] = {
00299 { 0, 1},
00300 { 1, 1},
00301 { 1, 0},
00302 { 0, -1},
00303 {-1, -1},
00304 {-1, 0},
00305 { 1, -1},
00306 {-1, 1}
00307 };
00308 p[pn++] = pos(i, j, n);
00309 for (int k = 8; k--; ) {
00310 for (int l = 0; l < n
00311 && 0 <= (i+l*dir[k][0]) && (i+l*dir[k][0]) < n
00312 && 0 <= (j+l*dir[k][1]) && (j+l*dir[k][1]) < n; ++l) {
00313 p[pn++] = pos(i+l*dir[k][0], j+l*dir[k][1], n);
00314 }
00315 }
00316
00317 A[pos(i, j, n)] = IntSet(p, pn);
00318
00319 pn = 0;
00320 }
00321 }
00322 delete [] p;
00323
00324 IntMaximizeScript::run<QueenArmies,BAB,SizeOptions>(opt);
00325 return 0;
00326 }
00327
00328