From 8f93d832318dd960842940b3e688332124484f51 Mon Sep 17 00:00:00 2001
From: Stijn Buys <ingar@osirion.org>
Date: Wed, 6 Jun 2012 18:25:47 +0000
Subject: Added unique solution step solver.

---
 src/solverwindow.cc | 16 +++++++++++++
 src/sudoku.cc       | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/sudoku.h        |  2 ++
 3 files changed, 84 insertions(+)

diff --git a/src/solverwindow.cc b/src/solverwindow.cc
index 9bda3d5..06de5fb 100644
--- a/src/solverwindow.cc
+++ b/src/solverwindow.cc
@@ -150,4 +150,20 @@ void SolverWindow::clear()
 
 void SolverWindow::step()
 {
+	int nbSolutions = 0;
+	Sudoku sudoku;
+	solverwindow_sudokuwidget->get_values(sudoku);
+	
+	Sudoku solution;
+	for (int row = 0; row < 9; row++) {
+		for (int column = 0; column < 9; column++) {
+			int i = sudoku.solve_step(row, column);
+			if ((i > 0) && (sudoku.value(row, column) == 0)) {
+				nbSolutions++;
+			}
+			solution.value(row, column) = i;
+		}
+	}
+	solverwindow_sudokuwidget->set_values(solution);
+	qDebug() << nbSolutions << " cells solved";
 }
\ No newline at end of file
diff --git a/src/sudoku.cc b/src/sudoku.cc
index 28e59b6..13369fe 100644
--- a/src/sudoku.cc
+++ b/src/sudoku.cc
@@ -8,4 +8,70 @@ Sudoku::Sudoku()
 			sudoku_value[row][column] = 0;
 		}
 	}
+}
+
+int Sudoku::solve_step(int pos_row, int pos_column)
+{
+	// verify if the cell has already been solved
+	if ((sudoku_value[pos_row][pos_column] > 0 ) && (sudoku_value[pos_row][pos_column] <= 9)) {
+		return sudoku_value[pos_row][pos_column];
+	}
+	
+	bool possible_solution[9];
+	
+	for (int idx = 0; idx < 9; idx++) {
+		possible_solution[idx] = true; 
+	}
+	
+	// eliminate row
+	for (int column = 0; column < 9; column++) {
+		if (column != pos_column) {
+			int value = sudoku_value[pos_row][column];
+			if ((value > 0) && (value <= 9)) {
+				possible_solution[value - 1] = false;
+			}
+		}
+	}
+	// eliminate column
+	for (int row = 0; row < 9; row++) {
+		if (row != pos_row) {
+			int value = sudoku_value[row][pos_column];
+			if ((value > 0) && (value <= 9)) {
+				possible_solution[value - 1] = false;
+			}
+		}
+		
+	}
+	
+	// eliminate subgrid
+	int grid_row = pos_row - (pos_row % 3);
+	int grid_column = pos_column - (pos_column % 3);
+	for (int row = grid_row; row < grid_row + 3; row++) {
+		for (int column = grid_column; column < grid_column + 3; column ++) {
+			if ((column != pos_column) && (row != pos_row)) {
+				int value = sudoku_value[row][column];
+				if ((value > 0) && (value <= 9)) {
+					possible_solution[value - 1] = false;
+				}	
+			}
+			
+		}
+		
+	}
+	
+	int nbeliminated = 0;
+	int solution = 0;
+	for (int idx = 0; idx < 9; idx++) {
+		if (!possible_solution[idx]) {
+			nbeliminated++;
+		} else {
+			solution = idx + 1;
+		}
+	}
+	
+	if (nbeliminated == 8) {
+		return solution;
+	} else {
+		return 0;
+	}
 }
\ No newline at end of file
diff --git a/src/sudoku.h b/src/sudoku.h
index 2059a81..afb9f16 100644
--- a/src/sudoku.h
+++ b/src/sudoku.h
@@ -17,6 +17,8 @@ public:
 		return sudoku_value[row][column];
 	}
 	
+	int solve_step(int pos_row, int pos_column);
+	
 private:
 	int sudoku_value[9][9];
 };
-- 
cgit v1.2.3