summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorStijn Buys <ingar@osirion.org>2012-09-30 11:43:36 +0000
committerStijn Buys <ingar@osirion.org>2012-09-30 11:43:36 +0000
commit44006abac0169346d67a6de31f6fe0793ead0a09 (patch)
treeec691aa1beba65559849de3a0690600e8773df7c
parent4a529901ad6ce3d4d4c53b68dde56f8b698661a8 (diff)
Added validity test, API cleanup.
-rw-r--r--src/cell.cc8
-rw-r--r--src/cell.h45
-rw-r--r--src/solverwindow.cc31
-rw-r--r--src/solverwindow.h1
-rw-r--r--src/sudoku.cc59
-rw-r--r--src/sudoku.h20
-rw-r--r--src/sudokuwidget.cc18
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 <QVBoxLayout>
#include <QPushButton>
+/*
+ * 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);
}
}
}