From 44006abac0169346d67a6de31f6fe0793ead0a09 Mon Sep 17 00:00:00 2001 From: Stijn Buys Date: Sun, 30 Sep 2012 11:43:36 +0000 Subject: Added validity test, API cleanup. --- src/cell.cc | 8 ++++++++ src/cell.h | 45 +++++++++++++++++++++++++++++++++++----- src/solverwindow.cc | 31 +++++++++++++++++++++++++--- src/solverwindow.h | 1 + src/sudoku.cc | 59 ++++++++++++++++++++++++++++++++++++++--------------- src/sudoku.h | 20 ++++++++++++------ src/sudokuwidget.cc | 18 ++++++++++++---- 7 files changed, 148 insertions(+), 34 deletions(-) diff --git a/src/cell.cc b/src/cell.cc index 31754b7..c586a73 100644 --- a/src/cell.cc +++ b/src/cell.cc @@ -4,6 +4,7 @@ Cell::Cell() { cell_value = 0; + cell_valid = true; } Cell::Cell(const Cell & other) @@ -13,7 +14,9 @@ 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; for (int i = 0; i < 9; i++) { cell_possibility[i] = other.cell_possibility[i]; @@ -29,3 +32,8 @@ void Cell::set_possibility(int value, bool possible) { cell_possibility[value] = possible; } + +void Cell::set_valid(bool valid) +{ + cell_valid = valid; +} diff --git a/src/cell.h b/src/cell.h index e81a7c4..4000846 100644 --- a/src/cell.h +++ b/src/cell.h @@ -5,24 +5,59 @@ class Cell { public: + /** + * @brief default constructor + * */ Cell(); + + /** + * @brief copy constructor + * */ Cell(const Cell & other); + /** + * @brief assignment operator + * */ void assign(const Cell & other); - // inspector - inline int value() const { return cell_value; } + // inspectors + /** + * @brief return true if a given value is a valid possibility for this cell + * */ inline int possibility(const int value) { return cell_possibility[value]; } + + /** + * @brief return true of the current value for this cell is a valid possibility + * */ + inline bool valid() const { return cell_valid; } - // mutator - void set_value(int value); + /** + * @brief return the current value for this cell_possibility + * */ + inline int value() const { return cell_value; } + + // mutators + /** + * @brief set wether or not the given value is a valid possibility for a this cell + * */ void set_possibility(int value, bool possible = true); + /** + * @brief set wether or not this cell is valid + * */ + void set_valid(bool valid); + + /** + * @brief set the value for this cell + * */ + void set_value(int value); + private: - int cell_value; bool cell_possibility[9]; + bool cell_valid; + int cell_value; }; #endif // __INCLUDED_SUDOKUSOLVER_CELL__ diff --git a/src/solverwindow.cc b/src/solverwindow.cc index 1ace44f..feace77 100644 --- a/src/solverwindow.cc +++ b/src/solverwindow.cc @@ -9,6 +9,12 @@ #include #include +/* + * FIXME + * On windows, this results in a rather awkward directory. + * The homepath should probably be a setting. + * */ + const QString HOMEDIR(QDir::homePath() + "/.sudoku"); SolverWindow::SolverWindow() @@ -44,6 +50,11 @@ SolverWindow::SolverWindow() sidebarlayout->addWidget(stepcoveragebutton); connect(stepcoveragebutton, SIGNAL(clicked()), this, SLOT(step_coverage())); + // add validate button + QPushButton *validatebutton = new QPushButton(tr("Validate")); + sidebarlayout->addWidget(validatebutton); + connect(validatebutton, SIGNAL(clicked()), this, SLOT(validate())); + // add stretch sidebarlayout->addStretch(1); @@ -95,7 +106,7 @@ void SolverWindow::load() for (int column = 0; column < 9 ; column++) { int i; textstream >> i; - sudoku.set_value(row, column, i); + sudoku.cell(row, column).set_value(i); } } solverwindow_sudokuwidget->set_values(sudoku); @@ -135,7 +146,7 @@ void SolverWindow::save() solverwindow_sudokuwidget->get_values(sudoku); for (int row = 0; row < 9; row++) { for (int column = 0; column < 9 ; column++) { - textstream << sudoku.value(row, column); + textstream << sudoku.cell(row, column).value(); if (column < 8) { textstream << ' '; if ((column % 3) == 2) { @@ -180,4 +191,18 @@ void SolverWindow::step_coverage() int solved = sudoku.solve_coverage(); solverwindow_sudokuwidget->set_values(sudoku); qDebug() << solved << " cells solved"; -} \ No newline at end of file +} + +void SolverWindow::validate() +{ + Sudoku sudoku; + solverwindow_sudokuwidget->get_values(sudoku); + if (sudoku.validate()) { + qDebug() << "sudoku is valid"; + } else { + qDebug() << "sudoku is not valid"; + } + solverwindow_sudokuwidget->set_values(sudoku); + qDebug() << "sudoku validated"; +} + diff --git a/src/solverwindow.h b/src/solverwindow.h index 2422e97..27385c9 100644 --- a/src/solverwindow.h +++ b/src/solverwindow.h @@ -23,6 +23,7 @@ public slots: void step_constraints(); void step_coverage(); void clear(); + void validate(); private: SudokuWidget *solverwindow_sudokuwidget; diff --git a/src/sudoku.cc b/src/sudoku.cc index 9fcb865..4fcfbf9 100644 --- a/src/sudoku.cc +++ b/src/sudoku.cc @@ -35,11 +35,12 @@ 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() @@ -51,9 +52,24 @@ void Sudoku::reset() } } +bool Sudoku::validate() +{ + bool v = true; + for (int row = 0; row < 9; row++) { + for (int column = 0; column < 9; column++) { + reset_cell(row, column); + v = v && sudoku_cell[row][column].valid(); + } + } + return v; +} + // reset the solution space for this cell and calculate possible values void Sudoku::reset_cell(int pos_row, int pos_column) { + // mark cell as valid + sudoku_cell[pos_row][pos_column].set_valid(true); + // reset all possibilities for this cell for (int possible_value = 0; possible_value < 9; possible_value++) { sudoku_cell[pos_row][pos_column].set_possibility(possible_value, true); @@ -62,7 +78,7 @@ void Sudoku::reset_cell(int pos_row, int pos_column) // eliminate row for (int column = 0; column < 9; column++) { if (column != pos_column) { - const int v = value(pos_row,column); + const int v = cell(pos_row,column).value(); if ((v > 0) && (v <= 9)) { sudoku_cell[pos_row][pos_column].set_possibility(v -1, false); } @@ -72,7 +88,7 @@ void Sudoku::reset_cell(int pos_row, int pos_column) // eliminate column for (int row = 0; row < 9; row++) { if (row != pos_row) { - const int v = value(row,pos_column); + const int v = cell(row,pos_column).value(); if ((v > 0) && (v <= 9)) { sudoku_cell[pos_row][pos_column].set_possibility(v -1, false); } @@ -87,7 +103,7 @@ void Sudoku::reset_cell(int pos_row, int pos_column) 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)) { - const int v = value(row, column); + const int v = cell(row, column).value(); if ((v > 0) && (v <= 9)) { sudoku_cell[pos_row][pos_column].set_possibility(v -1, false); } @@ -96,6 +112,13 @@ void Sudoku::reset_cell(int pos_row, int pos_column) } } + + // set validity + if ((cell(pos_row,pos_column).value() > 0) && (cell(pos_row,pos_column).value() <= 9)) { + if (!sudoku_cell[pos_row][pos_column].possibility(sudoku_cell[pos_row][pos_column].value() - 1)) { + sudoku_cell[pos_row][pos_column].set_valid(false); + } + } } /* @@ -120,7 +143,7 @@ int Sudoku::solve_coverage() // verify if there's exactly one possibility for v in this row for (int column = 0; column < 9 ; column++) { - if (!value(row, column) && sudoku_cell[row][column].possibility(v - 1)) { + if (!cell(row, column).value() && cell(row,column).possibility(v - 1)) { // value is still possible for this cell available_column = column; } else { @@ -129,7 +152,7 @@ int Sudoku::solve_coverage() } if (covered == 8) { // value is only possible for a single cell - solution.set_value(row, available_column, v); + solution.cell(row, available_column).set_value(v); // qDebug() << "(" << row << "," << available_column << ") row covered, value " << v; } } @@ -141,7 +164,7 @@ int Sudoku::solve_coverage() // verify if there's exactly one possibility for v in this column for (int row = 0; row < 9; row++) { - if (!value(row, column) && sudoku_cell[row][column].possibility(v - 1)) { + if (!cell(row, column).value() && sudoku_cell[row][column].possibility(v - 1)) { // value is still possible a single cell available_row = row; } else { @@ -150,7 +173,7 @@ int Sudoku::solve_coverage() } if (covered == 8) { // value is only possible for a single cell - solution.set_value(available_row, column, v); + solution.cell(available_row, column).set_value(v); // qDebug() << "(" << available_row << "," << column << ") column covered, value " << v; } } @@ -168,7 +191,7 @@ int Sudoku::solve_coverage() int available_pos = 0; int covered = 0; - if (!value(sg_rowidx, sg_colidx) && sudoku_cell[sg_rowidx][sg_colidx].possibility(v - 1)) { + if (!cell(sg_rowidx, sg_colidx).value() && cell(sg_rowidx,sg_colidx).possibility(v - 1)) { // value is still possible a single cell available_pos = subgrid_pos; } else { @@ -179,13 +202,15 @@ int Sudoku::solve_coverage() // value is only possible for a single cell int av_rowidx = sg_row + available_pos / 3; int av_colidx = sg_column + available_pos % 3; - solution.set_value(av_rowidx, av_colidx, v); + solution.cell(av_rowidx, av_colidx).set_value(v); // qDebug() << "(" << av_rowidx << "," << av_colidx << ") subgrid covered, value " << v; } } } } + reset(); + return compare_and_assign(solution); } @@ -199,18 +224,20 @@ int Sudoku::solve_constraints() Sudoku solution; for (int row = 0; row < 9; row++) { for (int column = 0; column < 9; column++) { - solution.set_value(row, column, solve_constraints(row, column)); + solution.cell(row, column).set_value(solve_constraints(row, column)); } } + reset(); + return compare_and_assign(solution); } int Sudoku::solve_constraints(int pos_row, int pos_column) { // verify if the cell has already been solved - if ((value(pos_row,pos_column) > 0 ) && (value(pos_row,pos_column) <= 9)) { - return value(pos_row,pos_column); + if ((cell(pos_row,pos_column).value() > 0 ) && (cell(pos_row,pos_column).value() <= 9)) { + return cell(pos_row,pos_column).value(); } bool possible_solution[9]; @@ -222,7 +249,7 @@ int Sudoku::solve_constraints(int pos_row, int pos_column) // eliminate row for (int column = 0; column < 9; column++) { if (column != pos_column) { - const int v = value(pos_row,column); + const int v = cell(pos_row,column).value(); if ((v > 0) && (v <= 9)) { possible_solution[v - 1] = false; } @@ -231,7 +258,7 @@ int Sudoku::solve_constraints(int pos_row, int pos_column) // eliminate column for (int row = 0; row < 9; row++) { if (row != pos_row) { - const int v = value(row,pos_column); + const int v = cell(row,pos_column).value(); if ((v > 0) && (v <= 9)) { possible_solution[v - 1] = false; } @@ -245,7 +272,7 @@ int Sudoku::solve_constraints(int pos_row, int pos_column) 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)) { - const int v = value(row, column); + const int v = cell(row, column).value(); if ((v > 0) && (v <= 9)) { possible_solution[v - 1] = false; } diff --git a/src/sudoku.h b/src/sudoku.h index ae205b6..57dcf57 100644 --- a/src/sudoku.h +++ b/src/sudoku.h @@ -15,14 +15,13 @@ public: int compare_and_assign(const Sudoku & other); - inline int value(int row, int column) const { - return sudoku_cell[row][column].value(); - } - - void set_value(int row, int column, int cell_value); - void reset(); + bool validate(); + + /** + * @brief reset solution space of the given cell + * */ void reset_cell(int pos_row, int pos_column); int solve_constraints(int pos_row, int pos_column); @@ -31,6 +30,15 @@ public: int solve_coverage(); + inline Cell & cell (int row, int column) + { + return sudoku_cell[row][column]; + } + + inline const Cell & cell(int row, int column) const + { + return sudoku_cell[row][column]; + } private: Cell sudoku_cell[9][9]; }; diff --git a/src/sudokuwidget.cc b/src/sudokuwidget.cc index afa0972..23052ef 100644 --- a/src/sudokuwidget.cc +++ b/src/sudokuwidget.cc @@ -23,16 +23,26 @@ QSize SudokuWidget::sizeHint () const } void SudokuWidget::set_values(const Sudoku & values) -{ +{ for (int row = 0; row < 9; row++) { for (int column = 0; column < 9 ; column++) { - int i = values.value(row, column); + QPalette child_palette(palette()); + int i = values.cell(row, column).value(); if (i > 0) { QString str = QString::number(i); sudokuwidget_value[row][column]->setText(str); + + // set background color depending on the validity of the cell value + if (values.cell(row, column).valid()) { + //child_palette.setColor(QPalette::Base, QColor(0, 0, 255)); + } else { + // FIXME colors should be configurable + child_palette.setColor(QPalette::Base, QColor(255, 0, 0)); + } } else { sudokuwidget_value[row][column]->clear(); } + sudokuwidget_value[row][column]->setPalette(child_palette); } } } @@ -45,9 +55,9 @@ void SudokuWidget::get_values(Sudoku & values) QString str(sudokuwidget_value[row][column]->text()); int i = str.toInt(&ok); if (ok && (i > 0) && (i <= 9)) { - values.set_value(row, column, i); + values.cell(row, column).set_value(i); } else { - values.set_value(row, column, 0); + values.cell(row, column).set_value(0); } } } -- cgit v1.2.3