minesweeper.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Guido Tack, 2006
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
#include <cctype>
using namespace Gecode;
namespace {
extern const char *specs[];
extern const unsigned int n_examples;
int spec_size(const char *s);
int mineField(const char *s, int n, int i, int j);
}
class MineSweeper : public Script {
private:
const char *spec;
int size;
BoolVarArray b;
BoolVar pos(int h, int w) {
return b[h*size + w];
}
const BoolVar pos(int h, int w) const {
return b[h*size + w];
}
BoolVarArgs fieldsAround(Matrix<BoolVarArray>& m,
int x, int y) {
int bvsize=0;
for (int ix = std::max(0, x-1); ix<=x+1 && ix<size; ix++)
for (int iy = std::max(0, y-1); iy<=y+1 && iy<size; iy++)
bvsize++;
bvsize--; // remove (x,y) itself
BoolVarArgs b(bvsize);
int count=0;
for (int ix = std::max(0, x-1); ix<=x+1 && ix<size; ix++)
for (int iy = std::max(0, y-1); iy<=y+1 && iy<size; iy++)
if (ix != x || iy != y)
b[count++] = m(ix,iy);
return b;
}
public:
MineSweeper(const SizeOptions& opt)
: Script(opt), spec(specs[opt.size()]),
size(spec_size(spec)),
b(*this,size*size,0,1) {
Matrix<BoolVarArray> m(b, size, size);
// Initialize matrix and post constraints
for (int h=0; h<size; h++)
for (int w=0; w<size; w++) {
int v = mineField(spec, size, h, w);
if (v != -1) {
rel(*this, m(w, h), IRT_EQ, 0);
linear(*this, fieldsAround(m, w, h), IRT_EQ, v);
}
}
// Install branching
branch(*this, b, BOOL_VAR_NONE(), BOOL_VAL_MAX());
}
virtual void
print(std::ostream& os) const {
for (int h = 0; h < size; ++h) {
os << '\t';
for (int w = 0; w < size; ++w) {
int v = mineField(spec, size, h, w);
if (v != -1)
os << v << " ";
else if (pos(h,w).val() == 1)
os << "* ";
else
os << ". ";
}
os << std::endl;
}
os << std::endl;
}
MineSweeper(MineSweeper& s) :
Script(s), spec(s.spec), size(s.size) {
b.update(*this, s.b);
}
virtual Space*
copy(void) {
return new MineSweeper(*this);
}
};
int
main(int argc, char* argv[]) {
SizeOptions opt("MineSweeper");
opt.size(0);
opt.parse(argc,argv);
if (opt.size() >= n_examples) {
std::cerr << "Error: size must be between 0 and "
<< n_examples-1 << std::endl;
return 1;
}
Script::run<MineSweeper,DFS,SizeOptions>(opt);
return 0;
}
namespace {
const char* specs[] = {
// 0
"..2.3."
"2....."
"..24.3"
"1.34.."
".....3"
".3.3..",
// 1
".2.211.."
"..4.2..2"
"2..2..3."
"2.22.3.3"
"..1...4."
"1...2..3"
".2.22.3."
"1.1..1.1",
// 2
"1..2.2.2.."
".32...4..1"
"...13...4."
"3.1...3..."
".21.1..3.2"
".3.2..2.1."
"2..32..2.."
".3...32..3"
"..3.33...."
".2.2...22.",
// 3
"2...3.1."
".5.4...1"
"..5..4.."
"2...4.5."
".2.4...2"
"..5..4.."
"2...5.4."
".3.3...2",
// 4
"0.0.1..11."
"1.2.2.22.."
"......2..2"
".23.11...."
"0......2.1"
"...22.1..."
".....3.32."
".5.2...3.1"
".3.1..3..."
".2...12..0",
// 5
".21.2.2..."
".4..3...53"
"...4.44..3"
"4.4..5.6.."
"..45....54"
"34....55.."
"..4.4..5.5"
"2..33.6..."
"36...3..4."
"...4.2.21.",
// 6
".32..1.."
"....1..3"
"3..2...4"
".5...5.."
"..6...5."
"3...5..4"
"2..5...."
"..2..34.",
// 7
".1.....3."
"...343..."
"244...443"
"...4.4..."
".4.4.3.6."
"...4.3..."
"123...133"
"...322..."
".2.....3.",
// 8
"......."
".23435."
".1...3."
"...5..."
".1...3."
".12234."
".......",
// 9
"2...2...2"
".4.4.3.4."
"..4...1.."
".4.3.3.4."
"2.......2"
".5.4.5.4."
"..3...3.."
".4.3.5.6."
"2...1...2"
};
const unsigned int n_examples = sizeof(specs)/sizeof(char*);
int spec_size(const char *s) {
int l = std::strlen(s);
int res = static_cast<int>(std::sqrt(static_cast<float>(l)));
return res;
}
int mineField(const char *s, int n, int i, int j) {
assert(spec_size(s) == n);
assert(i >= 0 && i < n);
assert(j >= 0 && j < n);
char c = s[i*n + j];
if (!std::isalnum(c))
return -1;
if (std::isdigit(c))
return c - '0';
if (std::islower(c))
c = static_cast<char>(std::toupper(c));
// std::alpha(c) == true
int res = (c - 'A') + 10;
if (res > n) return 0;
else return res;
}
}
// STATISTICS: example-any
Gecode::BoolVarArgs
Passing Boolean variables.
Definition int.hh:712
Gecode::BoolVarArray
Boolean variable array.
Definition int.hh:808
Gecode::BoolVar
Boolean integer variables.
Definition int.hh:512
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::Matrix
Matrix-interface for arrays.
Definition minimodel.hh:2161
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:675
Gecode::Space
Computation spaces.
Definition core.hpp:1742
MineSweeper::main
int main(int argc, char *argv[])
Main-function.
Definition minesweeper.cpp:152
MineSweeper::n_examples
const unsigned int n_examples
Number of specifications.
Definition minesweeper.cpp:278
MineSweeper::spec_size
int spec_size(const char *s)
Compute the size of a specification.
Definition minesweeper.cpp:281
MineSweeper::specs
const char * specs[]
The specifications.
Definition minesweeper.cpp:179
MineSweeper::mineField
int mineField(const char *s, int n, int i, int j)
Return value at position (i,j) in the example s of size n.
Definition minesweeper.cpp:288
MineSweeper::MineSweeper
MineSweeper(MineSweeper &s)
Constructor for cloning s.
Definition minesweeper.cpp:135
MineSweeper::copy
virtual Space * copy(void)
Copy space during cloning.
Definition minesweeper.cpp:141
MineSweeper::MineSweeper
MineSweeper(const SizeOptions &opt)
Actual model.
Definition minesweeper.cpp:95
MineSweeper::print
virtual void print(std::ostream &os) const
Print solution.
Definition minesweeper.cpp:117
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
driver.hh
int.hh
Gecode::Script
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
Gecode::branch
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
Gecode::linear
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::count
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Gecode::BOOL_VAR_NONE
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:364
Gecode::BOOL_VAL_MAX
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition val.hpp:135