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 * Last modified: 00010 * $Date: 2010-05-08 19:24:20 +0200 (Sat, 08 May 2010) $ by $Author: tack $ 00011 * $Revision: 10910 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 // Basic rules of the model 00102 for (int i = n*n; i--; ) { 00103 // w[i] means that no blacks are allowed on A[i] 00104 rel(*this, w[i] == (U || A[i])); 00105 // Make sure blacks and whites are disjoint. 00106 rel(*this, !w[i] || !b[i]); 00107 // If i in U, then b[i] has a piece. 00108 rel(*this, b[i] == (singleton(i) <= U)); 00109 } 00110 00111 // Connect optimization variable to number of pieces 00112 linear(*this, w, IRT_EQ, q); 00113 linear(*this, b, IRT_GQ, q); 00114 00115 // Connect cardinality of U to the number of black pieces. 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 // No non-assigned orders left 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 // Set up the A-sets 00281 // A[i] will contain the values attacked by a queen at position i 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 // STATISTICS: example-any