summaryrefslogtreecommitdiffstats
path: root/kmines/solver
diff options
context:
space:
mode:
Diffstat (limited to 'kmines/solver')
-rw-r--r--kmines/solver/Makefile.am18
-rw-r--r--kmines/solver/advFastRules.cpp482
-rw-r--r--kmines/solver/adviseFast.cpp201
-rw-r--r--kmines/solver/adviseFast.h70
-rw-r--r--kmines/solver/adviseFull.cpp655
-rw-r--r--kmines/solver/adviseFull.h93
-rw-r--r--kmines/solver/bfield.cpp221
-rw-r--r--kmines/solver/bfield.h83
-rw-r--r--kmines/solver/headerP.h191
-rw-r--r--kmines/solver/solver.cpp249
-rw-r--r--kmines/solver/solver.h84
-rw-r--r--kmines/solver/test.cpp45
-rw-r--r--kmines/solver/testFast.cpp30
-rw-r--r--kmines/solver/testRate.cpp41
-rw-r--r--kmines/solver/testSolve.cpp33
15 files changed, 2496 insertions, 0 deletions
diff --git a/kmines/solver/Makefile.am b/kmines/solver/Makefile.am
new file mode 100644
index 00000000..8a6696a7
--- /dev/null
+++ b/kmines/solver/Makefile.am
@@ -0,0 +1,18 @@
+INCLUDES = -I$(top_srcdir)/kmines/generic -I$(top_srcdir)/kmines -I$(top_srcdir)/libkdegames $(all_includes)
+
+noinst_LTLIBRARIES = libsolver.la
+noinst_HEADERS = bfield.h solver.h headerP.h adviseFast.h adviseFull.h
+libsolver_la_LDFLAGS = $(all_libraries) $(KDE_RPATH) -no-undefined
+libsolver_la_SOURCES = bfield.cpp solver.cpp advFastRules.cpp adviseFast.cpp \
+ adviseFull.cpp
+METASOURCES = solver.moc
+
+check_PROGRAMS = test testFast testSolve testRate
+test_SOURCES = test.cpp
+test_LDADD = ./libsolver.la $(LIB_KDECORE)
+testFast_SOURCES = testFast.cpp
+testFast_LDADD = ./libsolver.la $(LIB_KDECORE)
+testSolve_SOURCES = testSolve.cpp
+testSolve_LDADD = ./libsolver.la $(LIB_KDECORE) $(LIB_KDEUI)
+testRate_SOURCES = testRate.cpp
+testRate_LDADD = ./libsolver.la $(LIB_KDECORE) $(LIB_KDEUI)
diff --git a/kmines/solver/advFastRules.cpp b/kmines/solver/advFastRules.cpp
new file mode 100644
index 00000000..79c42bba
--- /dev/null
+++ b/kmines/solver/advFastRules.cpp
@@ -0,0 +1,482 @@
+/*
+ * Copyright (c) 2001 Mikhail Kourinny ([email protected])
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include <algorithm>
+#include <assert.h>
+#include "adviseFast.h"
+
+using std::set;
+
+AdviseFast::RuleSet::RuleSet(FactSet *f) :
+ facts(f)
+{
+ FactSet::iterator i;
+ for(i=facts->begin(); i!=facts->end(); ++i)
+ addGeneral(i->first);
+}
+
+AdviseFast::RuleSet::~RuleSet(){
+}
+
+void AdviseFast::RuleSet::addRule(Entry const &entry)
+{
+ _rules.insert(entry);
+}
+
+bool AdviseFast::RuleSet::getSurePoint(Coord *sp)
+{
+ if(_surePoints.empty()){
+ if(!apply()) return false;
+ }
+
+ CoordSet::iterator i = _surePoints.begin();
+ *sp = *i;
+ _surePoints.erase(i);
+
+ return true;
+}
+
+bool AdviseFast::RuleSet::reveal(Coord what)
+{
+ CoordSet affectedFacts;
+ if(!facts->reveal(what, &affectedFacts))
+ // OOPS :(
+ return false;
+
+ CoordSet::iterator i;
+ for( i = affectedFacts.begin();
+ i != affectedFacts.end();
+ ++i)
+ this->addGeneral(*i);
+
+ return true;
+}
+
+void AdviseFast::RuleSet::solve()
+{
+ Coord p;
+ while(getSurePoint(&p)) {
+ bool res = reveal(p);
+ assert(res);
+ Q_UNUSED(res);
+ }
+}
+
+bool AdviseFast::RuleSet::apply()
+{
+ while(!_rules.empty()){
+ set<Entry>::iterator i = _rules.begin();
+ std::auto_ptr<Rule> r (this->newRule(*i));
+ _rules.erase(i);
+
+ if(r->apply(&this->_surePoints)) return true;
+ }
+
+ return false;
+}
+
+AdviseFast::Rule *
+AdviseFast::RuleSet::newRule(Entry const &e){
+ CoordSet::const_iterator i = e.second.begin();
+ Coord p, p1;
+ switch(e.first){
+ case EMPTY:
+ assert(e.second.size() == 1);
+ return new EmptyRule(*i, this);
+
+ case FULL:
+ assert(e.second.size() == 1);
+ return new FullRule(*i, this);
+
+ case INCLUDE:
+ assert(e.second.size() == 2);
+ p = *i; ++i; p1 = *i;
+ return new InclusionRule(p, p1, this);
+
+ case INCLUDE1:
+ assert(e.second.size() == 2);
+ p = *i; ++i; p1 = *i;
+ return new InclusionRule(p1, p, this);
+
+ case INTERSECT:
+ assert(e.second.size() == 2);
+ p = *i; ++i; p1 = *i;
+ return new IntersectionRule(p, p1, this);
+
+ case INTERSECT1:
+ assert(e.second.size() == 2);
+ p = *i; ++i; p1 = *i;
+ return new IntersectionRule(p1, p, this);
+
+ case GENERAL:
+ assert(e.second.size() == 1);
+ return new GeneralRule(*i, this);
+
+ default:
+ assert(false);
+ }
+
+ // Make compiler happy
+ return 0;
+}
+
+void AdviseFast::RuleSet::removeRef(Coord p){
+ set<Entry>::iterator i, j;
+
+ for( i = j = _rules.begin();
+ i != _rules.end();
+ i = j)
+ {
+ ++j;
+ if(i->second.count(p)) _rules.erase(i);
+ }
+}
+
+void AdviseFast::RuleSet::addGeneral(Coord p){
+ this->removeRef(p);
+ Entry e;
+ e.first = GENERAL;
+ e.second.insert(p);
+ this->addRule(e);
+}
+
+#if defined(DEBUG) && DEBUG >= 2
+int AdviseFast::Rule::leaks = 0;
+#endif
+
+AdviseFast::Rule::Rule(RuleSet *parent) :
+ _parent(parent),
+ _facts(parent->facts)
+{
+#if defined(DEBUG) && DEBUG >= 2
+ cout << "Rule::Rule, leaks = " << ++leaks << endl;
+#endif
+}
+
+AdviseFast::Rule::~Rule()
+{
+#if defined(DEBUG) && DEBUG >= 2
+ cout << "Rule::~Rule, leaks = " << --leaks << endl;
+#endif
+}
+
+AdviseFast::GeneralRule::GeneralRule(
+ Coord fact,
+ RuleSet *parent) :
+ Rule(parent),
+ _fact(fact)
+{}
+
+bool AdviseFast::GeneralRule::apply(CoordSet *)
+{
+
+#if defined(DEBUG) && DEBUG >= 2
+ operator <<(
+ cout << "Applying general rule ",
+ _fact) << endl;
+#endif
+
+ // Return if there's no more such fact
+ if(!_facts->count(_fact)) return false;
+ Fact const &f = (*_facts)[_fact];
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << f << endl;
+#endif
+
+ // Insert intersection rules first
+ // relatedFacts -- facts which have non-zero intersection
+ CoordSet relatedFacts;
+ {
+ CoordSet::const_iterator i;
+ for( i=f.pointSet.begin();
+ i!=f.pointSet.end();
+ ++i){
+
+ CoordSet const & ps =
+ *_facts->getContainingFacts(*i);
+ relatedFacts.insert(
+ ps.begin(), ps.end());
+ }
+ }
+ relatedFacts.erase(_fact); // ;)
+
+ CoordSet::iterator i;
+ for( i=relatedFacts.begin();
+ i!=relatedFacts.end();
+ ++i)
+ {
+ RuleSet::Entry e;
+ e.second.insert(_fact);
+ e.second.insert(*i);
+
+ e.first = RuleSet::INTERSECT1; _parent->addRule(e);
+ e.first = RuleSet::INTERSECT; _parent->addRule(e);
+ e.first = RuleSet::INCLUDE1; _parent->addRule(e);
+ e.first = RuleSet::INCLUDE; _parent->addRule(e);
+ }
+
+ // Now simple rules, so that they appear first in the list
+ RuleSet::Entry e; e.second.insert(_fact);
+ e.first = RuleSet::FULL; _parent->addRule(e);
+ e.first = RuleSet::EMPTY; _parent->addRule(e);
+
+ // No point revealed, so...
+ return false;
+}
+
+AdviseFast::EmptyRule::EmptyRule(
+ Coord fact,
+ RuleSet *parent) :
+ Rule(parent),
+ _fact(fact)
+{}
+
+bool AdviseFast::EmptyRule::apply(
+ CoordSet *surePoints)
+{
+
+#if defined(DEBUG) && DEBUG >= 2
+ operator <<(
+ cout << "Applying empty rule ",
+ _fact) << endl;
+#endif
+
+ if(!_facts->count(_fact)) return false;
+ Fact const &f = (*_facts)[_fact];
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << f << endl;
+#endif
+
+ // FactSet does not contain empty facts!!
+ assert(!f.pointSet.empty());
+
+ // If there are mines around, alas :(
+ if(f.mines) return false;
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << "succeeded!" << endl;
+#endif
+
+ surePoints->insert(
+ f.pointSet.begin(),
+ f.pointSet.end());
+
+ _parent->removeRef(_fact);
+
+ return true;
+}
+
+AdviseFast::FullRule::FullRule(
+ Coord fact,
+ RuleSet *parent) :
+ Rule(parent),
+ _fact(fact)
+{}
+
+bool AdviseFast::FullRule::apply(
+ CoordSet */*surePoints*/)
+{
+
+#if defined(DEBUG) && DEBUG >= 2
+ operator <<(
+ cout << "Applying full rule ",
+ _fact) << endl;
+#endif
+
+ if(!_facts->count(_fact)) return false;
+ Fact f = (*_facts)[_fact];
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << f << endl;
+#endif
+
+ // FactSet does not contain empty facts!!
+ assert(!f.pointSet.empty());
+
+ // The point set is not full of mines... :(
+ if(f.mines != (int)f.pointSet.size()) return false;
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << "succeeded!" << endl;
+#endif
+
+ CoordSet affectedFacts;
+ CoordSet::iterator i;
+ for( i=f.pointSet.begin();
+ i!=f.pointSet.end();
+ ++i)
+ _facts->mark(*i, &affectedFacts);
+
+ for( i=affectedFacts.begin();
+ i!=affectedFacts.end();
+ ++i)
+ _parent->addGeneral(*i);
+ _parent->removeRef(_fact);
+
+ // No mines revealed
+ return false;
+}
+
+AdviseFast::InclusionRule::InclusionRule(
+ Coord bigger, Coord smaller,
+ RuleSet *parent) :
+ Rule(parent),
+ _bigger(bigger), _smaller(smaller)
+{}
+
+bool AdviseFast::InclusionRule::apply(
+ CoordSet */*surePoints*/)
+{
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << "Applying inclusion rule ";
+ operator <<(cout, _bigger) << ' ';
+ operator <<(cout, _smaller) << endl;
+#endif
+
+ if(!_facts->count(_bigger)) return false;
+ if(!_facts->count(_smaller)) return false;
+
+ Fact b = (*_facts)[_bigger];
+ Fact s = (*_facts)[_smaller];
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << b << endl << s << endl;
+#endif
+
+ assert(!s.pointSet.empty());
+
+ CoordSet diff;
+ set_difference(
+ s.pointSet.begin(),
+ s.pointSet.end(),
+ b.pointSet.begin(),
+ b.pointSet.end(),
+ inserter(diff, diff.begin()));
+ if(!diff.empty())
+ // That is s is not included in b
+ return false;
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << "succeeded!" << endl;
+#endif
+
+ diff.clear();
+ set_difference(
+ b.pointSet.begin(),
+ b.pointSet.end(),
+ s.pointSet.begin(),
+ s.pointSet.end(),
+ inserter(diff, diff.begin()));
+
+ if(diff.empty()){
+ _facts->deleteFact(_bigger);
+ _parent->removeRef(_bigger);
+ } else {
+ b.pointSet = diff;
+ b.mines -= s.mines;
+ _facts->addFact(_bigger, b);
+ _parent->addGeneral(_bigger);
+ }
+
+ // No points revealed
+ return false;
+}
+
+AdviseFast::IntersectionRule::IntersectionRule(
+ Coord bigger, Coord smaller,
+ RuleSet *parent) :
+ Rule(parent),
+ _bigger(bigger), _smaller(smaller)
+{}
+
+bool AdviseFast::IntersectionRule::apply(
+ CoordSet *surePoints)
+{
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << "Applying intersection rule ";
+ operator <<(cout, _bigger) << ' ';
+ operator <<(cout, _smaller) << endl;
+#endif
+
+ if(!_facts->count(_bigger)) return false;
+ if(!_facts->count(_smaller)) return false;
+
+ Fact b = (*_facts)[_bigger];
+ Fact s = (*_facts)[_smaller];
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << b << endl << s << endl;
+#endif
+
+ CoordSet diff;
+ set_difference(
+ b.pointSet.begin(),
+ b.pointSet.end(),
+ s.pointSet.begin(),
+ s.pointSet.end(),
+ inserter(diff, diff.begin()));
+
+ if((int)diff.size() != b.mines - s.mines)
+ // Oops :(
+ return false;
+
+#if defined(DEBUG) && DEBUG >= 2
+ cout << "succeeded!" << endl;
+#endif
+
+ CoordSet cross, diffs;
+ set_difference(
+ s.pointSet.begin(),
+ s.pointSet.end(),
+ b.pointSet.begin(),
+ b.pointSet.end(),
+ inserter(diffs, diffs.begin()));
+ set_intersection(
+ s.pointSet.begin(),
+ s.pointSet.end(),
+ b.pointSet.begin(),
+ b.pointSet.end(),
+ inserter(cross, cross.begin()));
+
+ b.pointSet = diff;
+ b.mines -= s.mines;
+ _facts->addFact(_bigger, b);
+
+ s.pointSet = cross;
+ _facts->addFact(_smaller, s);
+
+ {
+ _parent->removeRef(_bigger);
+ _parent->addGeneral(_smaller);
+
+ RuleSet::Entry e;
+ e.first = RuleSet::FULL;
+ e.second.insert(_bigger);
+ _parent->addRule(e);
+ }
+
+ if(diffs.empty()) return false;
+
+ // Otherwise we have something to reveal!!
+ surePoints->insert(diffs.begin(), diffs.end());
+ return true;
+}
diff --git a/kmines/solver/adviseFast.cpp b/kmines/solver/adviseFast.cpp
new file mode 100644
index 00000000..f15d508e
--- /dev/null
+++ b/kmines/solver/adviseFast.cpp
@@ -0,0 +1,201 @@
+/*
+ * Copyright (c) 2001 Mikhail Kourinny ([email protected])
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "adviseFast.h"
+
+#include <algorithm>
+
+
+using namespace AdviseFast;
+
+std::ostream &AdviseFast::operator <<(std::ostream &s, Fact const &f)
+{
+ return s << f.pointSet << "= " << f.mines;
+}
+
+AdviseFast::FactSet::FactSet(BaseField *field) :
+ _field(field)
+{
+ Fact globalFact; globalFact.mines = field->nbMines();
+
+ int i, j;
+ for(i=field->height()-1; i>=0; --i)
+ for(j=field->width()-1; j>=0; --j){
+ Coord p(j, i);
+ // #### hasMine implies isCovered (and the solver should not
+ // know if there is a mine :) [NH]
+ if ( field->isCovered(p) /*|| field->hasMine(p)*/ )
+ globalFact.pointSet.insert(p);
+ else {
+ Fact f;
+ this->retrieveFact(p, &f);
+ this->addFact(p, f);
+ }
+ }
+
+ this->addFact(Coord(-1,-1), globalFact);
+}
+
+void AdviseFast::FactSet::retrieveFact(
+ Coord which,
+ Fact *where)
+{
+ where->mines = (_field->isCovered(which) ? -1
+ : (int)_field->nbMinesAround(which));
+ CoordList tmp = _field->coveredNeighbours(which);
+ for (CoordList::const_iterator it = tmp.begin(); it!=tmp.end(); ++it)
+ where->pointSet.insert(*it);
+}
+
+void AdviseFast::FactSet::addFact(
+ Coord const &point,
+ Fact const &fact)
+{
+ if(this->count(point)) this->deleteFact(point);
+
+ Fact &f = ((*this)[point] = fact);
+
+
+ // Remove marked points
+ CoordSet marked;
+ set_intersection(
+ f.pointSet.begin(),
+ f.pointSet.end(),
+ _marked.begin(),
+ _marked.end(),
+ inserter(marked, marked.begin()));
+
+ CoordSet::iterator i;
+ for(i=marked.begin(); i!=marked.end(); ++i)
+ f.pointSet.erase(*i);
+ f.mines -= marked.size();
+
+ // Don't insert empty fact
+ if(f.pointSet.empty()) { this->erase(point); return;}
+
+ for(i=f.pointSet.begin(); i!=f.pointSet.end(); ++i)
+ _containingFacts[*i].insert(point);
+}
+
+void AdviseFast::FactSet::deleteFact(
+ Coord const &point)
+{
+ if(!this->count(point)) return;
+ CoordSet::iterator i;
+ Fact &f = (*this)[point];
+ for(i=f.pointSet.begin(); i!=f.pointSet.end(); ++i){
+ _containingFacts[*i].erase(point);
+ if(_containingFacts[*i].empty())
+ _containingFacts.erase(*i);
+ }
+ this->erase(point);
+}
+
+bool AdviseFast::FactSet::reveal(
+ Coord point,
+ CoordSet *affectedFacts)
+{
+ // Tolerate :)
+ if( !_field->isCovered(point) ) return true; // :)
+
+ CoordList tmp;
+ if(_field->doReveal(point, &tmp, 0) == false)
+ // Blew up :(
+ return false;
+
+ CoordSet autorevealed;
+ for (CoordList::const_iterator it = tmp.begin(); it!=tmp.end(); ++it)
+ autorevealed.insert(*it);
+ autorevealed.insert(point);
+ affectedFacts->insert(autorevealed.begin(), autorevealed.end());
+
+ CoordSet::const_iterator i;
+ for(i=autorevealed.begin(); i!=autorevealed.end(); ++i)
+ {
+ // I still think that each poing will belong to
+ // at least one fact, but don't want to waste time
+ // proving it :)
+ if(_containingFacts.count(*i)){
+ CoordSet const &affF = _containingFacts[*i];
+ affectedFacts->insert(
+ affF.begin(), affF.end());
+ for(CoordSet::const_iterator j=affF.begin();
+ j!=affF.end();
+ ++j)
+ {
+ (*this)[*j].pointSet.erase(*i);
+ if((*this)[*j].pointSet.empty())
+ this->erase(*j);
+ }
+ _containingFacts.erase(*i);
+ }
+
+ Fact f; retrieveFact(*i, &f);
+ this->addFact(*i, f);
+ }
+
+ return true;
+}
+
+void AdviseFast::FactSet::mark(
+ Coord point,
+ CoordSet *affectedFacts)
+{
+ if(_marked.count(point)) return;
+ _marked.insert(point);
+
+ // I still think that each poing will belong to
+ // at least one fact, but don't want to waste time
+ // proving it :)
+ if(_containingFacts.count(point)){
+ CoordSet const &affF = _containingFacts[point];
+ affectedFacts->insert(affF.begin(), affF.end());
+ for(CoordSet::const_iterator i=affF.begin(); i!=affF.end(); ++i){
+ (*this)[*i].pointSet.erase(point);
+ (*this)[*i].mines--;
+ if((*this)[*i].pointSet.empty())
+ this->erase(*i);
+ }
+ _containingFacts.erase(point);
+ }
+
+ _field->doMark(point);
+}
+
+CoordSet const *AdviseFast::FactSet::getContainingFacts(
+ Coord const &point) const
+{
+ if(_containingFacts.count(point))
+ return &const_cast<std::map<Coord, CoordSet> &>(_containingFacts)
+ [point];
+ else return 0;
+}
+
+std::ostream &AdviseFast::operator <<(std::ostream &s, FactSet const &fs)
+{
+ FactSet::const_iterator i;
+ for(i=fs.begin(); i!=fs.end(); ++i)
+ s << i->first << ": " << i->second << endl;
+ return s;
+}
+
+bool AdviseFast::adviseFast(
+ Coord *,
+ FactSet *,
+ RuleSet *)
+{ return false;}
diff --git a/kmines/solver/adviseFast.h b/kmines/solver/adviseFast.h
new file mode 100644
index 00000000..db3b1955
--- /dev/null
+++ b/kmines/solver/adviseFast.h
@@ -0,0 +1,70 @@
+/*
+ * Copyright (c) 2001 Mikhail Kourinny ([email protected])
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef adviseFast_h
+#define adviseFast_h
+
+#include "headerP.h"
+
+
+namespace AdviseFast {
+
+ class GeneralRule : public Rule {
+ public:
+ GeneralRule(Coord fact, RuleSet *rules);
+ virtual bool apply(CoordSet *surePoints);
+ private:
+ Coord _fact;
+ };
+
+ class EmptyRule : public Rule {
+ public:
+ EmptyRule(Coord fact, RuleSet *rules);
+ virtual bool apply(CoordSet *surePoints);
+ private:
+ Coord _fact;
+ };
+
+ class FullRule : public Rule {
+ public:
+ FullRule(Coord fact, RuleSet *rules);
+ virtual bool apply(CoordSet *surePoints);
+ private:
+ Coord _fact;
+ };
+
+ class InclusionRule : public Rule {
+ public:
+ InclusionRule(Coord bigger, Coord smaller,
+ RuleSet *rules);
+ virtual bool apply(CoordSet *surePoints);
+ private:
+ Coord _bigger, _smaller;
+ };
+
+ class IntersectionRule : public Rule {
+ public:
+ IntersectionRule(Coord bigger, Coord smaller,
+ RuleSet *rules);
+ virtual bool apply(CoordSet *surePoints);
+ private:
+ Coord _bigger, _smaller;
+ };
+}
+
+#endif
diff --git a/kmines/solver/adviseFull.cpp b/kmines/solver/adviseFull.cpp
new file mode 100644
index 00000000..815ff02c
--- /dev/null
+++ b/kmines/solver/adviseFull.cpp
@@ -0,0 +1,655 @@
+/*
+ * Copyright (c) 2001 Mikhail Kourinny ([email protected])
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "adviseFull.h"
+#include <assert.h>
+#include <stdio.h>
+#include <math.h>
+
+using std::list;
+using std::map;
+using std::set;
+using namespace AdviseFull;
+
+AdviseFull::EquationSet::EquationSet() :
+ _maxPointSet(0)
+{}
+
+AdviseFull::EquationSet::EquationSet(
+ AdviseFast::FactSet const &facts) :
+ _maxPointSet(0)
+{
+ AdviseFast::FactSet::const_iterator i;
+ for(i=facts.begin(); i!=facts.end(); ++i, ++_maxPointSet){
+ Equation e;
+ e.pointSets.insert(_maxPointSet);
+ e.mines = i->second.mines;
+ _equations.push_back(e);
+
+ _pointSets[_maxPointSet] = i->second.pointSet;
+ }
+}
+
+void AdviseFull::EquationSet::normalize()
+{
+ short i=0;
+ set<short> empty;
+ for(i=0; i<_maxPointSet; ++i){
+ if(!_pointSets.count(i)) continue;
+ if(_pointSets[i].empty()){
+ this->substitute(i, empty);
+ continue;
+ }
+ for(short j=i+1;j<_maxPointSet; ++j){
+ if(!_pointSets.count(j)) continue;
+ if(_pointSets[j].empty()){
+ this->substitute(j, empty);
+ continue;
+ }
+
+ CoordSet intersect;
+ set_intersection(
+ _pointSets[i].begin(),
+ _pointSets[i].end(),
+ _pointSets[j].begin(),
+ _pointSets[j].end(),
+ inserter(intersect, intersect.begin()));
+ if(intersect.empty()) continue;
+
+ CoordSet _i, _j;
+ set_difference(
+ _pointSets[i].begin(),
+ _pointSets[i].end(),
+ _pointSets[j].begin(),
+ _pointSets[j].end(),
+ inserter(_i, _i.begin()));
+ set_difference(
+ _pointSets[j].begin(),
+ _pointSets[j].end(),
+ _pointSets[i].begin(),
+ _pointSets[i].end(),
+ inserter(_j, _j.begin()));
+
+ set<short> _ip, _jp;
+ _ip.insert(_maxPointSet);
+ _jp.insert(_maxPointSet);
+ _pointSets[_maxPointSet++] = intersect;
+ _ip.insert(_maxPointSet);
+ _pointSets[_maxPointSet++] = _i;
+ _jp.insert(_maxPointSet);
+ _pointSets[_maxPointSet++] = _j;
+
+ this->substitute(i, _ip);
+ this->substitute(j, _jp);
+ break;
+ }
+ }
+}
+
+void AdviseFull::EquationSet::separate(
+ list<EquationSet> *result) const
+{
+ result->clear(); // :)
+
+ list<Equation> equations = _equations;
+
+ while(!equations.empty()){
+ // Add a new equation set to *results
+ result->push_back(EquationSet());
+ EquationSet &workingSet = result->back();
+ workingSet._maxPointSet = _maxPointSet;
+
+ // Start iteration process
+ // recentlyDeceased is a set of pointSets added on the
+ // last iteration
+ workingSet._equations.push_back(equations.front());
+ set<short> recentlyDeceased = equations.front().pointSets;
+ equations.pop_front();
+
+ // The iteration process
+ while(!recentlyDeceased.empty()){
+
+ // Temporary set<short>
+ set<short> rd;
+
+ list<Equation>::iterator i = equations.begin();
+ while(i != equations.end()){
+ set<short> intersect;
+ set_intersection(
+ i->pointSets.begin(),
+ i->pointSets.end(),
+ recentlyDeceased.begin(),
+ recentlyDeceased.end(),
+ inserter(intersect, intersect.begin()));
+ if(intersect.empty()){
+ ++i;
+ } else {
+ set_difference(
+ i->pointSets.begin(),
+ i->pointSets.end(),
+ intersect.begin(),
+ intersect.end(),
+ inserter(rd, rd.begin()));
+ workingSet._equations.push_back(*i);
+ i = equations.erase(i);
+ }
+ }
+
+ // Now switch recentlyDeceased
+ set<short>::iterator j;
+ for( j = recentlyDeceased.begin();
+ j != recentlyDeceased.end();
+ ++j)
+ {
+ workingSet._pointSets[*j] =
+ (const_cast<
+ map<short, CoordSet> &>(
+ _pointSets))[*j];
+ }
+
+ recentlyDeceased = rd;
+ }
+ }
+}
+
+map<short, CoordSet> const &AdviseFull::EquationSet::solve(
+ list<Solution> *results) const
+{
+
+#ifdef DEBUG
+ printf("Entering EquationSet::solve\n");
+ prettyprint();
+#endif
+
+ EquationSet eqs = *this;
+
+ // Get the most evident solutions
+ Solution only;
+ list<Equation> &EQS = eqs._equations;
+
+ bool success;
+ do {
+
+ success = false;
+ list<Equation>::iterator i = EQS.begin();
+
+ while(i!=EQS.end()){
+#if defined(DEBUG) && DEBUG >= 2
+ printf("Taking look at the equation...\n");
+#endif
+ // Substitute known values
+ { set<short>::iterator j;
+ set<short> known;
+ for( j = i->pointSets.begin();
+ j != i->pointSets.end();
+ ++j)
+ {
+ if(only.count(*j)){
+ i->mines -= only[*j];
+ known.insert(*j);
+ }
+ }
+
+ // STL bug ??
+ for( j = known.begin();
+ j != known.end();
+ ++j)
+ i->pointSets.erase(*j);
+ }
+ // From now on the equation has no known values
+#if defined(DEBUG) && DEBUG >= 2
+ printf("Substituted known values.\n");
+#endif
+ if(i->mines < 0)
+ // Discrepancy
+ return _pointSets;
+
+
+ if(i->pointSets.empty()){
+#if defined(DEBUG) && DEBUG >= 2
+ printf("Empty equation.\n");
+#endif
+ if(i->mines){
+ // No points, non-zero mine count
+ // No solution
+ return _pointSets;
+ } else {
+ i = EQS.erase(i);
+ continue;
+ }
+ }
+
+ if(i->mines == 0){
+ set<short>::iterator j;
+ for(
+ j=i->pointSets.begin();
+ j!=i->pointSets.end();
+ ++j)
+ only[*j] = 0;
+
+ EQS.erase(i);
+ success = true;
+ break;
+ }
+
+ if(i->pointSets.size() == 1){
+ short j = *i->pointSets.begin();
+
+ if((int)eqs._pointSets[j].size() < i->mines)
+ // Discrepancy !!
+ return _pointSets;
+
+ only[j] = i->mines;
+
+ EQS.erase(i);
+ success = true;
+ break;
+ }
+
+ ++i;
+ }
+
+ } while(success);
+
+ // If no equations left we have a unique solution
+ if(EQS.empty()){
+#ifdef DEBUG
+ printf("Got a single solution!\n");
+#endif
+ results->push_back(only);
+ return _pointSets;
+ }
+
+ // Otherwise the first equation is not empty.
+ // Find the range for first element
+ short var = *EQS.begin()->pointSets.begin();
+ std::pair<short, short> range;
+ range.first = 0;
+ range.second = eqs._pointSets[var].size();
+
+ // A list of equations containing var
+ list<list<Equation>::iterator> containers;
+ list<Equation>::iterator i;
+ for( i = EQS.begin();
+ i != EQS.end();
+ ++i)
+ {
+ if(i->pointSets.count(var)){
+ i->pointSets.erase(var);
+ containers.push_back(i);
+
+ if(i->mines < range.second)
+ range.second = i->mines;
+
+ // The total size of other point sets
+ // in the equation
+ short totalsize = 0;
+ set<short>::iterator j;
+ for( j = i->pointSets.begin();
+ j != i->pointSets.end();
+ ++j)
+ totalsize += eqs._pointSets[*j].size();
+
+ if(range.first < i->mines - totalsize)
+ range.first = i->mines - totalsize;
+ }
+ }
+ // Found the range
+
+ // Now set properly equation set for first recursion
+ list<list<Equation>::iterator>::iterator super_iter; // ;)
+ short varvalue = range.first;
+ for( super_iter = containers.begin();
+ super_iter != containers.end();
+ ++super_iter)
+ (*super_iter)->mines -= varvalue;
+
+ // Recursive calls here
+ while(varvalue <= range.second){
+ only[var] = varvalue;
+ list<Solution> tempResults;
+ eqs.solve(&tempResults);
+
+ // Mix solutions with only and put them
+ // in *results
+ list<Solution>::iterator j;
+ for( j=tempResults.begin();
+ j!=tempResults.end();
+ ++j)
+ {
+ j->insert(only.begin(), only.end());
+ results->push_back(*j);
+ }
+
+ // Prepare next recursive call
+ ++varvalue;
+ for( super_iter = containers.begin();
+ super_iter != containers.end();
+ ++super_iter)
+ --(*super_iter)->mines;
+ }
+
+ return _pointSets;
+}
+
+void AdviseFull::EquationSet::prettyprint() const
+{
+
+#if defined(DEBUG)
+ printf("Point Sets:\n");
+ map<short, CoordSet>::const_iterator i;
+ for(i=_pointSets.begin(); i!=_pointSets.end(); ++i){
+ printf("%d:", i->first);
+ CoordSet::const_iterator j;
+ for(j=i->second.begin(); j!=i->second.end(); ++j)
+ printf("\t(%d,%d)\n", j->second, j->first);
+ }
+#endif
+
+ printf("Equations:\n");
+ list<Equation>::const_iterator l;
+ for(l=_equations.begin(); l!=_equations.end(); ++l){
+ set<short>::const_iterator j;
+ for(j=l->pointSets.begin(); j!=l->pointSets.end(); ++j)
+ printf("%d ", *j);
+ printf("= %d\n", l->mines);
+ }
+}
+
+void AdviseFull::EquationSet::substitute(
+ short out,
+ set<short> const &in)
+{
+ list<Equation>::iterator i;
+ for( i = _equations.begin();
+ i != _equations.end();
+ ++i)
+ {
+ if(i->pointSets.count(out)){
+ i->pointSets.erase(out);
+ i->pointSets.insert(in.begin(), in.end());
+ }
+ }
+
+ _pointSets.erase(out);
+}
+
+bool AdviseFull::surePoints(
+ map<short, CoordSet> const &m,
+ list<EquationSet::Solution> const &l,
+ CoordSet *surePoints)
+{
+ // A set of candidates to be surePoints
+ list<short> sp;
+ {
+ map<short, CoordSet>::const_iterator i;
+ for(i=m.begin(); i!=m.end(); ++i) sp.push_back(i->first);
+ }
+
+ // Scan solution list
+ list<EquationSet::Solution>::const_iterator i;
+ for(i=l.begin(); i!=l.end(); ++i){
+ list<short>::iterator j = sp.begin();
+ while(j != sp.end()){
+ // Non-empty possibility
+ if((const_cast<EquationSet::Solution &>(*i))[*j]){
+ j = sp.erase(j);
+ if(sp.empty()) // No candidates left
+ return false;
+ } else // Stay alive for now
+ ++j;
+ }
+ }
+
+ // There are SOME sure points;
+ // Fill *surePoints
+ list<short>::iterator isp;
+ map<short, CoordSet> &mm = const_cast<map<short, CoordSet> &>(m);
+ for(isp = sp.begin(); isp != sp.end(); ++isp)
+ surePoints->insert(mm[*isp].begin(), mm[*isp].end());
+
+ return true;
+}
+
+float AdviseFull::variantNumberFraction(
+ map<short, CoordSet> const &m,
+ EquationSet::Solution const &dividend,
+ EquationSet::Solution const &divisor,
+ float fraction)
+{
+ short count_difference = 0;
+ float quotient = 1;
+
+ EquationSet::Solution::const_iterator i;
+ for(i=divisor.begin(); i!=divisor.end(); ++i){
+ int j = i->first;
+ assert(m.count(j));
+ int size = (const_cast<map<short, CoordSet> &>(m))[j].size();
+ int dvd = (const_cast<EquationSet::Solution &>(dividend))[j];
+ int dvr = (const_cast<EquationSet::Solution &>(divisor))[j];
+
+ count_difference += dvd - dvr;
+
+ if(dvd < dvr){
+ dvr = size - dvr;
+ dvd = size - dvd;
+ }
+ while(dvr < dvd) {
+ float num = size-dvr++;
+ quotient *= num/dvr;
+ }
+ }
+
+ // Sorry, expensive call, but I'm lazy :((
+ if(count_difference){
+ assert(fraction != 0.);
+#if defined(DEBUG)
+ float correction = pow( fraction/(1-fraction), count_difference );
+ cout << "Got into correction, " <<
+ count_difference << ' ' << correction << endl;
+#endif
+ quotient *= pow( (1-fraction)/fraction , -count_difference );
+ }
+
+#if defined(DEBUG) && DEBUG >= 2
+ printf("variantNumberFraction: %.02f.\n", quotient);
+#endif
+
+ return quotient;
+}
+
+void AdviseFull::getProbabilities(
+ map<short, CoordSet> const &m,
+ list<EquationSet::Solution> const &l,
+ ProbabilityMap *probabilities,
+ float fraction)
+{
+ assert(!l.empty());
+ EquationSet::Solution const &front = l.front();
+
+ float probabilitiesSum = 0;
+ map<short, float> probs;
+ { map<short, CoordSet>::const_iterator i;
+ for(i=m.begin(); i!=m.end(); ++i)
+ probs[i->first] = 0;
+ }
+
+ list<EquationSet::Solution>::const_iterator i;
+ for(i=l.begin(); i!=l.end(); ++i){
+ float frac = variantNumberFraction(m, *i, front, fraction);
+ EquationSet::Solution::const_iterator j;
+ for(j=i->begin(); j!=i->end(); ++j)
+ probs[j->first] += j->second*frac;
+ probabilitiesSum += frac;
+ }
+
+ probabilities->clear();
+
+ map<short, float>::iterator j;
+ for(j=probs.begin(); j!= probs.end(); ++j){
+ CoordSet const &ps = const_cast<map<short, CoordSet> &>(m)[j->first];
+ j->second /= ps.size() * probabilitiesSum;
+ CoordSet::const_iterator k;
+ for(k=ps.begin(); k!=ps.end(); ++k)
+ probabilities->insert(
+ std::pair<float, Coord>(j->second, *k));
+ }
+
+ // That's it :)
+}
+
+void AdviseFull::adviseFull(
+ AdviseFast::FactSet *facts,
+ CoordSet *surePoints,
+ ProbabilityMap *probabilities)
+{
+ EquationSet eqs(*facts);
+
+#if defined(DEBUG) && DEBUG >= 2
+ eqs.prettyprint();
+#endif
+
+ eqs.normalize();
+#if defined(DEBUG) && DEBUG >= 2
+ eqs.prettyprint();
+#endif
+
+ list<EquationSet> eqss;
+ eqs.separate(&eqss);
+#ifdef DEBUG
+ {list<EquationSet>::iterator i;
+ for(i=eqss.begin(); i!=eqss.end(); ++i)
+ i->prettyprint();
+ }
+#endif
+
+
+ // OK, uneffective, but simple :(
+ surePoints->clear();
+ probabilities->clear();
+
+ // Get a fraction;
+ float fraction;
+ { BaseField const *f = facts->getField();
+ fraction = ((float)f->nbMines()) / (f->width() * f->height());
+ }
+
+ /* From now on the first equation set on the list includes
+ * the equation corresponding to "total" fact. This is the
+ * first equation on the set.
+ *
+ * Give it a special treatment ;) */
+ if(!eqss.empty()) do {
+ EquationSet prime = eqss.front();
+ EquationSet::Equation total = prime._equations.front();
+ prime._equations.pop_front();
+
+ list<EquationSet> prime_sep;
+ prime.separate(&prime_sep);
+
+ // Find a pool
+ list<EquationSet::Equation>::iterator i = prime._equations.begin();
+ while(!prime._equations.empty()){
+ set<short>::iterator j;
+ for( j = i->pointSets.begin();
+ j != i->pointSets.end();
+ ++j)
+ prime._pointSets.erase(*j);
+ i = prime._equations.erase(i);
+ }
+
+ assert(prime._pointSets.size() <= 1);
+ if(prime._pointSets.size() == 0) break;
+
+ short pool = prime._pointSets.begin()->first;
+ CoordSet const &p = prime._pointSets[pool];
+#ifdef DEBUG
+ cout << "Prime equation set:" << endl <<
+ " separated into " << prime_sep.size() << endl <<
+ " pool size is " << p.size() << endl;
+#endif
+ // Euristic
+ // if( prime_sep.size () > 6 && p.size() >= prime_sep.size() * 10){
+ if(p.size() < (prime_sep.size()+1) * 10)
+ // No special treatment!!
+ break;
+
+
+ // Actually, just substitute prime (!!!)
+ eqss.pop_front();
+ eqss.insert(eqss.begin(),
+ prime_sep.begin(),
+ prime_sep.end());
+
+ prime._equations.clear();
+ EquationSet::Equation o;
+ o.pointSets.insert(pool);
+ // #### is the convertion right ? (NH)
+ o.mines = (ushort)(fraction * p.size());
+ // A precaution
+ if(o.mines == 0) o.mines = 1; // ;)
+
+ prime._equations.push_front(o);
+ eqss.push_front(prime);
+
+
+#ifdef DEBUG
+ cout << "Specially treated:" << endl;
+ {
+ list<EquationSet>::iterator i;
+ for(i=eqss.begin(); i!=eqss.end(); ++i)
+ i->prettyprint();
+ }
+#endif
+ } while (false);
+
+ list<EquationSet>::const_iterator i;
+ for(i=eqss.begin(); i!=eqss.end(); ++i){
+ CoordSet sp; ProbabilityMap pb;
+
+ list<EquationSet::Solution> solutions;
+ map<short, CoordSet> const &m = i->solve(&solutions);
+#ifdef DEBUG
+ printf("Got solutions.\n");
+#if defined(DEBUG) && DEBUG >= 2
+ { list<EquationSet::Solution>::iterator i;
+ for( i = solutions.begin();
+ i != solutions.end();
+ ++i)
+ {
+ EquationSet::Solution::iterator j;
+ for(j=i->begin(); j!=i->end(); ++j)
+ printf("%d:\t%d\n",
+ j->first, j->second);
+ printf("\n");
+ }
+ }
+#endif
+#endif
+
+ //bool sure =
+ AdviseFull::surePoints(m, solutions, &sp);
+ surePoints->insert(sp.begin(), sp.end());
+
+ getProbabilities(m, solutions, &pb, fraction);
+ probabilities->insert(pb.begin(), pb.end());
+ }
+
+ // That's it
+ return;
+}
diff --git a/kmines/solver/adviseFull.h b/kmines/solver/adviseFull.h
new file mode 100644
index 00000000..2b0cc97b
--- /dev/null
+++ b/kmines/solver/adviseFull.h
@@ -0,0 +1,93 @@
+/*
+ * Copyright (c) 2001 Mikhail Kourinny ([email protected])
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __ADVISE_FULL_H
+#define __ADVISE_FULL_H
+
+#include <list>
+#include <algorithm>
+
+#include "headerP.h"
+
+
+namespace AdviseFull {
+ class EquationSet {
+ public: // Well, why is it necessary?
+ struct Equation {
+ std::set<short> pointSets;
+ short mines;
+ };
+ typedef std::map<short, short> Solution;
+
+ public:
+ EquationSet();
+ EquationSet(AdviseFast::FactSet const &facts);
+
+ std::list<Equation> _equations;
+ std::map<short, CoordSet> _pointSets;
+
+ /** Make sure no _pointSets have
+ * non-empty intersection */
+ void normalize();
+
+ /** Returns in *results a set of equation sets
+ * which can be solved separately.
+ * *this assumed normalized :) */
+ void separate(std::list<EquationSet> *results) const;
+
+ /** Solves... returns _pointSets.
+ * It's nice to have *this separated :) */
+ std::map<short, CoordSet> const &solve(
+ std::list<Solution> *results) const;
+
+ void prettyprint() const;
+
+ private:
+ /** One more than max(_pointSets[i].first) */
+ short _maxPointSet;
+
+ /** Substitutes a pointSet in all equations */
+ void substitute(
+ short out,
+ std::set<short> const &in);
+ };
+
+ bool surePoints(
+ std::map<short, CoordSet> const &m,
+ std::list<EquationSet::Solution> const &l,
+ CoordSet *surePoints);
+
+ /** The fourth argument is a fraction of mines in the "pool" */
+ void getProbabilities(
+ std::map<short, CoordSet> const &m,
+ std::list<EquationSet::Solution> const &l,
+ ProbabilityMap *probabilities,
+ float fraction = 0);
+
+ /** Get the quotient of the number of variants of
+ * point distribution satisfying dividend and divisor
+ * solutions */
+ /** The fourth argument is a fraction of mines in the "pool" */
+ float variantNumberFraction(
+ std::map<short, CoordSet> const &m,
+ EquationSet::Solution const &dividend,
+ EquationSet::Solution const &divisor,
+ float fraction = 0);
+}
+
+#endif
diff --git a/kmines/solver/bfield.cpp b/kmines/solver/bfield.cpp
new file mode 100644
index 00000000..d6c03643
--- /dev/null
+++ b/kmines/solver/bfield.cpp
@@ -0,0 +1,221 @@
+/*
+ * Copyright (c) 1996-2002 Nicolas HADACEK ([email protected])
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "bfield.h"
+
+
+using namespace KGrid2D;
+
+BaseField::BaseField(long seed)
+ : _nbUncovered(0), _nbMarked(0), _nbUncertain(0), _random(seed)
+{}
+
+CoordList BaseField::coveredNeighbours(const Coord &p) const
+{
+ CoordList n;
+ CoordList tmp = neighbours(p);
+ for (CoordList::const_iterator it=tmp.begin(); it!=tmp.end(); ++it)
+ if ( state(*it)!=Uncovered ) n.append(*it);
+ return n;
+}
+
+uint BaseField::nbMinesAround(const Coord &p) const
+{
+ uint nb = 0;
+ CoordList n = neighbours(p);
+ for (CoordList::const_iterator it=n.begin(); it!=n.end(); ++it)
+ if ( hasMine(*it) ) nb++;
+ return nb;
+}
+
+void BaseField::reset(uint width, uint height, uint nbMines)
+{
+ _firstReveal = true;
+ _nbMarked = 0;
+ _nbUncertain = 0;
+ _nbUncovered = 0;
+ _nbMines = nbMines;
+
+ Case tmp;
+ tmp.mine = false;
+ tmp.state = Covered;
+ resize(width, height);
+ fill(tmp);
+}
+
+bool BaseField::checkField(uint w, uint h, uint nb, const QString &s)
+{
+ if ( s.length()!=w*h ) return false;
+ uint n = 0;
+ unsigned int strLength(s.length());
+ for (uint i=0; i<strLength; i++)
+ if ( s[i]=="1" ) n++;
+ else if ( s[i]!="0" ) return false;
+ return ( n==nb );
+}
+
+void BaseField::initReplay(const QString &s)
+{
+ Q_ASSERT( checkField(width(), height(), _nbMines, s) );
+
+ _firstReveal = false;
+
+ Case tmp;
+ tmp.state = Covered;
+ unsigned int strLength(s.length());
+ for (uint i=0; i<strLength; i++) {
+ tmp.mine = ( s[i]=="1" );
+ at(i) = tmp;
+ }
+}
+
+void BaseField::changeState(KMines::CaseState state, int inc)
+{
+ switch (state) {
+ case Uncovered: _nbUncovered += inc; break;
+ case Uncertain: _nbUncertain += inc; break;
+ case Marked: _nbMarked += inc; break;
+ default: break;
+ }
+}
+
+void BaseField::changeCase(const Coord &p, KMines::CaseState newState)
+{
+ changeState(state(p), -1);
+ changeState(newState, 1);
+ (*this)[p].state = newState;
+}
+
+void BaseField::uncover(const Coord &p, CoordList *autorevealed)
+{
+ if ( state(p)!=Covered ) return;
+ changeCase(p, Uncovered);
+
+ if ( nbMinesAround(p)==0 ) {
+ CoordList n = coveredNeighbours(p);
+ if (autorevealed) *autorevealed += n;
+ for (CoordList::const_iterator it=n.begin(); it!=n.end(); ++it)
+ uncover(*it, autorevealed);
+ }
+}
+
+void BaseField::showAllMines(bool won)
+{
+ for (uint i=0; i<size(); i++) {
+ Coord p = coord(i);
+ if ( hasMine(p) && state(p)!=Exploded && state(p)!=Marked ) {
+ changeCase(p, won ? Marked : Uncovered);
+ if ( !won ) _nbUncovered--; // not an empty case ...
+ }
+ }
+}
+
+bool BaseField::autoReveal(const Coord &p, bool *caseUncovered)
+{
+ if ( state(p)!=Uncovered ) return true;
+
+ uint nb = nbMinesAround(p);
+ CoordList n = neighbours(p);
+ for (CoordList::const_iterator it=n.begin(); it!=n.end(); ++it)
+ if ( state(*it)==Marked ) nb--;
+ if ( nb==0 ) // number of surrounding mines == number of marks :)
+ for (CoordList::const_iterator it=n.begin(); it!=n.end(); ++it)
+ if ( !reveal(*it, 0, caseUncovered) ) return false;
+ return true;
+}
+
+bool BaseField::reveal(const Coord &p, CoordList *autorevealed,
+ bool *caseUncovered)
+{
+ if ( state(p)!=Covered ) return true;
+
+ if (_firstReveal) {
+ _firstReveal = false;
+ // set mines positions on field ; must avoid the first
+ // revealed case
+ uint n = size() - 1; // minus one case free
+ Q_ASSERT( _nbMines<n );
+ for(uint k=0; k<_nbMines; k++) {
+ uint pos = _random.getLong(n - k);
+ uint i = 0;
+ Coord tmp;
+ for (;;) {
+ tmp = coord(i);
+ if ( !(tmp==p) && !hasMine(tmp) ) {
+ if ( pos==0 ) break;
+ pos--;
+ }
+ i++;
+ }
+ (*this)[tmp].mine = true;
+ }
+ }
+
+ if ( !hasMine(p) ) {
+ uncover(p, autorevealed);
+ if (caseUncovered) *caseUncovered = true;
+ return true;
+ }
+
+ // explosion
+ changeCase(p, Exploded);
+
+ // find all errors
+ for (uint i=0; i<size(); i++) {
+ Coord p = coord(i);
+ if ( state(p)==Marked && !hasMine(p) ) changeCase(p, Error);
+ }
+ return false;
+}
+
+void BaseField::completeReveal()
+{
+ for (;;) {
+ bool changed = false;
+ for (uint i=0; i<size(); i++) {
+ Coord c = coord(i);
+ if ( state(c)!=Uncovered ) continue;
+ autoReveal(c, &changed);
+ uint nb = nbMinesAround(c);
+ CoordList n = neighbours(c);
+ for (CoordList::const_iterator it=n.begin(); it!=n.end(); ++it)
+ if ( state(*it)!=Uncovered ) nb--;
+ if (nb) continue;
+ for (CoordList::const_iterator it=n.begin(); it!=n.end(); ++it)
+ if ( state(*it)!=Uncovered && state(*it)!=Marked ) {
+ changed = true;
+ changeCase(*it, Marked);
+ }
+ }
+ if ( !changed ) break;
+ }
+}
+
+void BaseField::doMark(const Coord &c)
+{
+ if ( state(c)!=Covered ) return;
+ changeCase(c, Marked);
+}
+
+QCString BaseField::string() const
+{
+ QCString s(size());
+ for (uint i=0; i<size(); i++)
+ s[i] = (hasMine(coord(i)) ? '1' : '0');
+ return s;
+}
diff --git a/kmines/solver/bfield.h b/kmines/solver/bfield.h
new file mode 100644
index 00000000..9c91d41c
--- /dev/null
+++ b/kmines/solver/bfield.h
@@ -0,0 +1,83 @@
+/*
+ * Copyright (c) 1996-2002 Nicolas HADACEK ([email protected])
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef BASE_FIELD_H
+#define BASE_FIELD_H
+
+#include <qcstring.h>
+
+#include <krandomsequence.h>
+#include <kgrid2d.h>
+
+#include "defines.h"
+
+
+class BaseField : public KGrid2D::Square<KMines::Case>, public KMines
+{
+ public:
+ // seed for KRandomSequence (used by solver check programs)
+ BaseField(long seed = 0);
+ virtual ~BaseField() {}
+
+ void reset(uint width, uint height, uint nbMines);
+ static bool checkField(uint width, uint height, uint nbMines,
+ const QString &field);
+ void initReplay(const QString &field); // string == "0100011011000101..."
+
+// --------------------------
+// interface used by the solver
+ uint nbMines() const { return _nbMines; }
+ bool isCovered(const KGrid2D::Coord &p) const
+ { return ( state(p)!=KMines::Uncovered ); }
+ uint nbMinesAround(const KGrid2D::Coord &) const;
+ KGrid2D::CoordList coveredNeighbours(const KGrid2D::Coord &p) const;
+ bool isSolved() const { return (size() - _nbUncovered)==_nbMines; }
+
+ // return false if the case revealed contains a mine.
+ virtual bool doReveal(const KGrid2D::Coord &c,
+ KGrid2D::CoordList *autorevealed, bool *caseUncovered)
+ { return reveal(c, autorevealed, caseUncovered); }
+ virtual void doMark(const KGrid2D::Coord &);
+// -------------------------
+
+ uint nbMarked() const { return _nbMarked; }
+ QCString string() const;
+
+ void showAllMines(bool won);
+
+ protected:
+ bool firstReveal() const { return _firstReveal; }
+ KMines::CaseState state(const KGrid2D::Coord &p) const
+ { return (*this)[p].state; }
+ bool hasMine(const KGrid2D::Coord &p) const { return (*this)[p].mine; }
+ virtual void changeCase(const KGrid2D::Coord &, KMines::CaseState);
+ bool reveal(const KGrid2D::Coord &c,
+ KGrid2D::CoordList *autorevealed, bool *caseUncovered);
+ bool autoReveal(const KGrid2D::Coord &, bool *caseUncovered);
+ void completeReveal();
+
+ private:
+ bool _firstReveal;
+ uint _nbUncovered, _nbMarked, _nbUncertain, _nbMines;
+ KRandomSequence _random;
+
+ void uncover(const KGrid2D::Coord &, KGrid2D::CoordList *autoreveal);
+ void changeState(KMines::CaseState, int increment);
+};
+
+#endif
diff --git a/kmines/solver/headerP.h b/kmines/solver/headerP.h
new file mode 100644
index 00000000..984e3113
--- /dev/null
+++ b/kmines/solver/headerP.h
@@ -0,0 +1,191 @@
+/*
+ * Copyright (c) 2001 Mikhail Kourinny ([email protected])
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this program; if not, write to the Free
+ * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __HEADERP_H
+#define __HEADERP_H
+
+//#define DEBUG 2
+
+#include <set>
+#include <list>
+#include <map>
+#include <memory>
+#include <iostream>
+
+#include "bfield.h"
+
+
+using namespace KGrid2D;
+using std::cout;
+using std::endl;
+
+typedef std::set<Coord, std::less<Coord> > CoordSet;
+
+inline std::ostream &operator <<(std::ostream &s, const Coord &c)
+{
+ s << '(' << c.first << ',' << c.second << ')' << endl;
+ return s;
+}
+
+inline std::ostream &operator <<(std::ostream &s, const CoordSet &set)
+{
+ for(CoordSet::const_iterator i=set.begin(); i!=set.end(); ++i)
+ s << *i;
+ return s;
+}
+
+inline std::ostream &operator <<(std::ostream &s, const BaseField &f)
+{
+ for (uint j=0; j<f.height(); j++) {
+ for (uint i=0; i<f.width(); i++) {
+ Coord c(i, j);
+ if ( f.isCovered(c) ) s << "? ";
+ else s << f.nbMinesAround(c) << ' ';
+ }
+ s << endl;
+ }
+ return s;
+}
+
+namespace AdviseFast {
+
+ /** A fact - number of mines in adjacent cells */
+ struct Fact {
+ CoordSet pointSet;
+ short mines;
+ };
+ std::ostream &operator <<(std::ostream &, Fact const &);
+
+ /** A set of facts that can be generated out of Field */
+ class FactSet : public std::map<Coord, Fact> {
+ public:
+ FactSet(BaseField *);
+ BaseField const *getField() const { return _field;}
+
+ /** Reveals a point on the field underlining
+ * Returns false on blowup !!! */
+ bool reveal(
+ Coord what,
+ CoordSet *affectedFacts);
+ void mark(
+ Coord what,
+ CoordSet *affectedFacts);
+ CoordSet const *getContainingFacts(
+ Coord const &)
+ const;
+ /** May be used to substitute fact */
+ void addFact(Coord const &, Fact const &);
+ void deleteFact(Coord const &);
+ void retrieveFact(Coord which, Fact *where);
+
+ private:
+ BaseField *_field;
+ std::map<Coord, CoordSet> _containingFacts;
+ CoordSet _marked;
+ };
+ std::ostream &operator <<(std::ostream &, FactSet const &);
+
+ /** A Rule abstraction that can be applied.
+ * Applying the rule results in either modifyling the
+ * RuleSet which it belongs to or FactSet it is based on
+ * or both ;)
+ */
+ class RuleSet;
+ struct Rule {
+ Rule(RuleSet *parent);
+ virtual ~Rule();
+ virtual bool apply(CoordSet *surePoints) = 0;
+
+ RuleSet *_parent;
+ FactSet *_facts;
+#if defined(DEBUG)
+# if DEBUG >= 2
+ private:
+ static int leaks;
+# endif
+#endif
+ };
+
+ /** A set of rules */
+ class RuleSet {
+ public:
+ enum RuleType {
+ EMPTY,
+ FULL,
+ INCLUDE,
+ INCLUDE1,
+ INTERSECT,
+ INTERSECT1,
+ GENERAL};
+
+ typedef std::pair<RuleType, CoordSet> Entry;
+
+ RuleSet(FactSet *);
+ ~RuleSet();
+ void addRule(Entry const &);
+
+ /** A factory method */
+ Rule *newRule(Entry const &);
+
+ /** Remove all references to a point from RuleSet */
+ void removeRef(Coord);
+
+ /** removeRef + add a General Rule */
+ void addGeneral(Coord);
+
+ /** Returns false on blowup */
+ bool reveal(Coord p);
+
+ /** Returns false on failure */
+ bool getSurePoint(Coord *sp);
+ /** Works until is stuck :) */
+ void solve();
+
+ FactSet *facts;
+
+ private:
+ std::set<Entry> _rules;
+ CoordSet _surePoints;
+
+ /** Fills _surePoints.
+ * Returns false if nothing done. */
+ bool apply();
+ };
+
+ /** Returns true on success */
+ bool adviseFast(
+ Coord *point,
+ FactSet *facts,
+ RuleSet *rules);
+
+}
+
+
+namespace AdviseFull {
+ typedef std::multimap<float, Coord> ProbabilityMap;
+
+ /** If there are sure free cells,
+ * sets surePoints, otherwise sets probabilities */
+ void adviseFull(
+ AdviseFast::FactSet *facts,
+ CoordSet *surePoints,
+ ProbabilityMap *probabilities);
+
+}
+
+#endif
diff --git a/kmines/solver/solver.cpp b/kmines/solver/solver.cpp
new file mode 100644
index 00000000..00807fca
--- /dev/null
+++ b/kmines/solver/solver.cpp
@@ -0,0 +1,249 @@
+/*
+ * Copyright (c) 2001 Mikhail Kourinny ([email protected])
+ * Copyright (c) 2002 Nicolas HADACEK ([email protected])
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "solver.h"
+#include "solver.moc"
+
+#include <algorithm>
+#include <assert.h>
+
+#include <qtimer.h>
+#include <qlayout.h>
+#include <qlabel.h>
+#include <kprogress.h>
+
+#include <klocale.h>
+
+#include "headerP.h"
+
+
+//-----------------------------------------------------------------------------
+class SolverPrivate
+{
+ public:
+ SolverPrivate() : facts(0), rules(0) {}
+ ~SolverPrivate() {
+ delete facts;
+ delete rules;
+ }
+
+ AdviseFast::FactSet *facts;
+ AdviseFast::RuleSet *rules;
+#ifdef DEBUG
+ unsigned long t0, t;
+#endif
+};
+
+Solver::Solver(QObject *parent)
+ : QObject(parent)
+{
+ d = new SolverPrivate;
+
+#ifdef DEBUG
+#define PRINT_ELAPSED(purpose) \
+ d->t = time(0); \
+ cout << "Spent " << d->t - d->t0 << " seconds on " purpose << endl; \
+ d->t0 = d->t;
+
+#endif
+}
+
+Solver::~Solver()
+{
+ delete d;
+}
+
+Coord Solver::advise(BaseField &field, float &probability)
+{
+ Coord point;
+ probability = 1;
+ delete d->facts;
+ d->facts = new AdviseFast::FactSet(&field);
+ delete d->rules;
+ d->rules = new AdviseFast::RuleSet(d->facts);
+
+ if( AdviseFast::adviseFast(&point, d->facts, d->rules) ) return point;
+
+ CoordSet surePoints;
+ AdviseFull::ProbabilityMap probabilities;
+ AdviseFull::adviseFull(d->facts, &surePoints, &probabilities);
+
+ // return one of the sure point (random choice to limit the tropism) [NH]
+ if( !surePoints.empty() ) {
+ KRandomSequence r;
+ uint k = r.getLong(surePoints.size());
+ CoordSet::iterator it = surePoints.begin();
+ for (uint i=0; i<k; i++) ++it;
+ return *it;
+ }
+
+ // Just a minimum probability logic here
+ if( !probabilities.empty() ){
+ probability = probabilities.begin()->first;
+ return probabilities.begin()->second;
+ }
+
+ // Otherwise the Field is already solved :)
+ return Coord(-1,-1);
+}
+
+void Solver::solve(BaseField &field, bool noGuess)
+{
+ _field = &field;
+ initSolve(false, noGuess);
+}
+
+bool Solver::initSolve(bool oneStep, bool noGuess)
+{
+ _inOneStep = oneStep;
+ _noGuess = noGuess;
+ delete d->facts;
+ d->facts = new AdviseFast::FactSet(_field);
+ delete d->rules;
+ d->rules = new AdviseFast::RuleSet(d->facts);
+#ifdef DEBUG
+ d->t0 = time(0);
+#endif
+ return solveStep();
+}
+
+bool Solver::solveStep()
+{
+ if ( _field->isSolved() ) {
+ emit solvingDone(true);
+ return true;
+ }
+
+ d->rules->solve();
+
+#ifdef DEBUG
+ PRINT_ELAPSED("fast rules")
+#endif
+
+ if( _field->isSolved() ) {
+ emit solvingDone(true);
+ return true;
+ }
+
+ CoordSet surePoints;
+ AdviseFull::ProbabilityMap probabilities;
+ AdviseFull::adviseFull(d->facts, &surePoints, &probabilities);
+
+#ifdef DEBUG
+ PRINT_ELAPSED("full rules")
+#endif
+
+ if(!surePoints.empty()){
+ CoordSet::iterator i;
+ for(i=surePoints.begin(); i!=surePoints.end(); ++i) {
+ bool b = d->rules->reveal(*i);
+ assert(b);
+ }
+ } else if ( !_noGuess ) {
+#ifdef DEBUG
+ cout << "Applying heuristics!" << endl;
+ cout << *_field << endl;
+#endif
+ // Minimum probability logic
+ assert(!probabilities.empty());
+#ifdef DEBUG
+ AdviseFull::ProbabilityMap::iterator i=probabilities.begin();
+ cout << "Probability is " << i->first << endl;
+#endif
+ bool success = d->rules->reveal(probabilities.begin()->second);
+ if ( !success ) {
+ emit solvingDone(false);
+ return false;
+ }
+ }
+
+ if (_inOneStep) return solveStep();
+ else QTimer::singleShot(0, this, SLOT(solveStep()));
+ return false;
+}
+
+bool Solver::solveOneStep(BaseField &field)
+{
+ _field = &field;
+ return initSolve(true, false);
+}
+
+
+//-----------------------------------------------------------------------------
+SolvingRateDialog::SolvingRateDialog(const BaseField &field, QWidget *parent)
+ : KDialogBase(Plain, i18n("Compute Solving Rate"), Ok|Close,
+ Close, parent, "compute_solving_rate", true, true),
+ _refField(field)
+{
+ connect(&_solver, SIGNAL(solvingDone(bool)), SLOT(solvingDone(bool)));
+
+ KGuiItem item = KStdGuiItem::ok();
+ item.setText(i18n("Start"));
+ setButtonOK(item);
+
+ QVBoxLayout *top = new QVBoxLayout(plainPage(), 0, spacingHint());
+ QLabel *label = new QLabel(i18n("Width: %1").arg(field.width()),
+ plainPage());
+ top->addWidget(label);
+ label = new QLabel(i18n("Height: %1").arg(field.height()), plainPage());
+ top->addWidget(label);
+ label = new QLabel(i18n("Mines: %1 (%2%)").arg(field.nbMines())
+ .arg( field.nbMines() * 100.0 / field.size()),
+ plainPage());
+ top->addWidget(label);
+
+ top->addSpacing(spacingHint());
+
+ _progress = new KProgress(NB_STEPS, plainPage());
+ _progress->setTextEnabled(true);
+ _progress->setFormat("%v");
+ top->addWidget(_progress);
+
+ _label = new QLabel(i18n("Success rate:"), plainPage());
+ top->addWidget(_label);
+}
+
+void SolvingRateDialog::slotOk()
+{
+ enableButtonOK(false);
+ _i = 0;
+ _success = 0;
+ _progress->setValue(0);
+ QTimer::singleShot(0, this, SLOT(step()));
+}
+
+void SolvingRateDialog::step()
+{
+ if ( _i==NB_STEPS ) {
+ enableButtonOK(true);
+ return;
+ }
+ _i++;
+ _field.reset(_refField.width(), _refField.height(), _refField.nbMines());
+ _solver.solve(_field, false);
+}
+
+void SolvingRateDialog::solvingDone(bool success)
+{
+ if (success) _success++;
+ _label->setText(i18n("Success rate: %1%")
+ .arg(_success * 100.0 / _i, 0, 'f', 3));
+ _progress->advance(1);
+ QTimer::singleShot(0, this, SLOT(step()));
+}
diff --git a/kmines/solver/solver.h b/kmines/solver/solver.h
new file mode 100644
index 00000000..f076874e
--- /dev/null
+++ b/kmines/solver/solver.h
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2001 Mikhail Kourinny ([email protected])
+ * Copyright (c) 2002 Nicolas HADACEK ([email protected])
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __SOLVER_H
+#define __SOLVER_H
+
+#include <kdialogbase.h>
+
+#include "bfield.h"
+
+
+class QLabel;
+class KProgress;
+class SolverPrivate;
+
+class Solver : public QObject
+{
+ Q_OBJECT
+ public:
+ Solver(QObject *parent = 0);
+ ~Solver();
+
+ /** A method to advice a point placement */
+ KGrid2D::Coord advise(BaseField &field, float &probability);
+
+ /** Solve current mine field */
+ void solve(BaseField &field, bool noGuess);
+
+ /** Solve without signals/slot (for test programs) */
+ bool solveOneStep(BaseField &field);
+
+ signals:
+ void solvingDone(bool success);
+
+ private slots:
+ bool solveStep();
+
+ private:
+ BaseField *_field;
+ bool _inOneStep, _noGuess;
+ SolverPrivate *d;
+
+ bool initSolve(bool oneStep, bool noGuess);
+};
+
+class SolvingRateDialog : public KDialogBase
+{
+ Q_OBJECT
+ public:
+ SolvingRateDialog(const BaseField &field, QWidget *parent);
+
+ private slots:
+ void step();
+ void slotOk();
+ void solvingDone(bool success);
+
+ private:
+ const BaseField &_refField;
+ BaseField _field;
+ Solver _solver;
+ uint _i, _success;
+ QLabel *_label;
+ KProgress *_progress;
+
+ static const uint NB_STEPS = 200;
+};
+
+#endif
diff --git a/kmines/solver/test.cpp b/kmines/solver/test.cpp
new file mode 100644
index 00000000..dd56d7a0
--- /dev/null
+++ b/kmines/solver/test.cpp
@@ -0,0 +1,45 @@
+/** A program to test advisory library */
+
+#include "bfield.h"
+#include "headerP.h"
+
+#define W 10
+#define H 10
+
+int main(int argc, char *argv[])
+{
+ long seed = (argc<2 ? time(0) : atoi(argv[1]));
+ cout << "seed = " << seed << endl;
+
+ BaseField f(seed);
+ f.reset(W, H, 10);
+
+ KRandomSequence random(seed);
+ Coord c(random.getLong(W), random.getLong(H));
+ f.doReveal(c, 0, 0);
+
+ CoordSet sp;
+ AdviseFull::ProbabilityMap pm;
+
+ AdviseFast::FactSet facts(&f);
+ AdviseFull::adviseFull(&facts, &sp, &pm);
+
+ float pic[H][W];
+
+ for(uint i=0; i<H; ++i)
+ for(uint j=0; j<W; ++j) pic[i][j] = -1; // unknown
+ pic[c.second][c.first] = -(int)f.nbMinesAround(c);
+
+ AdviseFull::ProbabilityMap::iterator pmi;
+ for(pmi = pm.begin(); pmi != pm.end(); ++pmi)
+ pic[pmi->second.second][pmi->second.first] = pmi->first;
+
+ QString s;
+ for(uint i=0;i<H;++i) {
+ for(uint j=0;j<W;++j)
+ cout << s.sprintf("%+.02f ", pic[i][j]).latin1();
+ cout << endl;
+ }
+
+ return 0;
+}
diff --git a/kmines/solver/testFast.cpp b/kmines/solver/testFast.cpp
new file mode 100644
index 00000000..7dbaa757
--- /dev/null
+++ b/kmines/solver/testFast.cpp
@@ -0,0 +1,30 @@
+/** A program to test advisory library */
+
+#include "bfield.h"
+#include "headerP.h"
+
+#define W 10
+#define H 10
+
+int main(int argc, char *argv[])
+{
+ long seed = (argc < 2 ? time(0) : atoi(argv[1]));
+ cout << "seed = " << seed << endl;
+
+ BaseField f(seed);
+ f.reset(W, H, 10);
+
+ KRandomSequence random(seed);
+ Coord c(random.getLong(W), random.getLong(H));
+ f.doReveal(c, 0, 0);
+
+ AdviseFast::FactSet facts(&f);
+ AdviseFast::RuleSet rules(&facts);
+
+ rules.solve();
+
+ cout << f << endl;
+ if(!f.isSolved()) cout << facts << endl;
+
+ return 0;
+}
diff --git a/kmines/solver/testRate.cpp b/kmines/solver/testRate.cpp
new file mode 100644
index 00000000..7fa9e90f
--- /dev/null
+++ b/kmines/solver/testRate.cpp
@@ -0,0 +1,41 @@
+/** A program to test advisory library */
+
+#include <assert.h>
+#include <time.h>
+
+#include "bfield.h"
+#include "solver.h"
+#include "headerP.h"
+
+int main(int argc, char *argv[])
+{
+ if ( argc!=4 )
+ qFatal("Arguments: width height nbMines");
+
+ long seed = time(0);
+ cout << "seed = " << seed << endl;
+
+ short W, H, M;
+ W = atoi(argv[1]); assert(W > 0);
+ H = atoi(argv[2]); assert(H > 0);
+ M = atoi(argv[3]); assert(M >= 0); // ;)
+
+ BaseField field(seed);
+ Solver solver;
+
+ int i, solved = 0;
+ for(i=0;i<1000;++i){
+ field.reset(W, H, M);
+
+ if( !solver.solveOneStep(field)){
+ cout << "OOPS!!" << endl;
+ cout << field << endl;
+ } else ++solved;
+
+ cout << "Tried " << i+1 << ", solved " << solved << endl;
+ }
+
+ cout << "Solved total: " << solved << endl;
+
+ return 0;
+}
diff --git a/kmines/solver/testSolve.cpp b/kmines/solver/testSolve.cpp
new file mode 100644
index 00000000..61b7e570
--- /dev/null
+++ b/kmines/solver/testSolve.cpp
@@ -0,0 +1,33 @@
+/** A program to test advisory library */
+
+#include <assert.h>
+#include <time.h>
+
+#include "bfield.h"
+#include "solver.h"
+#include "headerP.h"
+
+int main(int argc, char *argv[])
+{
+ if ( argc!=4 )
+ qFatal("Arguments: width height nbMines");
+
+ long seed = time(0);
+ cout << "seed = " << seed << endl;
+
+ short W, H, M;
+ W = atoi(argv[1]); assert(W > 0);
+ H = atoi(argv[2]); assert(H > 0);
+ M = atoi(argv[3]); assert(M >= 0); // ;)
+
+ BaseField field(seed);
+ field.reset(W, H, M);
+
+ Solver solver;
+ if( !solver.solveOneStep(field) ) cout << "OOPS!!" << endl;
+ else cout << "Solved!" << endl;
+
+ cout << field << endl;
+
+ return 0;
+}
generated by cgit v1.2.1 (git 2.18.0) at 2024-12-18 12:02:48 +0000