crowded-chess.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * Mikael Lagerkvist <lagerkvist@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2001 00009 * Mikael Lagerkvist, 2005 00010 * 00011 * Last modified: 00012 * $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00013 * $Revision: 11473 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 #include <gecode/driver.hh> 00041 #include <gecode/int.hh> 00042 #include <gecode/minimodel.hh> 00043 00044 using namespace Gecode; 00045 00050 const int kval[] = { 00051 0, 0, 0, 0, 5, 00052 9, 15, 21, 29, 37, 00053 47, 57, 69, 81, 94, 00054 109 00055 }; 00056 00057 namespace { 00061 TupleSet bishops; 00065 class Bishops : public Space { 00066 public: 00067 const int n; 00068 BoolVarArray k; 00069 bool valid_pos(int i, int j) { 00070 return (i >= 0 && i < n) && (j >= 0 && j < n); 00071 } 00072 Bishops(int size) 00073 : n(size), k(*this,n*n,0,1) { 00074 Matrix<BoolVarArray> kb(k, n, n); 00075 for (int l = n; l--; ) { 00076 const int il = (n-1) - l; 00077 BoolVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1); 00078 for (int i = 0; i <= l; ++i) { 00079 d1[i] = kb(i+il, i); 00080 d2[i] = kb(i, i+il); 00081 d3[i] = kb((n-1)-i-il, i); 00082 d4[i] = kb((n-1)-i, i+il); 00083 } 00084 00085 linear(*this, d1, IRT_LQ, 1); 00086 linear(*this, d2, IRT_LQ, 1); 00087 linear(*this, d3, IRT_LQ, 1); 00088 linear(*this, d4, IRT_LQ, 1); 00089 } 00090 00091 linear(*this, k, IRT_EQ, 2*n - 2); 00092 // Forced bishop placement from crowded chess model 00093 rel(*this, kb(n-1, 0), IRT_EQ, 1); 00094 rel(*this, kb(n-1, n-1), IRT_EQ, 1); 00095 branch(*this, k, 00096 tiebreak(INT_VAR_DEGREE_MAX,INT_VAR_SIZE_MIN), INT_VAL_MAX); 00097 } 00098 Bishops(bool share, Bishops& s) : Space(share,s), n(s.n) { 00099 k.update(*this, share, s.k); 00100 } 00101 virtual Space* copy(bool share) { 00102 return new Bishops(share,*this); 00103 } 00104 }; 00108 void init_bishops(int size) { 00109 Bishops* prob = new Bishops(size); 00110 DFS<Bishops> e(prob); IntArgs ia(size*size); 00111 delete prob; 00112 00113 while (Bishops* s = e.next()) { 00114 for (int i = size*size; i--; ) 00115 ia[i] = s->k[i].val(); 00116 bishops.add(ia); 00117 delete s; 00118 } 00119 00120 bishops.finalize(); 00121 } 00122 } 00187 class CrowdedChess : public Script { 00188 protected: 00189 const int n; 00190 IntVarArray s; 00191 IntVarArray queens, 00192 rooks; 00193 BoolVarArray knights; 00194 00198 enum 00199 {Q, 00200 R, 00201 B, 00202 K, 00203 E, 00204 PMAX 00205 } piece; 00206 00207 // Is (i,j) a valid position on the board? 00208 bool valid_pos(int i, int j) { 00209 return (i >= 0 && i < n) && 00210 (j >= 0 && j < n); 00211 } 00212 00214 void knight_constraints(void) { 00215 static const int kmoves[4][2] = { 00216 {-1,2}, {1,2}, {2,-1}, {2,1} 00217 }; 00218 Matrix<BoolVarArray> kb(knights, n, n); 00219 for (int x = n; x--; ) 00220 for (int y = n; y--; ) 00221 for (int i = 4; i--; ) 00222 if (valid_pos(x+kmoves[i][0], y+kmoves[i][1])) 00223 rel(*this, 00224 kb(x, y), 00225 BOT_AND, 00226 kb(x+kmoves[i][0], y+kmoves[i][1]), 00227 0); 00228 } 00229 00230 00231 public: 00232 enum { 00233 PROP_TUPLE_SET, 00234 PROP_DECOMPOSE 00235 }; 00236 00238 CrowdedChess(const SizeOptions& opt) 00239 : n(opt.size()), 00240 s(*this, n*n, 0, PMAX-1), 00241 queens(*this, n, 0, n-1), 00242 rooks(*this, n, 0, n-1), 00243 knights(*this, n*n, 0, 1) { 00244 const int nkval = sizeof(kval)/sizeof(int); 00245 const int nn = n*n, q = n, r = n, b = (2*n)-2, 00246 k = n <= nkval ? kval[n-1] : kval[nkval-1]; 00247 const int e = nn - (q + r + b + k); 00248 00249 assert(nn == (e + q + r + b + k)); 00250 00251 Matrix<IntVarArray> m(s, n); 00252 00253 // *********************** 00254 // Basic model 00255 // *********************** 00256 00257 count(*this, s, E, IRT_EQ, e, opt.icl()); 00258 count(*this, s, Q, IRT_EQ, q, opt.icl()); 00259 count(*this, s, R, IRT_EQ, r, opt.icl()); 00260 count(*this, s, B, IRT_EQ, b, opt.icl()); 00261 count(*this, s, K, IRT_EQ, k, opt.icl()); 00262 00263 // Collect rows and columns for handling rooks and queens 00264 for (int i = 0; i < n; ++i) { 00265 IntVarArgs aa = m.row(i), bb = m.col(i); 00266 00267 count(*this, aa, Q, IRT_EQ, 1, opt.icl()); 00268 count(*this, bb, Q, IRT_EQ, 1, opt.icl()); 00269 count(*this, aa, R, IRT_EQ, 1, opt.icl()); 00270 count(*this, bb, R, IRT_EQ, 1, opt.icl()); 00271 00272 // Connect (queens|rooks)[i] to the row it is in 00273 element(*this, aa, queens[i], Q, ICL_DOM); 00274 element(*this, aa, rooks[i], R, ICL_DOM); 00275 } 00276 00277 // N-queens constraints 00278 distinct(*this, queens, ICL_DOM); 00279 distinct(*this, IntArgs::create(n,0,1), queens, ICL_DOM); 00280 distinct(*this, IntArgs::create(n,0,-1), queens, ICL_DOM); 00281 00282 // N-rooks constraints 00283 distinct(*this, rooks, ICL_DOM); 00284 00285 // Collect diagonals for handling queens and bishops 00286 for (int l = n; l--; ) { 00287 const int il = (n-1) - l; 00288 IntVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1); 00289 for (int i = 0; i <= l; ++i) { 00290 d1[i] = m(i+il, i); 00291 d2[i] = m(i, i+il); 00292 d3[i] = m((n-1)-i-il, i); 00293 d4[i] = m((n-1)-i, i+il); 00294 } 00295 00296 count(*this, d1, Q, IRT_LQ, 1, opt.icl()); 00297 count(*this, d2, Q, IRT_LQ, 1, opt.icl()); 00298 count(*this, d3, Q, IRT_LQ, 1, opt.icl()); 00299 count(*this, d4, Q, IRT_LQ, 1, opt.icl()); 00300 if (opt.propagation() == PROP_DECOMPOSE) { 00301 count(*this, d1, B, IRT_LQ, 1, opt.icl()); 00302 count(*this, d2, B, IRT_LQ, 1, opt.icl()); 00303 count(*this, d3, B, IRT_LQ, 1, opt.icl()); 00304 count(*this, d4, B, IRT_LQ, 1, opt.icl()); 00305 } 00306 } 00307 if (opt.propagation() == PROP_TUPLE_SET) { 00308 IntVarArgs b(s.size()); 00309 for (int i = s.size(); i--; ) 00310 b[i] = channel(*this, expr(*this, (s[i] == B))); 00311 extensional(*this, b, bishops, EPK_DEF, opt.icl()); 00312 } 00313 00314 // Handle knigths 00315 // Connect knigths to board 00316 for(int i = n*n; i--; ) 00317 knights[i] = expr(*this, (s[i] == K)); 00318 knight_constraints(); 00319 00320 00321 // *********************** 00322 // Redundant constraints 00323 // *********************** 00324 00325 // Queens and rooks not in the same place 00326 // Faster than going through the channelled board-connection 00327 for (int i = n; i--; ) 00328 rel(*this, queens[i], IRT_NQ, rooks[i]); 00329 00330 // Place bishops in two corners (from Schimpf and Hansens solution) 00331 // Avoids some symmetries of the problem 00332 rel(*this, m(n-1, 0), IRT_EQ, B); 00333 rel(*this, m(n-1, n-1), IRT_EQ, B); 00334 00335 00336 // *********************** 00337 // Branching 00338 // *********************** 00339 // Place each piece in turn 00340 branch(*this, s, INT_VAR_MIN_MIN, INT_VAL_MIN); 00341 } 00342 00344 CrowdedChess(bool share, CrowdedChess& e) 00345 : Script(share,e), n(e.n) { 00346 s.update(*this, share, e.s); 00347 queens.update(*this, share, e.queens); 00348 rooks.update(*this, share, e.rooks); 00349 knights.update(*this, share, e.knights); 00350 } 00351 00353 virtual Space* 00354 copy(bool share) { 00355 return new CrowdedChess(share,*this); 00356 } 00357 00359 virtual void 00360 print(std::ostream& os) const { 00361 Matrix<IntVarArray> m(s, n); 00362 char names[PMAX]; 00363 names[E] = '.'; names[Q] = 'Q'; names[R] = 'R'; 00364 names[B] = 'B'; names[K] = 'K'; 00365 const char* sep = n < 8 ? "\t\t" : "\t"; 00366 00367 for (int r = 0; r < n; ++r){ 00368 // Print main board 00369 os << '\t'; 00370 for (int c = 0; c < n; ++c) { 00371 if (m(r, c).assigned()) { 00372 os << names[m(r, c).val()]; 00373 } else { 00374 os << " "; 00375 } 00376 } 00377 // Print each piece on its own 00378 for (int p = 0; p < PMAX; ++p) { 00379 if (p == E) continue; 00380 os << sep; 00381 for (int c = 0; c < n; ++c) { 00382 if (m(r, c).assigned()) { 00383 if (m(r, c).val() == p) 00384 os << names[p]; 00385 else 00386 os << names[E]; 00387 } else { 00388 os << " "; 00389 } 00390 } 00391 } 00392 os << std::endl; 00393 } 00394 os << std::endl; 00395 } 00396 }; 00397 00401 int 00402 main(int argc, char* argv[]) { 00403 SizeOptions opt("CrowdedChess"); 00404 opt.propagation(CrowdedChess::PROP_TUPLE_SET); 00405 opt.propagation(CrowdedChess::PROP_TUPLE_SET, 00406 "extensional", 00407 "Use extensional propagation for bishops-placement"); 00408 opt.propagation(CrowdedChess::PROP_DECOMPOSE, 00409 "decompose", 00410 "Use decomposed propagation for bishops-placement"); 00411 opt.icl(ICL_DOM); 00412 opt.size(8); 00413 opt.parse(argc,argv); 00414 if (opt.size() < 5) { 00415 std::cerr << "Error: size must be at least 5" << std::endl; 00416 return 1; 00417 } 00418 init_bishops(opt.size()); 00419 Script::run<CrowdedChess,DFS,SizeOptions>(opt); 00420 return 0; 00421 } 00422 00423 // STATISTICS: example-any 00424