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 #include <gecode/driver.hh>
00035 #include <gecode/int.hh>
00036 #include <gecode/minimodel.hh>
00037
00038 #include <cctype>
00039
00040 using namespace Gecode;
00041
00042 namespace {
00043 extern const char *specs[];
00044 extern const unsigned int n_examples;
00045 int spec_size(const char *s);
00046 int mineField(const char *s, int n, int i, int j);
00047 }
00048
00060 class MineSweeper : public Script {
00061 private:
00062 const char *spec;
00063 int size;
00064 BoolVarArray b;
00065
00067 BoolVar pos(int h, int w) {
00068 return b[h*size + w];
00069 }
00071 const BoolVar pos(int h, int w) const {
00072 return b[h*size + w];
00073 }
00074
00076 BoolVarArgs fieldsAround(Matrix<BoolVarArray>& m,
00077 int x, int y) {
00078 int bvsize=0;
00079 for (int ix = std::max(0, x-1); ix<=x+1 && ix<size; ix++)
00080 for (int iy = std::max(0, y-1); iy<=y+1 && iy<size; iy++)
00081 bvsize++;
00082 bvsize--;
00083 BoolVarArgs b(bvsize);
00084 int count=0;
00085 for (int ix = std::max(0, x-1); ix<=x+1 && ix<size; ix++)
00086 for (int iy = std::max(0, y-1); iy<=y+1 && iy<size; iy++)
00087 if (ix != x || iy != y)
00088 b[count++] = m(ix,iy);
00089
00090 return b;
00091 }
00092
00093 public:
00095 MineSweeper(const SizeOptions& opt)
00096 : Script(opt), spec(specs[opt.size()]),
00097 size(spec_size(spec)),
00098 b(*this,size*size,0,1) {
00099 Matrix<BoolVarArray> m(b, size, size);
00100
00101
00102 for (int h=0; h<size; h++)
00103 for (int w=0; w<size; w++) {
00104 int v = mineField(spec, size, h, w);
00105 if (v != -1) {
00106 rel(*this, m(w, h), IRT_EQ, 0);
00107 linear(*this, fieldsAround(m, w, h), IRT_EQ, v);
00108 }
00109 }
00110
00111
00112 branch(*this, b, BOOL_VAR_NONE(), BOOL_VAL_MAX());
00113 }
00114
00116 virtual void
00117 print(std::ostream& os) const {
00118 for (int h = 0; h < size; ++h) {
00119 os << '\t';
00120 for (int w = 0; w < size; ++w) {
00121 int v = mineField(spec, size, h, w);
00122 if (v != -1)
00123 os << v << " ";
00124 else if (pos(h,w).val() == 1)
00125 os << "* ";
00126 else
00127 os << ". ";
00128 }
00129 os << std::endl;
00130 }
00131 os << std::endl;
00132 }
00133
00135 MineSweeper(MineSweeper& s) :
00136 Script(s), spec(s.spec), size(s.size) {
00137 b.update(*this, s.b);
00138 }
00140 virtual Space*
00141 copy(void) {
00142 return new MineSweeper(*this);
00143 }
00144
00145 };
00146
00147
00151 int
00152 main(int argc, char* argv[]) {
00153 SizeOptions opt("MineSweeper");
00154 opt.size(0);
00155 opt.parse(argc,argv);
00156 if (opt.size() >= n_examples) {
00157 std::cerr << "Error: size must be between 0 and "
00158 << n_examples-1 << std::endl;
00159 return 1;
00160 }
00161 Script::run<MineSweeper,DFS,SizeOptions>(opt);
00162 return 0;
00163 }
00164
00165
00166 namespace {
00167
00177
00179 const char* specs[] = {
00180
00181 "..2.3."
00182 "2....."
00183 "..24.3"
00184 "1.34.."
00185 ".....3"
00186 ".3.3..",
00187
00188 ".2.211.."
00189 "..4.2..2"
00190 "2..2..3."
00191 "2.22.3.3"
00192 "..1...4."
00193 "1...2..3"
00194 ".2.22.3."
00195 "1.1..1.1",
00196
00197 "1..2.2.2.."
00198 ".32...4..1"
00199 "...13...4."
00200 "3.1...3..."
00201 ".21.1..3.2"
00202 ".3.2..2.1."
00203 "2..32..2.."
00204 ".3...32..3"
00205 "..3.33...."
00206 ".2.2...22.",
00207
00208 "2...3.1."
00209 ".5.4...1"
00210 "..5..4.."
00211 "2...4.5."
00212 ".2.4...2"
00213 "..5..4.."
00214 "2...5.4."
00215 ".3.3...2",
00216
00217 "0.0.1..11."
00218 "1.2.2.22.."
00219 "......2..2"
00220 ".23.11...."
00221 "0......2.1"
00222 "...22.1..."
00223 ".....3.32."
00224 ".5.2...3.1"
00225 ".3.1..3..."
00226 ".2...12..0",
00227
00228 ".21.2.2..."
00229 ".4..3...53"
00230 "...4.44..3"
00231 "4.4..5.6.."
00232 "..45....54"
00233 "34....55.."
00234 "..4.4..5.5"
00235 "2..33.6..."
00236 "36...3..4."
00237 "...4.2.21.",
00238
00239 ".32..1.."
00240 "....1..3"
00241 "3..2...4"
00242 ".5...5.."
00243 "..6...5."
00244 "3...5..4"
00245 "2..5...."
00246 "..2..34.",
00247
00248 ".1.....3."
00249 "...343..."
00250 "244...443"
00251 "...4.4..."
00252 ".4.4.3.6."
00253 "...4.3..."
00254 "123...133"
00255 "...322..."
00256 ".2.....3.",
00257
00258 "......."
00259 ".23435."
00260 ".1...3."
00261 "...5..."
00262 ".1...3."
00263 ".12234."
00264 ".......",
00265
00266 "2...2...2"
00267 ".4.4.3.4."
00268 "..4...1.."
00269 ".4.3.3.4."
00270 "2.......2"
00271 ".5.4.5.4."
00272 "..3...3.."
00273 ".4.3.5.6."
00274 "2...1...2"
00275 };
00276
00278 const unsigned int n_examples = sizeof(specs)/sizeof(char*);
00279
00281 int spec_size(const char *s) {
00282 int l = std::strlen(s);
00283 int res = static_cast<int>(std::sqrt(static_cast<float>(l)));
00284 return res;
00285 }
00286
00288 int mineField(const char *s, int n, int i, int j) {
00289 assert(spec_size(s) == n);
00290 assert(i >= 0 && i < n);
00291 assert(j >= 0 && j < n);
00292 char c = s[i*n + j];
00293 if (!std::isalnum(c))
00294 return -1;
00295 if (std::isdigit(c))
00296 return c - '0';
00297 if (std::islower(c))
00298 c = static_cast<char>(std::toupper(c));
00299
00300 int res = (c - 'A') + 10;
00301 if (res > n) return 0;
00302 else return res;
00303 }
00305 }
00306
00307