Added initial coverage solver.

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];
 };