diff options
author | toma <toma@283d02a7-25f6-0310-bc7c-ecb5cbfe19da> | 2009-11-25 17:56:58 +0000 |
---|---|---|
committer | toma <toma@283d02a7-25f6-0310-bc7c-ecb5cbfe19da> | 2009-11-25 17:56:58 +0000 |
commit | c90c389a8a8d9d8661e9772ec4144c5cf2039f23 (patch) | |
tree | 6d8391395bce9eaea4ad78958617edb20c6a7573 /kmines/solver | |
download | tdegames-c90c389a8a8d9d8661e9772ec4144c5cf2039f23.tar.gz tdegames-c90c389a8a8d9d8661e9772ec4144c5cf2039f23.zip |
Copy the KDE 3.5 branch to branches/trinity for new KDE 3.5 features.
BUG:215923
git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/kdegames@1054174 283d02a7-25f6-0310-bc7c-ecb5cbfe19da
Diffstat (limited to 'kmines/solver')
-rw-r--r-- | kmines/solver/Makefile.am | 18 | ||||
-rw-r--r-- | kmines/solver/advFastRules.cpp | 482 | ||||
-rw-r--r-- | kmines/solver/adviseFast.cpp | 201 | ||||
-rw-r--r-- | kmines/solver/adviseFast.h | 70 | ||||
-rw-r--r-- | kmines/solver/adviseFull.cpp | 655 | ||||
-rw-r--r-- | kmines/solver/adviseFull.h | 93 | ||||
-rw-r--r-- | kmines/solver/bfield.cpp | 221 | ||||
-rw-r--r-- | kmines/solver/bfield.h | 83 | ||||
-rw-r--r-- | kmines/solver/headerP.h | 191 | ||||
-rw-r--r-- | kmines/solver/solver.cpp | 249 | ||||
-rw-r--r-- | kmines/solver/solver.h | 84 | ||||
-rw-r--r-- | kmines/solver/test.cpp | 45 | ||||
-rw-r--r-- | kmines/solver/testFast.cpp | 30 | ||||
-rw-r--r-- | kmines/solver/testRate.cpp | 41 | ||||
-rw-r--r-- | kmines/solver/testSolve.cpp | 33 |
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 (mkourinny@yahoo.com) + * + * 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 (mkourinny@yahoo.com) + * + * 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 (mkourinny@yahoo.com) + * + * 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 (mkourinny@yahoo.com) + * + * 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 ÷nd, + 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 (mkourinny@yahoo.com) + * + * 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 ÷nd, + 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 (hadacek@kde.org) + * + * 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 (hadacek@kde.org) + * + * 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 (mkourinny@yahoo.com) + * + * 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 (mkourinny@yahoo.com) + * Copyright (c) 2002 Nicolas HADACEK (hadacek@kde.org) + * + * 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 (mkourinny@yahoo.com) + * Copyright (c) 2002 Nicolas HADACEK (hadacek@kde.org) + * + * 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; +} |