Generated on Sat Jan 12 2019 20:58:51 for Gecode by doxygen 1.8.13
minesweeper.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Copyright:
7  * Guido Tack, 2006
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/driver.hh>
35 #include <gecode/int.hh>
36 #include <gecode/minimodel.hh>
37 
38 #include <cctype>
39 
40 using namespace Gecode;
41 
42 namespace {
43  extern const char *specs[];
44  extern const unsigned int n_examples;
45  int spec_size(const char *s);
46  int mineField(const char *s, int n, int i, int j);
47 }
48 
60 class MineSweeper : public Script {
61 private:
62  const char *spec;
63  int size;
65 
67  BoolVar pos(int h, int w) {
68  return b[h*size + w];
69  }
71  const BoolVar pos(int h, int w) const {
72  return b[h*size + w];
73  }
74 
76  BoolVarArgs fieldsAround(Matrix<BoolVarArray>& m,
77  int x, int y) {
78  int bvsize=0;
79  for (int ix = std::max(0, x-1); ix<=x+1 && ix<size; ix++)
80  for (int iy = std::max(0, y-1); iy<=y+1 && iy<size; iy++)
81  bvsize++;
82  bvsize--; // remove (x,y) itself
83  BoolVarArgs b(bvsize);
84  int count=0;
85  for (int ix = std::max(0, x-1); ix<=x+1 && ix<size; ix++)
86  for (int iy = std::max(0, y-1); iy<=y+1 && iy<size; iy++)
87  if (ix != x || iy != y)
88  b[count++] = m(ix,iy);
89 
90  return b;
91  }
92 
93 public:
96  : Script(opt), spec(specs[opt.size()]),
97  size(spec_size(spec)),
98  b(*this,size*size,0,1) {
99  Matrix<BoolVarArray> m(b, size, size);
100 
101  // Initialize matrix and post constraints
102  for (int h=0; h<size; h++)
103  for (int w=0; w<size; w++) {
104  int v = mineField(spec, size, h, w);
105  if (v != -1) {
106  rel(*this, m(w, h), IRT_EQ, 0);
107  linear(*this, fieldsAround(m, w, h), IRT_EQ, v);
108  }
109  }
110 
111  // Install branching
112  branch(*this, b, BOOL_VAR_NONE(), BOOL_VAL_MAX());
113  }
114 
116  virtual void
117  print(std::ostream& os) const {
118  for (int h = 0; h < size; ++h) {
119  os << '\t';
120  for (int w = 0; w < size; ++w) {
121  int v = mineField(spec, size, h, w);
122  if (v != -1)
123  os << v << " ";
124  else if (pos(h,w).val() == 1)
125  os << "* ";
126  else
127  os << ". ";
128  }
129  os << std::endl;
130  }
131  os << std::endl;
132  }
133 
136  Script(s), spec(s.spec), size(s.size) {
137  b.update(*this, s.b);
138  }
140  virtual Space*
141  copy(void) {
142  return new MineSweeper(*this);
143  }
144 
145 };
146 
147 
151 int
152 main(int argc, char* argv[]) {
153  SizeOptions opt("MineSweeper");
154  opt.size(0);
155  opt.parse(argc,argv);
156  if (opt.size() >= n_examples) {
157  std::cerr << "Error: size must be between 0 and "
158  << n_examples-1 << std::endl;
159  return 1;
160  }
161  Script::run<MineSweeper,DFS,SizeOptions>(opt);
162  return 0;
163 }
164 
165 
166 namespace {
167 
177 
179  const char* specs[] = {
180  // 0
181  "..2.3."
182  "2....."
183  "..24.3"
184  "1.34.."
185  ".....3"
186  ".3.3..",
187  // 1
188  ".2.211.."
189  "..4.2..2"
190  "2..2..3."
191  "2.22.3.3"
192  "..1...4."
193  "1...2..3"
194  ".2.22.3."
195  "1.1..1.1",
196  // 2
197  "1..2.2.2.."
198  ".32...4..1"
199  "...13...4."
200  "3.1...3..."
201  ".21.1..3.2"
202  ".3.2..2.1."
203  "2..32..2.."
204  ".3...32..3"
205  "..3.33...."
206  ".2.2...22.",
207  // 3
208  "2...3.1."
209  ".5.4...1"
210  "..5..4.."
211  "2...4.5."
212  ".2.4...2"
213  "..5..4.."
214  "2...5.4."
215  ".3.3...2",
216  // 4
217  "0.0.1..11."
218  "1.2.2.22.."
219  "......2..2"
220  ".23.11...."
221  "0......2.1"
222  "...22.1..."
223  ".....3.32."
224  ".5.2...3.1"
225  ".3.1..3..."
226  ".2...12..0",
227  // 5
228  ".21.2.2..."
229  ".4..3...53"
230  "...4.44..3"
231  "4.4..5.6.."
232  "..45....54"
233  "34....55.."
234  "..4.4..5.5"
235  "2..33.6..."
236  "36...3..4."
237  "...4.2.21.",
238  // 6
239  ".32..1.."
240  "....1..3"
241  "3..2...4"
242  ".5...5.."
243  "..6...5."
244  "3...5..4"
245  "2..5...."
246  "..2..34.",
247  // 7
248  ".1.....3."
249  "...343..."
250  "244...443"
251  "...4.4..."
252  ".4.4.3.6."
253  "...4.3..."
254  "123...133"
255  "...322..."
256  ".2.....3.",
257  // 8
258  "......."
259  ".23435."
260  ".1...3."
261  "...5..."
262  ".1...3."
263  ".12234."
264  ".......",
265  // 9
266  "2...2...2"
267  ".4.4.3.4."
268  "..4...1.."
269  ".4.3.3.4."
270  "2.......2"
271  ".5.4.5.4."
272  "..3...3.."
273  ".4.3.5.6."
274  "2...1...2"
275  };
276 
278  const unsigned int n_examples = sizeof(specs)/sizeof(char*);
279 
281  int spec_size(const char *s) {
282  int l = std::strlen(s);
283  int res = static_cast<int>(std::sqrt(static_cast<float>(l)));
284  return res;
285  }
286 
288  int mineField(const char *s, int n, int i, int j) {
289  assert(spec_size(s) == n);
290  assert(i >= 0 && i < n);
291  assert(j >= 0 && j < n);
292  char c = s[i*n + j];
293  if (!std::isalnum(c))
294  return -1;
295  if (std::isdigit(c))
296  return c - '0';
297  if (std::islower(c))
298  c = static_cast<char>(std::toupper(c));
299  // std::alpha(c) == true
300  int res = (c - 'A') + 10;
301  if (res > n) return 0;
302  else return res;
303  }
305 }
306 
307 // STATISTICS: example-any
void size(unsigned int s)
Set default size.
Definition: options.hpp:586
virtual Space * copy(void)
Copy space during cloning.
Options for scripts with additional size parameter
Definition: driver.hh:675
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:364
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:39
int main(int argc, char *argv[])
Main-function.
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:40
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:995
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:666
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
virtual void print(std::ostream &os) const
Print solution.
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
Computation spaces.
Definition: core.hpp:1701
Parametric base-class for scripts.
Definition: driver.hh:729
Gecode::FloatVal c(-8, 8)
Example: Minesweeper
Definition: minesweeper.cpp:60
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition: val.hpp:135
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Equality ( )
Definition: int.hh:926
Options opt
The options.
Definition: test.cpp:97
Gecode::IntArgs i({1, 2, 3, 4})
void sqrt(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:102
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
unsigned int size(I &i)
Size of all ranges of range iterator i.
int spec_size(const char *s)
Compute the size of a specification.
Passing Boolean variables.
Definition: int.hh:712
Boolean variable array.
Definition: int.hh:808
Boolean integer variables.
Definition: int.hh:512
const int v[7]
Definition: distinct.cpp:259
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
int mineField(const char *s, int n, int i, int j)
Return value at position (i,j) in the example s of size n.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Post propagator for SetVar x
Definition: set.hh:767
Matrix-interface for arrays.
Definition: minimodel.hh:2048
Gecode toplevel namespace
MineSweeper(const SizeOptions &opt)
Actual model.
Definition: minesweeper.cpp:95
MineSweeper(MineSweeper &s)
Constructor for cloning s.