summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIan Wadham <[email protected]>2015-07-21 12:32:03 +1000
committerIan Wadham <[email protected]>2015-07-21 12:41:05 +1000
commit70127772e670615b64fd1cf2bef9b251560f2db3 (patch)
tree663b579bf4e83e0426a62a06f513afe3cb5534f9
parent55a399f4b9661dd60f9609af5924524a488775d2 (diff)
Fix CPU bottleneck on large cages (size 7-9), esp. with Add operator.
-rw-r--r--src/generator/cagegenerator.cpp49
-rw-r--r--src/generator/cagegenerator.h5
-rw-r--r--src/globals.h3
3 files changed, 28 insertions, 29 deletions
diff --git a/src/generator/cagegenerator.cpp b/src/generator/cagegenerator.cpp
index 4caf6e3..4b334e5 100644
--- a/src/generator/cagegenerator.cpp
+++ b/src/generator/cagegenerator.cpp
@@ -591,7 +591,7 @@ void CageGenerator::setPossibilities (const QVector<int> cage,
void CageGenerator::setPossibleAddsOrMultiplies
(const QVector<int> cage, CageOperator cageOperator, int requiredValue)
{
- QVector<int> digits;
+ int digits[MaxMathOrder]; // Maximum order of maths-based puzzles == 9.
int maxDigit = mOrder;
int nDigits = cage.size();
int currentValue;
@@ -606,10 +606,10 @@ void CageGenerator::setPossibleAddsOrMultiplies
// Calculate the number of possible sets of digits in the cage.
for (int n = 0; n < nDigits; n++) {
loopCount = loopCount * maxDigit;
+ digits[n] = 1;
}
// Start with a sum or product of all 1's, then check all possibilities.
- digits.fill (1, nDigits);
currentValue = (cageOperator == Add) ? nDigits : 1;
for (int n = 0; n < loopCount; n++) {
if (currentValue == requiredValue) {
@@ -631,7 +631,9 @@ void CageGenerator::setPossibleAddsOrMultiplies
digitsOK = isSelfConsistent (cage, nDigits, digits);
}
if (digitsOK) {
- mPossibilities->append (QList<int>::fromVector (digits));
+ for (int n = 0; n < nDigits; n++) {
+ mPossibilities->append (digits[n]);
+ }
nCons++;
}
#ifdef MATHDOKU_LOG
@@ -651,21 +653,19 @@ void CageGenerator::setPossibleAddsOrMultiplies
// Calculate the next set of possible digits (as in an odometer).
for (int d = 0; d < nDigits; d++) {
digits[d]++;
- if (digits.at (d) > maxDigit) { // Carry 1.
- digits[d] -= maxDigit;
+ currentValue++; // Use prev sum, to save time.
+ if (digits[d] > maxDigit) { // Carry 1.
+ digits[d] -= maxDigit;
+ currentValue -= maxDigit;
}
else {
break; // No carry.
}
}
- // Calculate the sum or product of this set of digits.
- currentValue = (cageOperator == Add) ? 0 : 1;
- for (int d = 0; d < nDigits; d++) {
- if (cageOperator == Add) {
- currentValue += digits[d];
- }
- else {
+ if (cageOperator == Multiply) {
+ currentValue = 1;
+ for (int d = 0; d < nDigits; d++) {
currentValue *= digits[d];
}
}
@@ -676,35 +676,32 @@ void CageGenerator::setPossibleAddsOrMultiplies
#endif
}
-bool CageGenerator::hasDuplicates (int nDigits, QVector<int> digits)
+bool CageGenerator::hasDuplicates (int nDigits, int digits[])
{
- QVector<bool> usedDigits;
- usedDigits.fill (false, mOrder + 1); // Digits range is 1->order.
+ int usedDigits = 0;
+ int mask = 0;
for (int n = 0; n < nDigits; n++) {
- int digit = digits.at (n);
- if (usedDigits.at (digit)) {
+ mask = 1 << digits[n];
+ if (usedDigits & mask) {
return true;
}
- usedDigits[digit] = true;
+ usedDigits |= mask;
}
return false;
}
bool CageGenerator::isSelfConsistent (const QVector<int> cage,
- int nDigits, QVector<int> digits)
+ int nDigits, int digits[])
{
QVector<int> usedGroups;
+ int mask = 0;
+ int cell;
usedGroups.fill (0, mGraph->cliqueCount());
for (int n = 0; n < nDigits; n++) {
- int cell = cage.at (n);
- int digit = digits.at (n);
- int mask = 1 << digit;
+ cell = cage.at (n);
+ mask = 1 << digits[n];
QList<int> groupList = mGraph->cliqueList (cell);
Q_FOREACH (int group, groupList) {
- // qDebug() << "Digit" << (n + 1) << "value" << digit << "mask"
- // << mask << "position" << cell << "conflict group"
- // << group << "cells" << mGraph->clique (group)
- // << "group mask" << usedGroups.at (group);
if (mask & usedGroups.at (group)) {
return false;
}
diff --git a/src/generator/cagegenerator.h b/src/generator/cagegenerator.h
index 231acef..e90df15 100644
--- a/src/generator/cagegenerator.h
+++ b/src/generator/cagegenerator.h
@@ -174,12 +174,11 @@ private:
CageOperator cageOperator, int cageValue);
// Check if a cage contains duplicate digits (not allowed in Killer Sudoku).
- bool hasDuplicates (int nDigits, QVector<int> digits);
+ bool hasDuplicates (int nDigits, int digits[]);
// Check if a combo of digits in a cage satisfies Sudoku rules (a Mathdoku
// cage can contain a digit more than once, but not in the same row/column).
- bool isSelfConsistent (const QVector<int> cage, int nDigits,
- QVector<int> digits);
+ bool isSelfConsistent (const QVector<int> cage, int nDigits, int digits[]);
// Initialise the cage generator for a particular size and type of puzzle.
void init (SKGraph * graph, bool hiddenOperators);
diff --git a/src/globals.h b/src/globals.h
index 7c04202..0a3754b 100644
--- a/src/globals.h
+++ b/src/globals.h
@@ -38,6 +38,9 @@ enum CageOperator {NoOperator, Divide, Subtract, Multiply, Add};
typedef QVector<int> BoardContents;
+// The maximum digit that can be used in a Mathdoku or Killer Sudoku puzzle.
+const int MaxMathOrder = 9;
+
typedef struct {
char * typeName;
SudokuType type;