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