Added brute-force search algorithm.

7 files changed, 114 insertions, 10 deletions

diff --git a/src/cell.cc b/src/cell.cc
index c586a73..21b7560 100644
--- a/src/cell.cc
+++ b/src/cell.cc
@@ -14,9 +14,8 @@ Cell::Cell(const Cell & other)
 	
 void Cell::assign(const Cell & other)
 {
-	cell_valid = other.cell_valid;
-	cell_value = other.cell_value;
-	cell_valid = other.cell_valid;
+	cell_valid = other.valid();
+	cell_value = other.value();
 	
 	for (int i = 0; i < 9; i++) {
 		cell_possibility[i] = other.cell_possibility[i];
diff --git a/src/mainwindow.cc b/src/mainwindow.cc
index f441783..72b7f60 100644
--- a/src/mainwindow.cc
+++ b/src/mainwindow.cc
@@ -54,8 +54,13 @@ void MainWindow::initActions()
 	
 	// Move -> Solve
 	action_solve = new QAction(tr("Solve"), this);
-	action_solve->setStatusTip(tr("Try to solve this game"));
+	action_solve->setStatusTip(tr("Solve sudoku constraints"));
 	connect(action_solve, SIGNAL(triggered()), mainwindow_solverwindow, SLOT(solve()));
+
+	// Move -> Search
+	action_search = new QAction(tr("Search"), this);
+	action_search->setStatusTip(tr("Search for a solution"));
+	connect(action_search, SIGNAL(triggered()), mainwindow_solverwindow, SLOT(search()));
 }
 
 void MainWindow::initMenus()
@@ -72,5 +77,6 @@ void MainWindow::initMenus()
 	mainwindow_movemenu->addAction(action_hint);
 	mainwindow_movemenu->addAction(action_step);
 	mainwindow_movemenu->addAction(action_solve);
+	mainwindow_movemenu->addAction(action_search);
 }
 
diff --git a/src/mainwindow.h b/src/mainwindow.h
index 9eb16ea..f18e6df 100644
--- a/src/mainwindow.h
+++ b/src/mainwindow.h
@@ -37,6 +37,7 @@ private:
 	QAction		*action_hint;
 	QAction		*action_step;
 	QAction		*action_solve;
+	QAction		*action_search;
 
 };
 
diff --git a/src/solverwindow.cc b/src/solverwindow.cc
index 33ca7c2..e7f4633 100644
--- a/src/solverwindow.cc
+++ b/src/solverwindow.cc
@@ -181,14 +181,14 @@ void SolverWindow::step()
 	solverwindow_sudokuwidget->get_values(sudoku);
 	
 	Sudoku solution(sudoku);
-	int solved = solution.solve();
+	int solved = solution.solve_rules();
 	if (solved == 0) {
 		qDebug() << "no solveable cells left!";
 		return;
 	}
 	
 	// compare sudoku and solution values
