diff options
| -rw-r--r-- | README | 5 | ||||
| -rw-r--r-- | src/main.cc | 10 | ||||
| -rw-r--r-- | src/mainwindow.cc | 71 | ||||
| -rw-r--r-- | src/mainwindow.h | 28 | ||||
| -rw-r--r-- | src/solverwindow.cc | 47 | ||||
| -rw-r--r-- | src/solverwindow.h | 4 | ||||
| -rw-r--r-- | src/sudoku.cc | 21 | ||||
| -rw-r--r-- | src/sudoku.h | 2 |
8 files changed, 169 insertions, 19 deletions
@@ -1,5 +1,5 @@ -SUDOKU SOLVER +INGAR'S SUDOKU SOLVER I'm not a fervent sudoku solver but I always wanted to try implementing a program to solve the puzzles faster than I can. This is my first attempt. @@ -16,7 +16,7 @@ BUILDING INSTRUCTIONS ../configure make - The binary will be called 'sudokusolver' and be located in the 'src' directory. + The binary will be called 'sudoku' and be located in the 'src' directory. USAGE @@ -51,3 +51,4 @@ COPYRIGHT ingar@telenet.be htpt://ingar.satgnu.net + diff --git a/src/main.cc b/src/main.cc index 91525f7..c7b1fff 100644 --- a/src/main.cc +++ b/src/main.cc @@ -1,10 +1,18 @@ +#include "mainwindow.h" + #include <QApplication> -#include "mainwindow.h" +#include <cstdlib> int main(int argc, char **argv) { + // TODO initialize random seed + /* + unsigned int seed = THE_SEED; + srandom(seed); + */ + QApplication application(argc, argv); MainWindow mainwindow; diff --git a/src/mainwindow.cc b/src/mainwindow.cc index f109a86..f441783 100644 --- a/src/mainwindow.cc +++ b/src/mainwindow.cc @@ -4,6 +4,73 @@ MainWindow::MainWindow() { - SolverWindow *solverwindow = new SolverWindow(); - setCentralWidget(solverwindow); + setWindowTitle(tr("Sudoku")); + + mainwindow_solverwindow = new SolverWindow(); + setCentralWidget(mainwindow_solverwindow); + + initActions(); + + initMenus(); } + + +void MainWindow::initActions() +{ + // Game -> New + action_new = new QAction(tr("&New"), this); + action_new->setShortcuts(QKeySequence::New); + action_new->setStatusTip(tr("Start a new game")); + connect(action_new, SIGNAL(triggered()), mainwindow_solverwindow, SLOT(clear())); + + // Game -> Load + action_load = new QAction(tr("&Load..."), this); + action_load->setShortcuts(QKeySequence::Open); + action_load->setStatusTip(tr("Load a previously saved game")); + connect(action_load, SIGNAL(triggered()), mainwindow_solverwindow, SLOT(load())); + + action_save = new QAction(tr("&Save"), this); + action_load->setStatusTip(tr("Save the current game")); + + action_saveas = new QAction(tr("Save &As..."), this); + action_load->setStatusTip(tr("Save the current game to a new file")); + connect(action_saveas, SIGNAL(triggered()), mainwindow_solverwindow, SLOT(saveas())); + + // Game -> Quit + action_quit = new QAction(tr("&Quit"), this); + action_quit->setShortcuts(QKeySequence::Quit); + action_quit->setStatusTip(tr("Exit the application")); + connect(action_quit, SIGNAL(triggered()), qApp, SLOT(closeAllWindows())); + + // Move -> Hint + action_hint = new QAction(tr("Hint"), this); + action_hint->setStatusTip(tr("Give a hint")); + // TODO + + // Move -> Step + action_step = new QAction(tr("Step"), this); + action_step->setStatusTip(tr("Solve a single cell")); + connect(action_step, SIGNAL(triggered()), mainwindow_solverwindow, SLOT(step())); + + // Move -> Solve + action_solve = new QAction(tr("Solve"), this); + action_solve->setStatusTip(tr("Try to solve this game")); + connect(action_solve, SIGNAL(triggered()), mainwindow_solverwindow, SLOT(solve())); +} + +void MainWindow::initMenus() +{ + mainwindow_gamemenu = menuBar()->addMenu(tr("&Game")); + mainwindow_gamemenu->addAction(action_new); + mainwindow_gamemenu->addAction(action_load); + mainwindow_gamemenu->addSeparator(); + mainwindow_gamemenu->addAction(action_save); + mainwindow_gamemenu->addAction(action_saveas); + mainwindow_gamemenu->addAction(action_quit); + + mainwindow_movemenu = menuBar()->addMenu(tr("&Move")); + mainwindow_movemenu->addAction(action_hint); + mainwindow_movemenu->addAction(action_step); + mainwindow_movemenu->addAction(action_solve); +} + diff --git a/src/mainwindow.h b/src/mainwindow.h index 19d45c8..9eb16ea 100644 --- a/src/mainwindow.h +++ b/src/mainwindow.h @@ -6,6 +6,9 @@ #include <QMainWindow> class SudokuWidget; +class QAction; +class QMenu; +class SolverWindow; class MainWindow : public QMainWindow { @@ -13,6 +16,29 @@ class MainWindow : public QMainWindow public: MainWindow(); + +private: + void initActions(); + + void initMenus(); + + SolverWindow *mainwindow_solverwindow; + QMenu *mainwindow_gamemenu; + QMenu *mainwindow_movemenu; + + // Game menu actions + QAction *action_new; + QAction *action_load; + QAction *action_save; + QAction *action_saveas; + QAction *action_quit; + + // Move menu actions + QAction *action_hint; + QAction *action_step; + QAction *action_solve; + }; -#endif // __INCLUDED_SUDOKUSOLVER_MAINWINDOW__
\ No newline at end of file +#endif // __INCLUDED_SUDOKUSOLVER_MAINWINDOW__ + diff --git a/src/solverwindow.cc b/src/solverwindow.cc index feace77..33ca7c2 100644 --- a/src/solverwindow.cc +++ b/src/solverwindow.cc @@ -9,6 +9,7 @@ #include <QVBoxLayout> #include <QPushButton> +#include <cstdlib> /* * FIXME * On windows, this results in a rather awkward directory. @@ -33,7 +34,7 @@ SolverWindow::SolverWindow() // add save button QPushButton *savebutton = new QPushButton(tr("Save")); sidebarlayout->addWidget(savebutton); - connect(savebutton, SIGNAL(clicked()), this, SLOT(save())); + connect(savebutton, SIGNAL(clicked()), this, SLOT(saveas())); // add revert button QPushButton *revertbutton = new QPushButton(tr("Revert")); @@ -65,8 +66,7 @@ SolverWindow::SolverWindow() // add sidebar layout windowlayout->addLayout(sidebarlayout); - - + // sudoku widget solverwindow_sudokuwidget = new SudokuWidget(); windowlayout->addWidget(solverwindow_sudokuwidget, 1); @@ -122,7 +122,7 @@ void SolverWindow::revert() solverwindow_sudokuwidget->set_values(solverwindow_revertstate); } -void SolverWindow::save() +void SolverWindow::saveas() { QString filename = QFileDialog::getSaveFileName(this, tr("Save as..."), HOMEDIR, "Sudoku (*.sudoku)"); if (filename.isEmpty()) { @@ -175,6 +175,45 @@ void SolverWindow::clear() solverwindow_sudokuwidget->set_values(sudoku); } +void SolverWindow::step() +{ + Sudoku sudoku; + solverwindow_sudokuwidget->get_values(sudoku); + + Sudoku solution(sudoku); + int solved = solution.solve(); + 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_current = index_start; + do { + int column = index_current % 9; + int row = (index_current - column) / 9; + if ((sudoku.cell(row,column).value() == 0) && (solution.cell(row,column).value() != 0)) { + sudoku.cell(row,column).set_value(solution.cell(row, column).value()); + solverwindow_sudokuwidget->set_values(sudoku); + return; + } + + index_current = (index_current + 1) % 81; + + } while (index_current != index_start); + +} + +void SolverWindow::solve() +{ + Sudoku sudoku; + solverwindow_sudokuwidget->get_values(sudoku); + int solved = sudoku.solve(); + solverwindow_sudokuwidget->set_values(sudoku); + qDebug() << solved << " cells solved"; +} + void SolverWindow::step_constraints() { Sudoku sudoku; diff --git a/src/solverwindow.h b/src/solverwindow.h index 27385c9..27e2114 100644 --- a/src/solverwindow.h +++ b/src/solverwindow.h @@ -18,8 +18,10 @@ public: public slots: void load(); - void save(); + void saveas(); void revert(); + void solve(); + void step(); void step_constraints(); void step_coverage(); void clear(); diff --git a/src/sudoku.cc b/src/sudoku.cc index 44f8365..07b9056 100644 --- a/src/sudoku.cc +++ b/src/sudoku.cc @@ -1,6 +1,4 @@ -// #include <QtGui> - #include "sudoku.h" Sudoku::Sudoku() @@ -35,12 +33,6 @@ int Sudoku::compare_and_assign(const Sudoku & other) } return d; } -/* -void Sudoku::set_value(int row, int column, int cell_value) -{ - sudoku_cell[row][column].set_value(cell_value); -} -*/ // reset the solution space and calculate possible values for all cells void Sudoku::reset() @@ -309,4 +301,17 @@ int Sudoku::solve_constraints(int pos_row, int pos_column) } else { return 0; } +} + +int Sudoku::solve() +{ + int solved_total = 0; + int solved_step = 0; + + do { + solved_step = solve_coverage() + solve_constraints(); + solved_total += solved_step; + } while (solved_step > 0); + + return (solved_total); }
\ No newline at end of file diff --git a/src/sudoku.h b/src/sudoku.h index 57dcf57..0aa8395 100644 --- a/src/sudoku.h +++ b/src/sudoku.h @@ -30,6 +30,8 @@ public: int solve_coverage(); + int solve(); + inline Cell & cell (int row, int column) { return sudoku_cell[row][column]; |