minesweeper.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * 00006 * Copyright: 00007 * Guido Tack, 2006 00008 * 00009 * Last modified: 00010 * $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00011 * $Revision: 11473 $ 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 #include <gecode/driver.hh> 00039 #include <gecode/int.hh> 00040 #include <gecode/minimodel.hh> 00041 00042 #include <cctype> 00043 00044 using namespace Gecode; 00045 00046 namespace { 00047 extern const char *specs[]; 00048 extern const unsigned int n_examples; 00049 int spec_size(const char *s); 00050 int mineField(const char *s, int n, int i, int j); 00051 } 00052 00064 class MineSweeper : public Script { 00065 private: 00066 const char *spec; 00067 int size; 00068 BoolVarArray b; 00069 00071 BoolVar pos(int h, int w) { 00072 return b[h*size + w]; 00073 } 00075 const BoolVar pos(int h, int w) const { 00076 return b[h*size + w]; 00077 } 00078 00080 BoolVarArgs fieldsAround(Matrix<BoolVarArray>& m, 00081 int x, int y) { 00082 int bvsize=0; 00083 for (int ix = std::max(0, x-1); ix<=x+1 && ix<size; ix++) 00084 for (int iy = std::max(0, y-1); iy<=y+1 && iy<size; iy++) 00085 bvsize++; 00086 bvsize--; // remove (x,y) itself 00087 BoolVarArgs b(bvsize); 00088 int count=0; 00089 for (int ix = std::max(0, x-1); ix<=x+1 && ix<size; ix++) 00090 for (int iy = std::max(0, y-1); iy<=y+1 && iy<size; iy++) 00091 if (ix != x || iy != y) 00092 b[count++] = m(ix,iy); 00093 00094 return b; 00095 } 00096 00097 public: 00099 MineSweeper(const SizeOptions& opt) 00100 : spec(specs[opt.size()]), 00101 size(spec_size(spec)), 00102 b(*this,size*size,0,1) { 00103 Matrix<BoolVarArray> m(b, size, size); 00104 00105 // Initialize matrix and post constraints 00106 for (int h=0; h<size; h++) 00107 for (int w=0; w<size; w++) { 00108 int v = mineField(spec, size, h, w); 00109 if (v != -1) { 00110 rel(*this, m(w, h), IRT_EQ, 0); 00111 linear(*this, fieldsAround(m, w, h), IRT_EQ, v); 00112 } 00113 } 00114 00115 // Install branching 00116 branch(*this, b, INT_VAR_NONE, INT_VAL_MAX); 00117 } 00118 00120 virtual void 00121 print(std::ostream& os) const { 00122 for (int h = 0; h < size; ++h) { 00123 os << '\t'; 00124 for (int w = 0; w < size; ++w) { 00125 int v = mineField(spec, size, h, w); 00126 if ( v != -1) 00127 os << v << " "; 00128 else if (pos(h,w).val() == 1) 00129 os << "* "; 00130 else 00131 os << ". "; 00132 } 00133 os << std::endl; 00134 } 00135 os << std::endl; 00136 } 00137 00139 MineSweeper(bool share, MineSweeper& s) : 00140 Script(share,s), spec(s.spec), size(s.size) { 00141 b.update(*this, share, s.b); 00142 } 00144 virtual Space* 00145 copy(bool share) { 00146 return new MineSweeper(share,*this); 00147 } 00148 00149 }; 00150 00151 00155 int 00156 main(int argc, char* argv[]) { 00157 SizeOptions opt("MineSweeper"); 00158 opt.size(0); 00159 opt.parse(argc,argv); 00160 if (opt.size() >= n_examples) { 00161 std::cerr << "Error: size must be between 0 and " 00162 << n_examples-1 << std::endl; 00163 return 1; 00164 } 00165 Script::run<MineSweeper,DFS,SizeOptions>(opt); 00166 return 0; 00167 } 00168 00169 00170 namespace { 00171 00181 00183 const char* specs[] = { 00184 // 0 00185 "..2.3." 00186 "2....." 00187 "..24.3" 00188 "1.34.." 00189 ".....3" 00190 ".3.3..", 00191 // 1 00192 ".2.211.." 00193 "..4.2..2" 00194 "2..2..3." 00195 "2.22.3.3" 00196 "..1...4." 00197 "1...2..3" 00198 ".2.22.3." 00199 "1.1..1.1", 00200 // 2 00201 "1..2.2.2.." 00202 ".32...4..1" 00203 "...13...4." 00204 "3.1...3..." 00205 ".21.1..3.2" 00206 ".3.2..2.1." 00207 "2..32..2.." 00208 ".3...32..3" 00209 "..3.33...." 00210 ".2.2...22.", 00211 // 3 00212 "2...3.1." 00213 ".5.4...1" 00214 "..5..4.." 00215 "2...4.5." 00216 ".2.4...2" 00217 "..5..4.." 00218 "2...5.4." 00219 ".3.3...2", 00220 // 4 00221 "0.0.1..11." 00222 "1.2.2.22.." 00223 "......2..2" 00224 ".23.11...." 00225 "0......2.1" 00226 "...22.1..." 00227 ".....3.32." 00228 ".5.2...3.1" 00229 ".3.1..3..." 00230 ".2...12..0", 00231 // 5 00232 ".21.2.2..." 00233 ".4..3...53" 00234 "...4.44..3" 00235 "4.4..5.6.." 00236 "..45....54" 00237 "34....55.." 00238 "..4.4..5.5" 00239 "2..33.6..." 00240 "36...3..4." 00241 "...4.2.21.", 00242 // 6 00243 ".32..1.." 00244 "....1..3" 00245 "3..2...4" 00246 ".5...5.." 00247 "..6...5." 00248 "3...5..4" 00249 "2..5...." 00250 "..2..34.", 00251 // 7 00252 ".1.....3." 00253 "...343..." 00254 "244...443" 00255 "...4.4..." 00256 ".4.4.3.6." 00257 "...4.3..." 00258 "123...133" 00259 "...322..." 00260 ".2.....3.", 00261 // 8 00262 "......." 00263 ".23435." 00264 ".1...3." 00265 "...5..." 00266 ".1...3." 00267 ".12234." 00268 ".......", 00269 // 9 00270 "2...2...2" 00271 ".4.4.3.4." 00272 "..4...1.." 00273 ".4.3.3.4." 00274 "2.......2" 00275 ".5.4.5.4." 00276 "..3...3.." 00277 ".4.3.5.6." 00278 "2...1...2" 00279 }; 00280 00282 const unsigned int n_examples = sizeof(specs)/sizeof(char*); 00283 00285 int spec_size(const char *s) { 00286 int l = std::strlen(s); 00287 int res = static_cast<int>(std::sqrt(static_cast<float>(l))); 00288 return res; 00289 } 00290 00292 int mineField(const char *s, int n, int i, int j) { 00293 assert(spec_size(s) == n); 00294 assert(i >= 0 && i < n); 00295 assert(j >= 0 && j < n); 00296 char c = s[i*n + j]; 00297 if (!std::isalnum(c)) 00298 return -1; 00299 if (std::isdigit(c)) 00300 return c - '0'; 00301 if (std::islower(c)) 00302 c = static_cast<char>(std::toupper(c)); 00303 // std::alpha(c) == true 00304 int res = (c - 'A') + 10; 00305 if (res > n) return 0; 00306 else return res; 00307 } 00309 } 00310 00311 // STATISTICS: example-any