diff options
| -rw-r--r-- | src/cell.cc | 5 | ||||
| -rw-r--r-- | src/mainwindow.cc | 8 | ||||
| -rw-r--r-- | src/mainwindow.h | 1 | ||||
| -rw-r--r-- | src/solverwindow.cc | 18 | ||||
| -rw-r--r-- | src/solverwindow.h | 1 | ||||
| -rw-r--r-- | src/sudoku.cc | 77 | ||||
| -rw-r--r-- | src/sudoku.h | 14 |
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]; }; |