-	int index_start = (int) random() % 81;	// TODO this should be a random number from 0 to 80
+	int index_start = (int) random() % 81;
 	int index_current = index_start;
 	do {
 		int column = index_current % 9;
@@ -209,11 +209,23 @@ void SolverWindow::solve()
 {
 	Sudoku sudoku;
 	solverwindow_sudokuwidget->get_values(sudoku);
-	int solved = sudoku.solve();
+	int solved = sudoku.solve_rules();
+	sudoku.validate();
 	solverwindow_sudokuwidget->set_values(sudoku);
 	qDebug() << solved << " cells solved";
 }
 
+void SolverWindow::search()
+{
+	Sudoku sudoku;
+	solverwindow_sudokuwidget->get_values(sudoku);
+	int iterations = sudoku.solve_search();
+	solverwindow_sudokuwidget->set_values(sudoku);
+	if (iterations > 0) {
+		qDebug() << "solved in " << iterations << " iterations";
+	}
+}
+
 void SolverWindow::step_constraints()
 {
 	Sudoku sudoku;
diff --git a/src/solverwindow.h b/src/solverwindow.h
index 27e2114..17cb55c 100644
--- a/src/solverwindow.h
+++ b/src/solverwindow.h
@@ -21,6 +21,7 @@ public slots:
 	void saveas();
 	void revert();
 	void solve();
+	void search();
 	void step();
 	void step_constraints();
 	void step_coverage();
diff --git a/src/sudoku.cc b/src/sudoku.cc
index 07b9056..7ffe13f 100644
--- a/src/sudoku.cc
+++ b/src/sudoku.cc
@@ -1,6 +1,8 @@
 
 #include "sudoku.h"
 
+#include <cstdlib>
+
 Sudoku::Sudoku()
 {
 }
@@ -56,6 +58,22 @@ bool Sudoku::validate()
 	return v;
 }
 
+bool Sudoku::solved()
+{
+	bool s = true;
+	for (int row = 0; row < 9; row++) {
+		for (int column = 0; column < 9; column++) {
+			reset_cell(row, column);
+			if ((!cell(row, column).valid()) || (cell(row, column).value() == 0)) {
+				s = false;
+				
+			}
+		}
+	}
+
+	return s;
+}
+
 // reset the solution space for this cell and calculate possible values
 void Sudoku::reset_cell(int pos_row, int pos_column)
 {
@@ -303,7 +321,61 @@ int Sudoku::solve_constraints(int pos_row, int pos_column)
 	}
 }
 
-int Sudoku::solve()
+int Sudoku::solve_search()
+{
+	int nbiterations = 0;
+	bool b = solve_search_step( nbiterations, (*this));
+	if (b) {
+		return nbiterations;
+	} else {
+		return 0;
+	}
+
+}
+
+bool Sudoku::solve_search_step(int &iterations, Sudoku & solution)
+{
+	if (solved()) {
+		solution.assign((*this));
+		return true;
+	}
+
+	int index_start = (int) random() % 81;
+	int index_current = index_start;
+	do {
+		int column = index_current % 9;
+		int row = (index_current - column) / 9;
+		
+		if (cell(row, column).value() == 0) {
+			
+			// pick a possibility
+			for (int p = 0; p < 9; p++) {
+				if (cell(row, column).possibility(p) == true) {
+					Sudoku recursive(*this);
+					recursive.cell(row, column).set_value(p+1);
+					recursive.solve_rules();
+					
+					if (recursive.validate()) {
+						iterations++;
+						bool b = recursive.solve_search_step(iterations, solution);
+						if (b) {
+							return true;
+						}
+						
+					}
+				}
+			}
+			
+		}
+		
+		index_current = (index_current + 1) % 81;
+	
+	}  while (index_current != index_start);
+
+	return false;
+}
+
+int Sudoku::solve_rules()
 {
 	int solved_total = 0;
 	int solved_step = 0;
@@ -314,4 +386,5 @@ int Sudoku::solve()
 	} while (solved_step > 0);
 	
 	return (solved_total);
-}
\ No newline at end of file
+}
+
diff --git a/src/sudoku.h b/src/sudoku.h
index 0aa8395..394f165 100644
--- a/src/sudoku.h
+++ b/src/sudoku.h
@@ -19,6 +19,8 @@ public:
 	
 	bool validate();
 
+	bool solved();
+	
 	/**
 	 * @brief reset solution space of the given cell
 	 * */
@@ -30,7 +32,15 @@ public:
 	
 	int solve_coverage();
 	
-	int solve();
+	/**
+	 * @brief solve the sudoku, using constraint and converage rules only
+	 * */
+	int solve_rules();
+	
+	/**
+	 * @brief solve the sudoku, using exhaustive search
+	 * */
+	int solve_search();
 	
 	inline Cell & cell (int row, int column)
 	{
@@ -42,6 +52,8 @@ public:
 		return sudoku_cell[row][column];
 	}
 private:
+	bool solve_search_step(int &iterations, Sudoku & solution);
+	
 	Cell sudoku_cell[9][9];
 };