this repo has no description
dekker.one
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
40using namespace Gecode;
41
42namespace {
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
49/**
50 * \brief %Example: Minesweeper
51 *
52 * This is the classical MineSweeper game.
53 *
54 * The instances are taken from
55 * http://www.janko.at/Raetsel/Minesweeper/index.htm
56 *
57 * \ingroup Example
58 *
59 */
60class MineSweeper : public Script {
61private:
62 const char *spec;
63 int size;
64 BoolVarArray b;
65
66 /// Access position (\a h,\a w) in the matrix.
67 BoolVar pos(int h, int w) {
68 return b[h*size + w];
69 }
70 /// Access position (\a h,\a w) in the matrix.
71 const BoolVar pos(int h, int w) const {
72 return b[h*size + w];
73 }
74
75 /// Return the fields in \a m around position (\a x,\a y)
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
93public:
94 /// Actual model
95 MineSweeper(const SizeOptions& opt)
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
115 /// Print solution
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
134 /// Constructor for cloning \a s
135 MineSweeper(MineSweeper& s) :
136 Script(s), spec(s.spec), size(s.size) {
137 b.update(*this, s.b);
138 }
139 /// Copy space during cloning
140 virtual Space*
141 copy(void) {
142 return new MineSweeper(*this);
143 }
144
145};
146
147
148/** \brief Main-function
149 * \relates MineSweeper
150 */
151int
152main(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
166namespace {
167
168 /** \name Minesweeper specifications
169 *
170 * A specification is a square matrix of characters. Alphanumeric characters represent
171 * the number of mines adjacent to that field. Dots represent fields with an unknown number
172 * of mines adjacent to it (or an actual mine).
173 *
174 * \relates MineSweeper
175 */
176 //@{
177
178 /// The specifications
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
277 /// Number of specifications
278 const unsigned int n_examples = sizeof(specs)/sizeof(char*);
279
280 /// Compute the size of a specification
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
287 /// Return value at position (\a i,\a j) in the example \a s of size \a n
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 }
304 //@}
305}
306
307// STATISTICS: example-any