summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIan Wadham <[email protected]>2015-07-01 13:22:24 +1000
committerIan Wadham <[email protected]>2015-07-03 10:40:44 +1000
commit38b73df6506f521cd09dacfe49ca36da28ed61f3 (patch)
tree8a4c11ef158a8bf113a69d7560ef937f7d6492ec
parent858bb639c003f903158c8ecc1b901127bf5ebfca (diff)
Implement hints in Mathdoku and Killer Sudoku puzzles.
-rw-r--r--src/generator/cagegenerator.cpp6
-rw-r--r--src/generator/cagegenerator.h7
-rw-r--r--src/generator/dlxsolver.cpp14
-rw-r--r--src/generator/dlxsolver.h6
-rw-r--r--src/generator/mathdokugenerator.cpp4
-rw-r--r--src/generator/mathdokugenerator.h3
-rw-r--r--src/generator/sudokuboard.cpp3
-rw-r--r--src/gui/ksudoku.cpp6
8 files changed, 34 insertions, 15 deletions
diff --git a/src/generator/cagegenerator.cpp b/src/generator/cagegenerator.cpp
index 337e5e8..884f3d3 100644
--- a/src/generator/cagegenerator.cpp
+++ b/src/generator/cagegenerator.cpp
@@ -44,7 +44,8 @@ CageGenerator::~CageGenerator()
delete mPossibilitiesIndex;
}
-int CageGenerator::makeCages (SKGraph * graph, int maxSize, int maxValue,
+int CageGenerator::makeCages (SKGraph * graph, QList<int> * solutionMoves,
+ int maxSize, int maxValue,
bool hideOperators, int maxCombos)
{
// TODO - Use maxValue when OK'ing cages(?).
@@ -240,7 +241,8 @@ int CageGenerator::makeCages (SKGraph * graph, int maxSize, int maxValue,
#endif
// Use the DLX solver to check if this puzzle has a unique solution.
- int nSolutions = mDLXSolver->solveMathdoku (mGraph, mPossibilities,
+ int nSolutions = mDLXSolver->solveMathdoku (mGraph, solutionMoves,
+ mPossibilities,
mPossibilitiesIndex, 2);
if (nSolutions == 0) {
qDebug() << "FAILED TO FIND A SOLUTION: nSolutions =" << nSolutions;
diff --git a/src/generator/cagegenerator.h b/src/generator/cagegenerator.h
index b426d87..1278d75 100644
--- a/src/generator/cagegenerator.h
+++ b/src/generator/cagegenerator.h
@@ -71,6 +71,8 @@ public:
*
* @param graph An SKGraph object representing the size, geometric
* layout and rules of the particular kind of puzzle.
+ * @param solutionMoves A pointer that returns an ordered list of cells
+ * found by the solver when it reached a solution.
* @param maxSize The maximum number of cells a cage can have.
* @param maxValue The maximum total value a cage's cells can have.
* @param hideOperators Whether operators are to be hidden in a Mathdoku
@@ -84,8 +86,9 @@ public:
* unique solution to the puzzle using the cages
* generated (the caller may need to try again).
*/
- int makeCages (SKGraph * graph, int maxSize, int maxValue,
- bool hideOperators, int maxCombos);
+ int makeCages (SKGraph * graph, QList<int> * solutionMoves,
+ int maxSize, int maxValue,
+ bool hideOperators, int maxCombos);
private:
SKGraph * mGraph; // The geometry of the puzzle.
diff --git a/src/generator/dlxsolver.cpp b/src/generator/dlxsolver.cpp
index db89afb..8f0749f 100644
--- a/src/generator/dlxsolver.cpp
+++ b/src/generator/dlxsolver.cpp
@@ -27,7 +27,8 @@ DLXSolver::DLXSolver (QObject * parent)
:
QObject (parent),
mBoardValues (0),
- mGraph (0)
+ mGraph (0),
+ mSolutionMoves(0)
{
#ifdef DLX_LOG
qDebug() << "DLXSolver constructor entered";
@@ -114,6 +115,9 @@ void DLXSolver::recordSolution (const int solutionNum, QList<DLXNode *> & soluti
int order = mGraph->order();
int nCages = mGraph->cageCount();
SudokuType t = mGraph->specificType();
+ if (mSolutionMoves) {
+ mSolutionMoves->clear();
+ }
#ifdef DLX_LOG
qDebug() << "NUMBER OF ROWS IN SOLUTION" << solution.size();
#endif
@@ -147,6 +151,10 @@ void DLXSolver::recordSolution (const int solutionNum, QList<DLXNode *> & soluti
fprintf (stderr, "%d:%d ", cell,
mPossibilities->at (comboValues));
#endif
+ // Record the sequence of cell-numbers, for use in hints.
+ if (mSolutionMoves) {
+ mSolutionMoves->append (cell);
+ }
mBoardValues [cell] = mPossibilities->at (comboValues);
comboValues++;
}
@@ -354,10 +362,12 @@ int DLXSolver::solveSudoku (SKGraph * graph, const BoardContents & boardValues,
return nSolutions;
}
-int DLXSolver::solveMathdoku (SKGraph * graph, const QList<int> * possibilities,
+int DLXSolver::solveMathdoku (SKGraph * graph, QList<int> * solutionMoves,
+ const QList<int> * possibilities,
const QList<int> * possibilitiesIndex,
int solutionLimit)
{
+ mSolutionMoves = solutionMoves;
#ifdef DLX_LOG
qDebug() << "DLXSolver::solveMathdoku ENTERED" << possibilities->size()
<< "possibilities" << possibilitiesIndex->size() << "index size";
diff --git a/src/generator/dlxsolver.h b/src/generator/dlxsolver.h
index d4d9c9d..4b9cd9e 100644
--- a/src/generator/dlxsolver.h
+++ b/src/generator/dlxsolver.h
@@ -138,6 +138,8 @@ public:
* @param graph An SKGraph object representing the size, geometric
* layout and rules of the particular kind of puzzle,
* as well as its cage layouts, values and operators.
+ * @param solutionMoves A pointer that returns an ordered list of cells
+ * found by the solver when it reaches a solution.
* @param possibilities A pointer to a list of possible values for all the
* cells in all the cages.
* @param possibilitiesIndex
@@ -149,7 +151,8 @@ public:
*
* @return The number of solutions found (0 to solutionLimit).
*/
- int solveMathdoku (SKGraph * graph, const QList<int> * possibilities,
+ int solveMathdoku (SKGraph * graph, QList<int> * solutionMoves,
+ const QList<int> * possibilities,
const QList<int> * possibilitiesIndex,
int solutionLimit = 2);
@@ -228,6 +231,7 @@ private:
int mEndNodeNum;
BoardContents mBoardValues; // Holds Sudoku problem and solution.
+ QList<int> * mSolutionMoves; // Sequence of cells used in solution.
SKGraph * mGraph;
const QList<int> * mPossibilities;
const QList<int> * mPossibilitiesIndex;
diff --git a/src/generator/mathdokugenerator.cpp b/src/generator/mathdokugenerator.cpp
index b19eb75..94b5496 100644
--- a/src/generator/mathdokugenerator.cpp
+++ b/src/generator/mathdokugenerator.cpp
@@ -29,6 +29,7 @@ MathdokuGenerator::MathdokuGenerator (SKGraph * graph)
bool MathdokuGenerator::generateMathdokuTypes (BoardContents & puzzle,
BoardContents & solution,
+ QList<int> * solutionMoves,
Difficulty difficultyRequired)
{
// Cage sizes must be no more than the number of cells in a column or row.
@@ -47,7 +48,8 @@ bool MathdokuGenerator::generateMathdokuTypes (BoardContents & puzzle,
int n = 0;
while ((n <= 0) && (numTries < maxTries)) {
numTries++;
- n = cageGen.makeCages (mGraph, maxSize, maxVal, hideOps, maxCombos);
+ n = cageGen.makeCages (mGraph, solutionMoves,
+ maxSize, maxVal, hideOps, maxCombos);
if (n < 0) {
numMultis++;
}
diff --git a/src/generator/mathdokugenerator.h b/src/generator/mathdokugenerator.h
index 23398de..5bee033 100644
--- a/src/generator/mathdokugenerator.h
+++ b/src/generator/mathdokugenerator.h
@@ -41,6 +41,8 @@ public:
*
* @param puzzle The generated puzzle (returned).
* @param solution The values that must go into the solution.
+ * @param solutionMoves A pointer that returns an ordered list of cells
+ * found by the solver when it reached a solution.
* @param difficultyRequired The requested level of difficulty.
*
* @return True if puzzle-generation succeeded, false
@@ -48,6 +50,7 @@ public:
*/
bool generateMathdokuTypes (BoardContents & puzzle,
BoardContents & solution,
+ QList<int> * solutionMoves,
Difficulty difficultyRequired);
private:
diff --git a/src/generator/sudokuboard.cpp b/src/generator/sudokuboard.cpp
index 48c57df..d93a432 100644
--- a/src/generator/sudokuboard.cpp
+++ b/src/generator/sudokuboard.cpp
@@ -92,7 +92,8 @@ void SudokuBoard::generatePuzzle (BoardContents & puzzle,
MathdokuGenerator mg (m_graph);
solution = fillBoard();
numTries++;
- r = mg.generateMathdokuTypes (puzzle, solution, difficultyRequired);
+ r = mg.generateMathdokuTypes (puzzle, solution, &m_KSudokuMoves,
+ difficultyRequired);
if (r) {
qDebug() << "SudokuBoard::generatePuzzle SUCCEEDED: numTries"
<< numTries;
diff --git a/src/gui/ksudoku.cpp b/src/gui/ksudoku.cpp
index bb6b7d4..aae2527 100644
--- a/src/gui/ksudoku.cpp
+++ b/src/gui/ksudoku.cpp
@@ -347,12 +347,6 @@ void KSudoku::giveHint()
Game game = currentGame();
if(!game.isValid()) return;
SudokuType t = game.puzzle()->graph()->specificType();
- if ((t == Mathdoku) || (t == KillerSudoku)) {
- KMessageBox::information (this,
- i18n("Sorry, hints for Mathdoku and Killer Sudoku "
- "puzzles are not yet provided."));
- return;
- }
game.giveHint();
}