Generated on Fri Oct 19 11:24:49 2018 for Gecode by doxygen 1.6.3

queen-armies.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Mikael Lagerkvist, 2006
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 
00035 #include <gecode/driver.hh>
00036 #include <gecode/int.hh>
00037 #include <gecode/minimodel.hh>
00038 #include <gecode/set.hh>
00039 
00040 using namespace Gecode;
00041 
00046 IntSet* A;
00047 
00067 class QueenArmies : public IntMaximizeScript {
00068 public:
00069   const int n;
00070   SetVar U, 
00071     W; 
00072   BoolVarArray w, 
00073     b; 
00074   IntVar q; 
00075 
00077   enum {
00078     BRANCH_NAIVE,   
00079     BRANCH_SPECIFIC 
00080   };
00081 
00083   QueenArmies(const SizeOptions& opt) :
00084     IntMaximizeScript(opt),
00085     n(opt.size()),
00086     U(*this, IntSet::empty, IntSet(0, n*n)),
00087     W(*this, IntSet::empty, IntSet(0, n*n)),
00088     w(*this, n*n, 0, 1),
00089     b(*this, n*n, 0, 1),
00090     q(*this, 0, n*n)
00091   {
00092     // Basic rules of the model
00093     for (int i = n*n; i--; ) {
00094       // w[i] means that no blacks are allowed on A[i]
00095       rel(*this, w[i] == (U || A[i]));
00096       // Make sure blacks and whites are disjoint.
00097       rel(*this, !w[i] || !b[i]);
00098       // If i in U, then b[i] has a piece.
00099       rel(*this, b[i] == (singleton(i) <= U));
00100     }
00101 
00102     // Connect optimization variable to number of pieces
00103     linear(*this, w, IRT_EQ, q);
00104     linear(*this, b, IRT_GQ, q);
00105 
00106     // Connect cardinality of U to the number of black pieces.
00107     IntVar unknowns = expr(*this, cardinality(U));
00108     rel(*this, q <= unknowns);
00109     linear(*this, b, IRT_EQ, unknowns);
00110 
00111     if (opt.branching() == BRANCH_NAIVE) {
00112       branch(*this, w, BOOL_VAR_NONE(), BOOL_VAL_MAX());
00113       branch(*this, b, BOOL_VAR_NONE(), BOOL_VAL_MAX());
00114     } else {
00115       QueenBranch::post(*this);
00116       assign(*this, b, BOOL_ASSIGN_MAX());
00117     }
00118   }
00120   QueenArmies(QueenArmies& s)
00121     : IntMaximizeScript(s), n(s.n) {
00122     U.update(*this, s.U);
00123     W.update(*this, s.W);
00124     w.update(*this, s.w);
00125     b.update(*this, s.b);
00126     q.update(*this, s.q);
00127   }
00129   virtual Space*
00130   copy(void) {
00131     return new QueenArmies(*this);
00132   }
00134   virtual IntVar cost(void) const {
00135     return q;
00136   }
00138   virtual void
00139   print(std::ostream& os) const {
00140     os << '\t';
00141     for (int i = 0; i < n*n; ++i) {
00142       if (w[i].assigned() && w[i].val()) os << "W";
00143       else if (b[i].assigned() && b[i].val()) os << "B";
00144       else if (!w[i].assigned() && !b[i].assigned()) os << " ";
00145       else os << ".";
00146       if ((i+1)%n == 0) os << std::endl << (i!=(n*n-1)?"\t":"");
00147     }
00148     os << "Number of white queens: " << q << std::endl << std::endl;
00149   }
00150 
00158   class QueenBranch : public Brancher {
00159   private:
00161     mutable int start;
00163     class Choice : public Gecode::Choice {
00164     public:
00166       int pos;
00168       bool val;
00172       Choice(const Brancher& b, int pos0, bool val0)
00173         : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00175       virtual void archive(Archive& e) const {
00176         Gecode::Choice::archive(e);
00177         e << pos << val;
00178       }
00179     };
00180 
00182     QueenBranch(Home home)
00183       : Brancher(home), start(0) {}
00185     QueenBranch(Space& home, QueenBranch& b)
00186       : Brancher(home, b), start(b.start) {}
00187 
00188   public:
00190     virtual bool status(const Space& home) const {
00191       const QueenArmies& q = static_cast<const QueenArmies&>(home);
00192       for (int i = start; i < q.n*q.n; ++i)
00193         if (!q.w[i].assigned()) {
00194           start = i;
00195           return true;
00196         }
00197       // No non-assigned orders left
00198       return false;
00199     }
00201     virtual Gecode::Choice* choice(Space& home) {
00202       const QueenArmies& q = static_cast<const QueenArmies&>(home);
00203       int maxsize = -1;
00204       int pos = -1;
00205 
00206       for (int i = start; i < q.n*q.n; ++i) {
00207         if (q.w[i].assigned()) continue;
00208         IntSetRanges ai(A[i]);
00209         SetVarUnknownRanges qU(q.U);
00210         Iter::Ranges::Inter<IntSetRanges, SetVarUnknownRanges> r(ai, qU);
00211         int size = Iter::Ranges::size(r);
00212         if (size > maxsize) {
00213           maxsize = size;
00214           pos = i;
00215         }
00216       }
00217 
00218       assert(pos != -1);
00219       return new Choice(*this, pos, true);
00220     }
00222     virtual Choice* choice(const Space&, Archive& e) {
00223       int pos, val;
00224       e >> pos >> val;
00225       return new Choice(*this, pos, val);
00226     }
00230     virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00231                               unsigned int a) {
00232       QueenArmies& q = static_cast<QueenArmies&>(home);
00233       const Choice& c = static_cast<const Choice&>(_c);
00234       bool val = (a == 0) ? c.val : !c.val;
00235       return me_failed(Int::BoolView(q.w[c.pos]).eq(q, val))
00236         ? ES_FAILED
00237         : ES_OK;
00238     }
00240     virtual void print(const Space&, const Gecode::Choice& _c,
00241                        unsigned int a,
00242                        std::ostream& o) const {
00243       const Choice& c = static_cast<const Choice&>(_c);
00244       bool val = (a == 0) ? c.val : !c.val;
00245       o << "w[" << c.pos << "] = " << val;
00246     }
00248     virtual Actor* copy(Space& home) {
00249       return new (home) QueenBranch(home, *this);
00250     }
00252     static void post(QueenArmies& home) {
00253       (void) new (home) QueenBranch(home);
00254     }
00256     virtual size_t dispose(Space&) {
00257       return sizeof(*this);
00258     }
00259   };
00260 };
00261 
00266 int pos(int i, int j, int n) {
00267   return i*n + j;
00268 }
00269 
00273 int
00274 main(int argc, char* argv[]) {
00275   SizeOptions opt("QueenArmies");
00276   opt.size(6);
00277   opt.branching(QueenArmies::BRANCH_SPECIFIC);
00278   opt.branching(QueenArmies::BRANCH_NAIVE, "naive");
00279   opt.branching(QueenArmies::BRANCH_SPECIFIC, "specific");
00280   opt.solutions(0);
00281   opt.parse(argc,argv);
00282 
00283   // Set up the A-sets
00284   // A[i] will contain the values attacked by a queen at position i
00285   int n = opt.size();
00286   A = new IntSet[n*n];
00287   int *p = new int[std::max(n*n, 25)];
00288   int pn = 0;
00289   for (int i = n; i--; ) {
00290     for (int j = n; j--; ) {
00291       int dir[][2] = {
00292         { 0,  1},
00293         { 1,  1},
00294         { 1,  0},
00295         { 0, -1},
00296         {-1, -1},
00297         {-1,  0},
00298         { 1, -1},
00299         {-1,  1}
00300       };
00301       p[pn++] = pos(i, j, n);
00302       for (int k = 8; k--; ) {
00303         for (int l = 0; l < n
00304                && 0 <= (i+l*dir[k][0]) && (i+l*dir[k][0]) < n
00305                && 0 <= (j+l*dir[k][1]) && (j+l*dir[k][1]) < n; ++l) {
00306           p[pn++] = pos(i+l*dir[k][0], j+l*dir[k][1], n);
00307         }
00308       }
00309 
00310       A[pos(i, j, n)] = IntSet(p, pn);
00311 
00312       pn = 0;
00313     }
00314   }
00315   delete [] p;
00316 
00317   IntMaximizeScript::run<QueenArmies,BAB,SizeOptions>(opt);
00318   return 0;
00319 }
00320 
00321 // STATISTICS: example-any