From 6d6801d4779266b0eb062120525ef76510e76e3c Mon Sep 17 00:00:00 2001 From: Stijn Buys Date: Wed, 25 Jul 2012 18:47:14 +0000 Subject: Added initial coverage solver. --- src/cell.cc | 19 +++++++ src/cell.h | 8 +++ src/solverwindow.cc | 42 ++++++++------- src/solverwindow.h | 3 +- src/sudoku.cc | 148 ++++++++++++++++++++++++++++++++++++++++++++++++++-- src/sudoku.h | 19 +++++-- 6 files changed, 211 insertions(+), 28 deletions(-) diff --git a/src/cell.cc b/src/cell.cc index c5af933..31754b7 100644 --- a/src/cell.cc +++ b/src/cell.cc @@ -5,8 +5,27 @@ Cell::Cell() { cell_value = 0; } + +Cell::Cell(const Cell & other) +{ + assign(other); +} + +void Cell::assign(const Cell & other) +{ + cell_value = other.cell_value; + + for (int i = 0; i < 9; i++) { + cell_possibility[i] = other.cell_possibility[i]; + } +} void Cell::set_value(int value) { cell_value = value; } + +void Cell::set_possibility(int value, bool possible) +{ + cell_possibility[value] = possible; +} diff --git a/src/cell.h b/src/cell.h index 5b38403..e81a7c4 100644 --- a/src/cell.h +++ b/src/cell.h @@ -6,15 +6,23 @@ class Cell { public: Cell(); + Cell(const Cell & other); + + void assign(const Cell & other); // inspector inline int value() const { return cell_value; } + + inline int possibility(const int value) { return cell_possibility[value]; } // mutator void set_value(int value); + void set_possibility(int value, bool possible = true); + private: int cell_value; + bool cell_possibility[9]; }; #endif // __INCLUDED_SUDOKUSOLVER_CELL__ diff --git a/src/solverwindow.cc b/src/solverwindow.cc index 23157f4..a959a91 100644 --- a/src/solverwindow.cc +++ b/src/solverwindow.cc @@ -29,10 +29,15 @@ SolverWindow::SolverWindow() sidebarlayout->addWidget(savebutton); connect(savebutton, SIGNAL(clicked()), this, SLOT(save())); - // add step button - QPushButton *stepbutton = new QPushButton(tr("Step")); - sidebarlayout->addWidget(stepbutton); - connect(stepbutton, SIGNAL(clicked()), this, SLOT(step())); + // add step constraints button + QPushButton *stepconstraintsbutton = new QPushButton(tr("Constraints")); + sidebarlayout->addWidget(stepconstraintsbutton); + connect(stepconstraintsbutton, SIGNAL(clicked()), this, SLOT(step_constraints())); + + // add step coverage button + QPushButton *stepcoveragebutton = new QPushButton(tr("Coverage")); + sidebarlayout->addWidget(stepcoveragebutton); + connect(stepcoveragebutton, SIGNAL(clicked()), this, SLOT(step_coverage())); // add stretch sidebarlayout->addStretch(1); @@ -148,23 +153,20 @@ void SolverWindow::clear() solverwindow_sudokuwidget->set_values(sudoku); } -void SolverWindow::step() +void SolverWindow::step_constraints() { - int cells_solved = 0; Sudoku sudoku; solverwindow_sudokuwidget->get_values(sudoku); - - Sudoku solution; - for (int row = 0; row < 9; row++) { - for (int column = 0; column < 9; column++) { - solution.set_value(row, column, sudoku.solve_step(row, column)); - - if ((sudoku.value(row, column) == 0) && (solution.value(row, column) > 0)) { - cells_solved++; - } - - } - } - solverwindow_sudokuwidget->set_values(solution); - qDebug() << cells_solved << " cells solved"; + sudoku.solve_constraints(); + solverwindow_sudokuwidget->set_values(sudoku); + //qDebug() << cells_solved << " cells solved"; } + +void SolverWindow::step_coverage() +{ + Sudoku sudoku; + solverwindow_sudokuwidget->get_values(sudoku); + sudoku.solve_coverage(); + solverwindow_sudokuwidget->set_values(sudoku); + +} \ No newline at end of file diff --git a/src/solverwindow.h b/src/solverwindow.h index 886e721..51908c9 100644 --- a/src/solverwindow.h +++ b/src/solverwindow.h @@ -17,7 +17,8 @@ public slots: void load(); void save(); - void step(); + void step_constraints(); + void step_coverage(); void clear(); private: diff --git a/src/sudoku.cc b/src/sudoku.cc index 2725b02..3deabf9 100644 --- a/src/sudoku.cc +++ b/src/sudoku.cc @@ -5,12 +5,154 @@ Sudoku::Sudoku() { } -void Sudoku::set_value(int row, int column, int value) + +Sudoku::Sudoku(const Sudoku & other) +{ + assign(other); +} + +void Sudoku::assign(const Sudoku & other) +{ + for (int row = 0; row < 9; row++) { + for (int column = 0; column < 9; column++) { + sudoku_cell[row][column].assign(other.sudoku_cell[row][column]); + } + } +} + +void Sudoku::set_value(int row, int column, int cell_value) +{ + sudoku_cell[row][column].set_value(cell_value); +} + +void Sudoku::validate() +{ + for (int row = 0; row < 9; row++) { + for (int column = 0; column < 9; column++) { + validate_cell(row, column); + } + } +} + +// validate_cell calculates the possible values for a cell +void Sudoku::validate_cell(int pos_row, int pos_column) { - sudoku_cell[row][column].set_value(value); + // 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); + } + + // eliminate row + for (int column = 0; column < 9; column++) { + if (column != pos_column) { + const int v = value(pos_row,column); + if ((v > 0) && (v <= 9)) { + sudoku_cell[pos_row][pos_column].set_possibility(v -1, false); + } + } + } + + // eliminate column + for (int row = 0; row < 9; row++) { + if (row != pos_row) { + const int v = value(row,pos_column); + if ((v > 0) && (v <= 9)) { + sudoku_cell[pos_row][pos_column].set_possibility(v -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)) { + const int v = value(row, column); + if ((v > 0) && (v <= 9)) { + sudoku_cell[pos_row][pos_column].set_possibility(v -1, false); + } + } + + } + + } +} + +/* + * The coverage solver verifies the constraint which imposes that each + * value from 1-9 has to appear exactly once in each row, column and subgrid + * Cells with a unique solution are solved + */ +void Sudoku::solve_coverage() +{ + // calculate cell.possibilities + validate(); + + Sudoku solution(*this); + + // for each possible value + for (int v = 1; v <= 9; v++) { + + // verify coverage for each row + for (int row = 0; row < 9; row++) { + int available_column = 0; + int covered = 0; + for (int column = 0; column < 9 ; column++) { + if (!value(row, column) && sudoku_cell[row][column].possibility(v - 1)) { + // value is still possible for this cell + available_column = column; + } else { + covered++; + } + } + if (covered == 8) { + // value is only possible for a single cell + solution.set_value(row, available_column, v); + } + } + + // verify coverage for each column + for (int column = 0; column < 9; column++) { + int available_row = 0; + int covered = 0; + for (int row = 0; row < 9; row++) { + if (!value(row, column) && sudoku_cell[row][column].possibility(v - 1)) { + // value is still possible a single cell + available_row = row; + } else { + covered++; + } + } + if (covered == 8) { + // value is only possible for a single cell + solution.set_value(available_row, column, v); + } + } + + // verify coverage for each subgrid + } + assign(solution); +} + +/* + * The constraint solver verifies the constraint that each value from 1-9 + * can appear only once in each column, row and subgrid + * Cells with a unique solution are solved + */ +void 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)); + } + } + assign(solution); } -int Sudoku::solve_step(int pos_row, int pos_column) +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)) { diff --git a/src/sudoku.h b/src/sudoku.h index a6bf821..3b9af8e 100644 --- a/src/sudoku.h +++ b/src/sudoku.h @@ -9,16 +9,27 @@ class Sudoku { public: Sudoku(); - // inspector + Sudoku(const Sudoku & other); + + void assign(const Sudoku & other); + + // inspectors inline int value(int row, int column) const { return sudoku_cell[row][column].value(); } - // mutator - void set_value(int row, int column, int value); + // mutators + void validate(); + + void set_value(int row, int column, int cell_value); + + void validate_cell(int pos_row, int pos_column); + + int solve_constraints(int pos_row, int pos_column); - int solve_step(int pos_row, int pos_column); + void solve_constraints(); + void solve_coverage(); private: Cell sudoku_cell[9][9]; }; -- cgit v1.2.3