summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorStijn Buys <ingar@osirion.org>2012-08-04 20:09:33 +0000
committerStijn Buys <ingar@osirion.org>2012-08-04 20:09:33 +0000
commit135d8c8bc0f0c6555196a9736dbce76b4e1007ff (patch)
treeba2eb9f2e7e40dd43f3ec6ace06ddd88bb4eda30 /src
parent7045c3ca67b09496af63da40eb5b1ddebbbb7617 (diff)
Rnamed validate() functions to reset(),
added subgrid test to the coverage solver.
Diffstat (limited to 'src')
-rw-r--r--src/sudoku.cc39
-rw-r--r--src/sudoku.h6
2 files changed, 32 insertions, 13 deletions
diff --git a/src/sudoku.cc b/src/sudoku.cc
index 6c241d9..d55a43b 100644
--- a/src/sudoku.cc
+++ b/src/sudoku.cc
@@ -39,17 +39,18 @@ void Sudoku::set_value(int row, int column, int cell_value)
sudoku_cell[row][column].set_value(cell_value);
}
-void Sudoku::validate()
+// reset the solution space and calculate possible values for all cells
+void Sudoku::reset()
{
for (int row = 0; row < 9; row++) {
for (int column = 0; column < 9; column++) {
- validate_cell(row, column);
+ reset_cell(row, column);
}
}
}
-// validate_cell calculates the possible values for a cell
-void Sudoku::validate_cell(int pos_row, int pos_column)
+// reset the solution space for this cell and calculate possible values
+void Sudoku::reset_cell(int pos_row, int pos_column)
{
// reset all possibilities for this cell
for (int possible_value = 0; possible_value < 9; possible_value++) {
@@ -102,7 +103,7 @@ void Sudoku::validate_cell(int pos_row, int pos_column)
int Sudoku::solve_coverage()
{
// calculate cell.possibilities
- validate();
+ reset();
Sudoku solution(*this);
@@ -151,12 +152,30 @@ int Sudoku::solve_coverage()
// verify coverage for each subgrid
for (int subgrid = 0; subgrid < 9; subgrid++) {
+ // global coordinates of the (0,0) element of the subgrid
+ const int sg_row = (subgrid / 3) * 3;
+ const int sg_column = (subgrid % 3) * 3;
- // TODO the subgrid and subgrididx indices need te be delinearized
- // and translated into cell coordinates
-
- // verify if there's exactly one possibility for v in this subgrid
- for (int subgrididx = 0; subgrididx < 9; subgrididx++) {
+ // transle linear subgrid positions to row, col coordinate
+ for (int subgrid_pos = 0; subgrid_pos < 9; subgrid_pos++) {
+ int sg_rowidx = sg_row + subgrid_pos / 3;
+ int sg_colidx = sg_column + subgrid_pos % 3;
+ int available_pos = 0;
+ int covered = 0;
+
+ if (!value(sg_rowidx, sg_colidx) && sudoku_cell[sg_rowidx][sg_colidx].possibility(v - 1)) {
+ // value is still possible a single cell
+ available_pos = subgrid_pos;
+ } else {
+ covered++;
+ }
+
+ if (covered == 8) {
+ // value is only possible for a single cell
+ int sg_rowidx = sg_row + available_pos / 3;
+ int sg_colidx = sg_column + available_pos % 3;
+ solution.set_value(sg_rowidx, sg_colidx, v);
+ }
}
}
}
diff --git a/src/sudoku.h b/src/sudoku.h
index dd0ca08..ae205b6 100644
--- a/src/sudoku.h
+++ b/src/sudoku.h
@@ -19,11 +19,11 @@ public:
return sudoku_cell[row][column].value();
}
- void validate();
-
void set_value(int row, int column, int cell_value);
- void validate_cell(int pos_row, int pos_column);
+ void reset();
+
+ void reset_cell(int pos_row, int pos_column);
int solve_constraints(int pos_row, int pos_column);