summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIan Wadham <[email protected]>2015-07-03 10:25:57 +1000
committerIan Wadham <[email protected]>2015-07-03 10:40:45 +1000
commitff9663ba3504cdd300fccae03972024d2cc78da7 (patch)
tree8c7424b9768aacaa460d684f6c40f008ef95f7af
parent5062a58c7138c2b5ca653009b2bb3ec28b79958e (diff)
Add solution-checking, solutions and hints for loaded or entered cages.
-rw-r--r--src/generator/cagegenerator.cpp80
-rw-r--r--src/generator/cagegenerator.h27
-rw-r--r--src/generator/dlxsolver.cpp5
-rw-r--r--src/generator/dlxsolver.h7
-rw-r--r--src/generator/mathdokugenerator.cpp10
-rw-r--r--src/generator/mathdokugenerator.h15
6 files changed, 131 insertions, 13 deletions
diff --git a/src/generator/cagegenerator.cpp b/src/generator/cagegenerator.cpp
index 884f3d3..adcfe4d 100644
--- a/src/generator/cagegenerator.cpp
+++ b/src/generator/cagegenerator.cpp
@@ -257,6 +257,53 @@ int CageGenerator::makeCages (SKGraph * graph, QList<int> * solutionMoves,
return mGraph->cageCount();
}
+int CageGenerator::checkPuzzle (SKGraph * graph, BoardContents & solution,
+ QList<int> * solutionMoves, bool hideOperators)
+{
+#ifdef MATHDOKU_LOG
+ qDebug() << "CageGenerator::checkPuzzle(): nCAGES" << graph->cageCount();
+#endif
+
+ int result = 0;
+ mGraph = graph;
+ mOrder = graph->order();
+ mBoardArea = mOrder * mOrder;
+ mKillerSudoku = (graph->specificType() == KillerSudoku);
+ mHiddenOperators = mKillerSudoku ? true : hideOperators;
+ qDebug() << "\nCHECK PUZZLE: HIDDEN OPERATORS" << mHiddenOperators;
+
+ mPossibilities->clear();
+ mPossibilitiesIndex->clear();
+ mPossibilitiesIndex->append(0);
+
+ int nCages = graph->cageCount();
+ for (int n = 0; n < nCages; n++) {
+ // Add all the possibilities for each cage.
+#ifdef MATHDOKU_LOG
+ qDebug() << "SET ALL Possibilities: cage size" << graph->cage(n).size()
+ << "operator" << graph->cageOperator(n) << "value"
+ << graph->cageValue(n) << "cage" << graph->cage(n);
+#endif
+ setAllPossibilities (graph->cage(n), graph->cage(n).size(),
+ graph->cageOperator(n), graph->cageValue(n));
+ mPossibilitiesIndex->append (mPossibilities->size());
+ }
+#ifdef MATHDOKU_LOG
+ qDebug() << "POSSIBILITIES SET: now check-solve the puzzle.";
+ qDebug() << "INDEX" << (*mPossibilitiesIndex);
+ qDebug() << "POSS:" << (*mPossibilities);
+#endif
+ // Use the DLX solver to check if this puzzle has a unique solution.
+ result = mDLXSolver->solveMathdoku (graph, solutionMoves,
+ mPossibilities,
+ mPossibilitiesIndex, 2);
+ if (result == 1) {
+ // If there is a unique solution, retrieve it from the solver.
+ mDLXSolver->retrieveSolution (solution);
+ }
+ return result;
+}
+
QVector<int> CageGenerator::makeOneCage (int seedCell, int requiredSize)
{
QVector<int> cage;
@@ -443,19 +490,7 @@ bool CageGenerator::cageIsOK (const QVector<int> cage,
// Get all possibilities and keep checking, as we go, that the cage is OK.
bool isOK = true;
- if ((nDigits > 1) && mHiddenOperators && (! mKillerSudoku)) {
- // Operators are hidden, so we must consider every possible operator.
- if (nDigits == 2) {
- setPossibilities (cage, Divide, cageValue);
- setPossibilities (cage, Subtract, cageValue);
- }
- setPossibilities (cage, Add, cageValue);
- setPossibilities (cage, Multiply, cageValue);
- }
- else {
- // Operators are visible/fixed, so we can consider fewer possibilities.
- setPossibilities (cage, cageOperator, cageValue);
- }
+ setAllPossibilities (cage, nDigits, cageOperator, cageValue);
int numPoss = (mPossibilities->size() - mPossibilitiesIndex->last());
// There should be some possibilities and not too many (wrt difficulty).
@@ -478,6 +513,25 @@ bool CageGenerator::cageIsOK (const QVector<int> cage,
return isOK;
}
+void CageGenerator::setAllPossibilities (const QVector<int> cage, int nDigits,
+ CageOperator cageOperator,
+ int cageValue)
+{
+ if ((nDigits > 1) && mHiddenOperators && (! mKillerSudoku)) {
+ // Operators are hidden, so we must consider every possible operator.
+ if (nDigits == 2) {
+ setPossibilities (cage, Divide, cageValue);
+ setPossibilities (cage, Subtract, cageValue);
+ }
+ setPossibilities (cage, Add, cageValue);
+ setPossibilities (cage, Multiply, cageValue);
+ }
+ else {
+ // Operators are visible/fixed, so we can consider fewer possibilities.
+ setPossibilities (cage, cageOperator, cageValue);
+ }
+}
+
void CageGenerator::setPossibilities (const QVector<int> cage,
CageOperator cageOperator, int cageValue)
{
diff --git a/src/generator/cagegenerator.h b/src/generator/cagegenerator.h
index 1278d75..231acef 100644
--- a/src/generator/cagegenerator.h
+++ b/src/generator/cagegenerator.h
@@ -90,6 +90,29 @@ public:
int maxSize, int maxValue,
bool hideOperators, int maxCombos);
+ /**
+ * Using just the puzzle-graph and its cages, solve a Mathdoku or Killer
+ * Sudoku puzzle and check that it has only one solution. This method can
+ * be used with a manually entered puzzle or one loaded from a saved file,
+ * to obtain solution values and a move-sequence for hints, as well as
+ * checking that the puzzle and its data are valid.
+ *
+ * @param graph An SKGraph object representing the size, geometric
+ * layout and rules of the particular kind of puzzle.
+ * @param solution The solution returned if a unique solution exists.
+ * @param solutionMoves A pointer that returns an ordered list of cells
+ * found by the solver when it reached a solution.
+ * @param hideOperators Whether operators are to be hidden in a Mathdoku
+ * puzzle. In a Killer Sudoku the operators are all +
+ * and are always hidden.
+ *
+ * @return 0 = there is no solution,
+ * 1 = there is a unique solution,
+ * >1 = there is more than one solution.
+ */
+ int checkPuzzle (SKGraph * graph, BoardContents & solution,
+ QList<int> * solutionMoves, bool hideOperators);
+
private:
SKGraph * mGraph; // The geometry of the puzzle.
DLXSolver * mDLXSolver; // A solver for generated puzzles.
@@ -139,6 +162,10 @@ private:
int cageValue);
// Set all possible values for the cells of a cage (used by the solver).
+ void setAllPossibilities (const QVector<int> cage, int nDigits,
+ CageOperator cageOperator, int cageValue);
+
+ // Set all possible values for one operator in a cage (used by the solver).
void setPossibilities (const QVector<int> cage, CageOperator cageOperator,
int cageValue);
diff --git a/src/generator/dlxsolver.cpp b/src/generator/dlxsolver.cpp
index 8f0749f..2dcd2f6 100644
--- a/src/generator/dlxsolver.cpp
+++ b/src/generator/dlxsolver.cpp
@@ -180,6 +180,11 @@ void DLXSolver::recordSolution (const int solutionNum, QList<DLXNode *> & soluti
#endif
}
+void DLXSolver::retrieveSolution (BoardContents & solution)
+{
+ solution = mBoardValues;
+}
+
void DLXSolver::printSudoku()
{
// TODO - The code at SudokuBoard::print() is VERY similar...
diff --git a/src/generator/dlxsolver.h b/src/generator/dlxsolver.h
index 4b9cd9e..c29ab3a 100644
--- a/src/generator/dlxsolver.h
+++ b/src/generator/dlxsolver.h
@@ -156,6 +156,13 @@ public:
const QList<int> * possibilitiesIndex,
int solutionLimit = 2);
+ /**
+ * Copy back to the caller the last solution found by the solver.
+ *
+ * @param solution A BoardContents object to receive the solution.
+ */
+ void retrieveSolution (BoardContents & solution);
+
// void testDLX(); // TODO - Delete this eventually.
private:
diff --git a/src/generator/mathdokugenerator.cpp b/src/generator/mathdokugenerator.cpp
index 94b5496..04daa77 100644
--- a/src/generator/mathdokugenerator.cpp
+++ b/src/generator/mathdokugenerator.cpp
@@ -72,4 +72,14 @@ bool MathdokuGenerator::generateMathdokuTypes (BoardContents & puzzle,
return true;
}
+int MathdokuGenerator::solveMathdokuTypes (BoardContents & solution,
+ QList<int> * solutionMoves)
+{
+ bool hideOps = false;
+ int result = 0;
+ CageGenerator cageGen (solution);
+ result = cageGen.checkPuzzle (mGraph, solution, solutionMoves, hideOps);
+ return result;
+}
+
#include "mathdokugenerator.moc"
diff --git a/src/generator/mathdokugenerator.h b/src/generator/mathdokugenerator.h
index 5bee033..da20de4 100644
--- a/src/generator/mathdokugenerator.h
+++ b/src/generator/mathdokugenerator.h
@@ -53,6 +53,21 @@ public:
QList<int> * solutionMoves,
Difficulty difficultyRequired);
+ /**
+ * Solve a Mathdoku or Killer Sudoku and check how many solutions there are.
+ * The solver requires only the puzzle-graph, which contains all the cages.
+ *
+ * @param solution The values returned as the solution.
+ * @param solutionMoves A pointer that returns an ordered list of cells
+ * found by the solver when it reached a solution.
+ *
+ * @return 0 = there is no solution,
+ * 1 = there is a unique solution,
+ * >1 = there is more than one solution.
+ */
+ int solveMathdokuTypes (BoardContents & solution,
+ QList<int> * solutionMoves);
+
private:
SKGraph * mGraph; // The layout, rules and geometry of the puzzle.
};