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 #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--;
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
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
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
00185 "..2.3."
00186 "2....."
00187 "..24.3"
00188 "1.34.."
00189 ".....3"
00190 ".3.3..",
00191
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
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
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
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
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
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
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
00262 "......."
00263 ".23435."
00264 ".1...3."
00265 "...5..."
00266 ".1...3."
00267 ".12234."
00268 ".......",
00269
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
00304 int res = (c - 'A') + 10;
00305 if (res > n) return 0;
00306 else return res;
00307 }
00309 }
00310
00311