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 IntMaximizeScript(opt),
00089 n(opt.size()),
00090 U(*this, IntSet::empty, IntSet(0, n*n)),
00091 W(*this, IntSet::empty, IntSet(0, n*n)),
00092 w(*this, n*n, 0, 1),
00093 b(*this, n*n, 0, 1),
00094 q(*this, 0, n*n)
00095 {
00096
00097 for (int i = n*n; i--; ) {
00098
00099 rel(*this, w[i] == (U || A[i]));
00100
00101 rel(*this, !w[i] || !b[i]);
00102
00103 rel(*this, b[i] == (singleton(i) <= U));
00104 }
00105
00106
00107 linear(*this, w, IRT_EQ, q);
00108 linear(*this, b, IRT_GQ, q);
00109
00110
00111 IntVar unknowns = expr(*this, cardinality(U));
00112 rel(*this, q <= unknowns);
00113 linear(*this, b, IRT_EQ, unknowns);
00114
00115 if (opt.branching() == BRANCH_NAIVE) {
00116 branch(*this, w, BOOL_VAR_NONE(), BOOL_VAL_MAX());
00117 branch(*this, b, BOOL_VAR_NONE(), BOOL_VAL_MAX());
00118 } else {
00119 QueenBranch::post(*this);
00120 assign(*this, b, BOOL_ASSIGN_MAX());
00121 }
00122 }
00124 QueenArmies(bool share, QueenArmies& s)
00125 : IntMaximizeScript(share,s), n(s.n) {
00126 U.update(*this, share, s.U);
00127 W.update(*this, share, s.W);
00128 w.update(*this, share, s.w);
00129 b.update(*this, share, s.b);
00130 q.update(*this, share, s.q);
00131 }
00133 virtual Space*
00134 copy(bool share) {
00135 return new QueenArmies(share,*this);
00136 }
00138 virtual IntVar cost(void) const {
00139 return q;
00140 }
00142 virtual void
00143 print(std::ostream& os) const {
00144 os << '\t';
00145 for (int i = 0; i < n*n; ++i) {
00146 if (w[i].assigned() && w[i].val()) os << "W";
00147 else if (b[i].assigned() && b[i].val()) os << "B";
00148 else if (!w[i].assigned() && !b[i].assigned()) os << " ";
00149 else os << ".";
00150 if ((i+1)%n == 0) os << std::endl << (i!=(n*n-1)?"\t":"");
00151 }
00152 os << "Number of white queens: " << q << std::endl << std::endl;
00153 }
00154
00162 class QueenBranch : public Brancher {
00163 private:
00165 mutable int start;
00167 class Choice : public Gecode::Choice {
00168 public:
00170 int pos;
00172 bool val;
00176 Choice(const Brancher& b, int pos0, bool val0)
00177 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00179 virtual size_t size(void) const {
00180 return sizeof(Choice);
00181 }
00183 virtual void archive(Archive& e) const {
00184 Gecode::Choice::archive(e);
00185 e << pos << val;
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 }
00230 virtual Choice* choice(const Space&, Archive& e) {
00231 int pos, val;
00232 e >> pos >> val;
00233 return new Choice(*this, pos, val);
00234 }
00238 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00239 unsigned int a) {
00240 QueenArmies& q = static_cast<QueenArmies&>(home);
00241 const Choice& c = static_cast<const Choice&>(_c);
00242 bool val = (a == 0) ? c.val : !c.val;
00243 return me_failed(Int::BoolView(q.w[c.pos]).eq(q, val))
00244 ? ES_FAILED
00245 : ES_OK;
00246 }
00248 virtual void print(const Space&, const Gecode::Choice& _c,
00249 unsigned int a,
00250 std::ostream& o) const {
00251 const Choice& c = static_cast<const Choice&>(_c);
00252 bool val = (a == 0) ? c.val : !c.val;
00253 o << "w[" << c.pos << "] = " << val;
00254 }
00256 virtual Actor* copy(Space& home, bool share) {
00257 return new (home) QueenBranch(home, share, *this);
00258 }
00260 static void post(QueenArmies& home) {
00261 (void) new (home) QueenBranch(home);
00262 }
00264 virtual size_t dispose(Space&) {
00265 return sizeof(*this);
00266 }
00267 };
00268 };
00269
00274 int pos(int i, int j, int n) {
00275 return i*n + j;
00276 }
00277
00281 int
00282 main(int argc, char* argv[]) {
00283 SizeOptions opt("QueenArmies");
00284 opt.size(6);
00285 opt.branching(QueenArmies::BRANCH_SPECIFIC);
00286 opt.branching(QueenArmies::BRANCH_NAIVE, "naive");
00287 opt.branching(QueenArmies::BRANCH_SPECIFIC, "specific");
00288 opt.solutions(0);
00289 opt.parse(argc,argv);
00290
00291
00292
00293 int n = opt.size();
00294 A = new IntSet[n*n];
00295 int *p = new int[std::max(n*n, 25)];
00296 int pn = 0;
00297 for (int i = n; i--; ) {
00298 for (int j = n; j--; ) {
00299 int dir[][2] = {
00300 { 0, 1},
00301 { 1, 1},
00302 { 1, 0},
00303 { 0, -1},
00304 {-1, -1},
00305 {-1, 0},
00306 { 1, -1},
00307 {-1, 1}
00308 };
00309 p[pn++] = pos(i, j, n);
00310 for (int k = 8; k--; ) {
00311 for (int l = 0; l < n
00312 && 0 <= (i+l*dir[k][0]) && (i+l*dir[k][0]) < n
00313 && 0 <= (j+l*dir[k][1]) && (j+l*dir[k][1]) < n; ++l) {
00314 p[pn++] = pos(i+l*dir[k][0], j+l*dir[k][1], n);
00315 }
00316 }
00317
00318 A[pos(i, j, n)] = IntSet(p, pn);
00319
00320 pn = 0;
00321 }
00322 }
00323 delete [] p;
00324
00325 IntMaximizeScript::run<QueenArmies,BAB,SizeOptions>(opt);
00326 return 0;
00327 }
00328
00329