summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/solverwindow.cc16
-rw-r--r--src/sudoku.cc66
-rw-r--r--src/sudoku.h2
3 files changed, 84 insertions, 0 deletions
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];
};