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

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;
+}