Generated on Fri Oct 19 11:24:48 2018 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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--; // remove (x,y) itself
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     // Initialize matrix and post constraints
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     // Install branching
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       // 0
00181       "..2.3."
00182       "2....."
00183       "..24.3"
00184       "1.34.."
00185       ".....3"
00186       ".3.3..",
00187       // 1
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       // 2
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       // 3
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       // 4
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       // 5
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       // 6
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       // 7
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       // 8
00258       "......."
00259       ".23435."
00260       ".1...3."
00261       "...5..."
00262       ".1...3."
00263       ".12234."
00264       ".......",
00265       // 9
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     // std::alpha(c) == true
00300     int res = (c - 'A') + 10;
00301     if (res > n) return 0;
00302     else return res;
00303   }
00305 }
00306 
00307 // STATISTICS: example-any