diff --git a/src/generator/cagegenerator.cpp b/src/generator/cagegenerator.cpp index 54a85e1..b988a11 100644 --- a/src/generator/cagegenerator.cpp +++ b/src/generator/cagegenerator.cpp @@ -1,770 +1,769 @@ /**************************************************************************** * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or * * modify it under the terms of the GNU General Public License as * * published by the Free Software Foundation; either version 2 of * * the License, or (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program. If not, see . * ****************************************************************************/ #include "cagegenerator.h" #include "ksudoku_logging.h" #include "globals.h" #include "skgraph.h" #include "dlxsolver.h" -#include // #define MATHDOKU_LOG CageGenerator::CageGenerator (const BoardContents & solution) : mSolution (solution) { mMinSingles = 2; mMaxSingles = 4; mDLXSolver = new DLXSolver (this); // Auto-deleted by QObject. mPossibilities = new QList(); mPossibilitiesIndex = new QList(); } CageGenerator::~CageGenerator() { mPossibilities->clear(); mPossibilitiesIndex->clear(); delete mPossibilities; delete mPossibilitiesIndex; } int CageGenerator::makeCages (SKGraph * graph, QList * solutionMoves, int maxSize, int maxValue, bool hideOperators, int maxCombos) { // TODO - Use maxValue when OK'ing cages(?). // TODO - Experiment with mMinSingles and mMaxSingles. Make them parameters? QList saveUnusedCells; QList saveNeighbourFlags; #ifdef MATHDOKU_LOG QVector usedCells; #endif mMaxCombos = maxCombos; init (graph, hideOperators); graph->clearCages(); mPossibilities->clear(); mPossibilitiesIndex->clear(); mPossibilitiesIndex->append(0); mSingles = 0; #ifdef MATHDOKU_LOG usedCells.fill ('-', mBoardArea); qCDebug(KSudokuLog) << "USED CELLS " << usedCells; #endif // TODO - Will probably need to limit the number of size-1 cages and maybe // guarantee a minimum number as well. // TODO - Might need to generate at least one maximum-size cage first.. /* 1. Select the starting point and size for a cage. Top priority for a starting point is a cell that is surrounded on three or four sides, otherwise the cell is chosen at random from the list of unused cells.s A cell surrounded on four sides must become a single-cell cage, with a pre-determined value and no operator. Choosing a cell surrounded on three sides allows the cage to occupy and grow out of tight corners, avoiding an excess of small and single-cell cages. The chosen size is initially 1 (needed to control the difficulty of the puzzle) and later a random number from 2 to the maximum cage-size. The maximum cage-size also affects difficulty. 2. Use the function makeOneCage() to make a cage of the required size. The makeOneCage() function keeps adding unused neighbouring cells until the required size is reached or it runs out of space to grow the cage further. It updates the lists of used cells and neighbours as it goes. A neighbour that would otherwise become surrounded on all four sides is always added to the cage as it grows, but normally the next cell is chosen randomly. 3. Use the function setCageTarget() to choose an operator (+*-/), calculate the cage's value from the cell-values in the puzzle's solution and find all the possible combinations of values that cells in the cage *might* have, as seen by the user. The possible combinations are used when solving the generated puzzle, using the DLX algorithm, to check that the puzzle has a unique solution. Many generated puzzles have multiple solutions and have to be discarded. 4. Validate the cage, using function isCageOK(). A cage can be rejected if it might make the puzzle too hard or too easy. If so, discard the cage, back up and repeat steps 1 to 4. 5. Repeat steps 1 to 4 until all cells have been assigned to cages. */ int numFailures = 0; int maxFailures = 20; while (mUnusedCells.count() > 0) { QVector cage; CageOperator cageOperator; int cageValue; int chosenSize; int index = -1; for (const int n : qAsConst(mUnusedCells)) { switch (mNeighbourFlags.at (n)){ case 7: case 11: case 13: case 14: index = n; // Enclosed on three sides: start here. chosenSize = qrand() % (maxSize - 1) + 2; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "CHOSE CUL-DE-SAC" << mNeighbourFlags.at (n) << "at" << index; #endif break; case 15: index = n; // Isolated cell: size 1 is forced. chosenSize = 1; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "CHOSE ISOLATED" << mNeighbourFlags.at (n) << "at" << index; #endif break; default: break; } if (index >= 0) { break; } } if (index < 0) { // Pick a starting cell at random. index = mUnusedCells.at (qrand() % mUnusedCells.count()); if (mSingles < mMinSingles) { chosenSize = 1; // Start with size 1. mSingles++; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "INITIAL SINGLE" << mSingles; #endif } else { chosenSize = qrand()%(maxSize - 1) + 2; // Then avoid size 1. } } #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "chosenSize" << chosenSize << "cell" << index; #endif saveUnusedCells = mUnusedCells; saveNeighbourFlags = mNeighbourFlags; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "CALL makeOneCage: index" << index << "size" << chosenSize; #endif cage = makeOneCage (index, chosenSize); setCageTarget (cage, cageOperator, cageValue); if (! cageIsOK (cage, cageOperator, cageValue)) { mUnusedCells = saveUnusedCells; mNeighbourFlags = saveNeighbourFlags; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "CAGE IS NOT OK - unused" << mUnusedCells; #endif numFailures++; if (numFailures >= maxFailures) { qCDebug(KSudokuLog) << "makeOneCage() HAD" << numFailures << "failures" << "maximum is" << maxFailures; return 0; // Too many problems with making cages. } continue; } // The cage is OK: add it to the puzzle's layout. mGraph->addCage (cage, cageOperator, cageValue); #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "CAGE" << mGraph->cageCount() << cage; char tag = 'a' + mGraph->cageCount() - 1; for (const int cell : qAsConst(cage)) { usedCells[cell] = tag; } qCDebug(KSudokuLog) << "LAYOUT" << tag << usedCells; for (int row = 0; row < mOrder; row++) { for (int col = 0; col < mOrder; col++) { fprintf (stderr, "%c ", usedCells.at (col * mOrder + row)); } fprintf (stderr, "\n"); } fprintf (stderr, "\n"); #endif QList flagsList; for (const int cell : qAsConst(mUnusedCells)) { flagsList.append (mNeighbourFlags.at (cell)); } #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "FLAGS" << flagsList; qCDebug(KSudokuLog) << "UNUSED" << mUnusedCells; #endif } int nCages = mPossibilitiesIndex->count() - 1; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "Cages in mPossibilitiesIndex" << nCages << "generated cages" << mGraph->cageCount(); #endif int totCombos = 0; for (int n = 0; n < nCages; n++) { int nVals = mPossibilitiesIndex->at (n+1) - mPossibilitiesIndex->at (n); int size = mGraph->cage (n).size(); int nCombos = nVals / size; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "Cage" << n << "values" << nVals << "size" << size << "combos" << nCombos << "target" << mGraph->cageValue(n) << "op" << mGraph->cageOperator(n) << "topleft" << mGraph->cageTopLeft(n); #endif totCombos += nCombos; } #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "TOTAL COMBOS" << totCombos; #endif // Use the DLX solver to check if this puzzle has a unique solution. int nSolutions = mDLXSolver->solveMathdoku (mGraph, solutionMoves, mPossibilities, mPossibilitiesIndex, 2); if (nSolutions == 0) { #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "FAILED TO FIND A SOLUTION: nSolutions =" << nSolutions; #endif return -1; // At least one solution must exist. } else if (nSolutions > 1) { #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "NO UNIQUE SOLUTION: nSolutions =" << nSolutions; #endif return -1; // There must only one solution. } #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "UNIQUE SOLUTION FOUND: nSolutions =" << nSolutions; #endif return mGraph->cageCount(); } int CageGenerator::checkPuzzle (SKGraph * graph, BoardContents & solution, QList * solutionMoves, bool hideOperators) { #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "CageGenerator::checkPuzzle(): nCAGES" << graph->cageCount(); #endif int result = 0; mGraph = graph; mOrder = graph->order(); mBoardArea = mOrder * mOrder; mKillerSudoku = (graph->specificType() == KillerSudoku); // Only Mathdoku puzzles can have hidden operators as part of the *puzzle*. // KillerSudoku has + or NoOp and makes the +'s hidden only in the *view*. mHiddenOperators = mKillerSudoku ? false : hideOperators; qCDebug(KSudokuLog) << "CHECK 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 qCDebug(KSudokuLog) << "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 int nVals = mPossibilitiesIndex->at (n+1) - mPossibilitiesIndex->at (n); int size = mGraph->cage (n).size(); int nCombos = nVals / size; qCDebug(KSudokuLog) << "Cage" << n << "values" << nVals << "size" << size << "combos" << nCombos << "target" << mGraph->cageValue(n) << "op" << mGraph->cageOperator(n) << "topleft" << mGraph->cageTopLeft(n); #endif } #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "POSSIBILITIES SET: now check-solve the puzzle."; qCDebug(KSudokuLog) << "INDEX" << (*mPossibilitiesIndex); qCDebug(KSudokuLog) << "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 CageGenerator::makeOneCage (int seedCell, int requiredSize) { QVector cage; QList unusedNeighbours; const int direction[4] = {N, E, S, W}; const int increment[4] = {-1, +mOrder, +1, -mOrder}; const int opposite[4] = {S, W, N, E}; int index = seedCell; cage.clear(); unusedNeighbours.clear(); unusedNeighbours.append (index); while (true) { // Update the chosen cell's neighbours. int flags = mNeighbourFlags.at (index); for (int k = 0; k < 4; k++) { if (flags & direction[k]) { continue; // Already flagged. } int nb = index + increment[k]; mNeighbourFlags[nb] = mNeighbourFlags[nb] | opposite[k]; if (mUnusedCells.indexOf (nb) >= 0) { unusedNeighbours.append (nb); } } #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "index" << index << "NEIGHBOURS" << unusedNeighbours; #endif mUnusedCells.removeAt (mUnusedCells.indexOf (index)); mNeighbourFlags[index] = TAKEN; cage.append (index); if (cage.size() >= requiredSize) { break; } int unb = unusedNeighbours.indexOf (index); while (unb >= 0) { unusedNeighbours.removeAt (unb); unb = unusedNeighbours.indexOf (index); } if (unusedNeighbours.isEmpty()) { break; } // Pick a neighbour to be added to the cage. index = -1; for (const int unb : qAsConst(unusedNeighbours)) { flags = mNeighbourFlags.at (unb); if (flags == 15) { // Choose a cell that has been surrounded and isolated. index = unb; break; } } if (index < 0) { // Otherwise, choose a neighbouring cell at random. unb = qrand() % unusedNeighbours.count(); index = unusedNeighbours.at (unb); } } return cage; } void CageGenerator::setCageTarget (const QVector &cage, CageOperator & cageOperator, int & cageValue) { CageOperator op; int value = 0; int size = cage.size(); QVector digits; digits.fill (0, size); #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "CAGE SIZE" << size << "CONTENTS" << cage; #endif for (int n = 0; n < size; n++) { int digit = mSolution.at (cage.at(n)); digits[n] = digit; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "Add cell" << cage.at(n) << "value" << mSolution.at (cage.at(n)) << (n + 1) << "cells"; // : total" << value; #endif } if (size == 1) { cageOperator = NoOperator; cageValue = digits[0]; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "SINGLE CELL: #" << mSingles << "val" << cageValue; #endif return; } int lo = 0; int hi = 0; if (mKillerSudoku) { // Killer Sudoku has an Add operator for every calculated cage. op = Add; } else { // Mathdoku has a randomly chosen operator for each calculated cage. int weights[4] = {50, 30, 15, 15}; CageOperator ops[4] = {Divide, Subtract, Multiply, Add}; if (size != 2) { weights[0] = weights[1] = 0; } else { lo = qMin (digits[0], digits[1]); hi = qMax (digits[0], digits[1]); weights[0] = ((hi % lo) == 0) ? 50 : 0; } int roll = qrand() % (weights[0]+weights[1]+weights[2]+weights[3]); #ifdef MATHDOKU_LOG int wTotal = (weights[0]+weights[1]+weights[2]+weights[3]); qCDebug(KSudokuLog) << "ROLL" << roll << "VERSUS" << wTotal << "WEIGHTS" << weights[0] << weights[1] << weights[2] << weights[3]; #endif int n = 0; while (n < 4) { roll = roll - weights[n]; if (roll < 0) { break; } n++; } op = ops[n]; } switch (op) { case Divide: value = hi / lo; break; case Subtract: value = hi - lo; break; case Multiply: value = 1; for (int i = 0; i < size; i++) { value = value * digits[i]; } break; case Add: value = 0; for (int i = 0; i < size; i++) { value = value + digits[i]; } break; default: break; } #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "CHOSE OPERATOR" << op << "value" << value << digits; #endif cageOperator = op; cageValue = value; } bool CageGenerator::cageIsOK (const QVector &cage, CageOperator cageOperator, int cageValue) { // TODO - Is it worth checking for duplicate digits in Mathdoku, before // going the whole hog and checking for constraint satisfaction? // NOTE - The solution, by definition, has to satisfy constraints, even // if it does have duplicate digits (ie. those digits must be in // different rows/columns/boxes). int nDigits = cage.size(); // In Killer Sudoku, the cage's solution must not contain duplicate digits. if (mKillerSudoku) { QVector usedDigits; usedDigits.fill (false, mOrder + 1); // Digits' range is 1->order. for (int n = 0; n < nDigits; n++) { int digit = mSolution.at (cage.at(n)); if (usedDigits.at (digit)) { #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "SOLUTION VALUES CONTAIN DUPLICATE" << digit; #endif return false; // Cannot use this cage. } usedDigits[digit] = true; } } // Get all possibilities and keep checking, as we go, that the cage is OK. bool isOK = true; setAllPossibilities (cage, nDigits, cageOperator, cageValue); int numPoss = (mPossibilities->size() - mPossibilitiesIndex->last()); // There should be some possibilities and not too many (wrt difficulty). isOK &= (numPoss > 0); isOK &= ((numPoss / nDigits) <= mMaxCombos); if (isOK) { // Save the possibilities, for use when testing the puzzle solution. mPossibilitiesIndex->append (mPossibilities->size()); } else { // Discard the possibilities: this cage is no good. #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "CAGE REJECTED: combos" << (numPoss / nDigits) << "max" << mMaxCombos << cage << cageValue << cageOperator; #endif while (numPoss > 0) { mPossibilities->removeLast(); numPoss--; } } return isOK; } void CageGenerator::setAllPossibilities (const QVector &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 &cage, CageOperator cageOperator, int cageValue) { // Generate sets of possible solution-values from the range 1 to mOrder. switch (cageOperator) { case NoOperator: mPossibilities->append (cageValue); break; case Add: case Multiply: setPossibleAddsOrMultiplies (cage, cageOperator, cageValue); break; case Divide: for (int a = 1; a <= mOrder; a++) { for (int b = 1; b <= mOrder; b++) { if ((a == b * cageValue) || (b == a * cageValue)) { *mPossibilities << a << b; } } } break; case Subtract: for (int a = 1; a <= mOrder; a++) { for (int b = 1; b <= mOrder; b++) { if (((a - b) == cageValue) || ((b - a) == cageValue)) { *mPossibilities << a << b; } } } break; } } void CageGenerator::setPossibleAddsOrMultiplies (const QVector &cage, CageOperator cageOperator, int requiredValue) { int digits[MaxMathOrder]; // Maximum order of maths-based puzzles == 9. int maxDigit = mOrder; int nDigits = cage.size(); int currentValue; int nTarg = 0; int nCons = 0; #ifdef MATHDOKU_LOG int nDupl = 0; int nIncons = 0; #endif int loopCount = 1; // 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. currentValue = (cageOperator == Add) ? nDigits : 1; for (int n = 0; n < loopCount; n++) { if (currentValue == requiredValue) { nTarg++; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "TARGET REACHED" << requiredValue << "OP" << cageOperator << "DIGITS" << digits; #endif bool digitsOK = false; // In Killer Sudoku, all digits in the cage must be unique. if (mKillerSudoku) { // If so, there will be no breaches of Sudoku rules in the // intersections of rows, columns and blocks with that cage, // thus there is no need to do the isSelfConsistent() check. digitsOK = ! hasDuplicates (nDigits, digits); } // In Mathdoku, duplicate digits are OK, subject to Sudoku rules. else { digitsOK = isSelfConsistent (cage, nDigits, digits); } if (digitsOK) { for (int n = 0; n < nDigits; n++) { mPossibilities->append (digits[n]); } nCons++; } #ifdef MATHDOKU_LOG if (mKillerSudoku) { nDupl = digitsOK ? nDupl : nDupl++; qCDebug(KSudokuLog) << "CONTAINS DUPLICATES: KillerSudoku cage" << digitsOK << digits << "cage" << cage; } else { nIncons = digitsOK ? nIncons : nIncons++; qCDebug(KSudokuLog) << "SELF CONSISTENT: Mathdoku cage" << digitsOK << digits << "cage" << cage; } #endif } // Calculate the next set of possible digits (as in an odometer). for (int d = 0; d < nDigits; d++) { digits[d]++; currentValue++; // Use prev sum, to save time. if (digits[d] > maxDigit) { // Carry 1. digits[d] -= maxDigit; currentValue -= maxDigit; } else { break; // No carry. } } if (cageOperator == Multiply) { currentValue = 1; for (int d = 0; d < nDigits; d++) { currentValue *= digits[d]; } } } #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << loopCount << "possibles" << nTarg << "hit target" << nDupl << "had duplicate(s)" << nCons << "consistent"; #endif } bool CageGenerator::hasDuplicates (int nDigits, int digits[]) { int usedDigits = 0; int mask = 0; for (int n = 0; n < nDigits; n++) { mask = 1 << digits[n]; if (usedDigits & mask) { return true; } usedDigits |= mask; } return false; } bool CageGenerator::isSelfConsistent (const QVector &cage, int nDigits, int digits[]) { QVector usedGroups; int mask = 0; int cell; usedGroups.fill (0, mGraph->cliqueCount()); for (int n = 0; n < nDigits; n++) { cell = cage.at (n); mask = 1 << digits[n]; const QList groupList = mGraph->cliqueList (cell); for (const int group : groupList) { if (mask & usedGroups.at (group)) { return false; } usedGroups [group] |= mask; } } return true; } void CageGenerator::init (SKGraph * graph, bool hideOperators) { /* INITIAL SETUP FOR THE CageGenerator. 1. Mark all cells as unused (for cages). This is represented by a list of unused cells (QList) containing cell-indices. 2. Make a list showing blocked sides (NSWE bitmap) of each cell. A blocked side means that there is a cell assigned to a cage on that side. Cells at the edges or corners of the board are set up to have imaginary (dummy) cages as neighbours. */ mGraph = graph; mOrder = graph->order(); mBoardArea = mOrder * mOrder; // Only Mathdoku puzzles can have hidden operators as part of the *puzzle*. // KillerSudoku has + or NoOp and makes the +'s hidden only in the *view*. mKillerSudoku = (graph->specificType() == KillerSudoku); mHiddenOperators = mKillerSudoku ? false : hideOperators; #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "MAKE CAGES init(): HIDDEN OPERATORS" << mHiddenOperators; #endif mUnusedCells.clear(); mNeighbourFlags.clear(); for (int n = 0; n < mBoardArea; n++) { mUnusedCells.append (n); int col = graph->cellPosX (n); int row = graph->cellPosY (n); int limit = mOrder - 1; int neighbours = ALONE; // Mark cells on the perimeter of the board as having dummy neighbours. if (row == 0) { neighbours = neighbours | N; // Cell to the North is unavailable. } if (row == limit) { neighbours = neighbours | S; // Cell to the South is unavailable. } if (col == 0) { neighbours = neighbours | W; // Cell to the West is unavailable. } if (col == limit) { neighbours = neighbours | E; // Cell to the East is unavailable. } mNeighbourFlags.append (neighbours); } #ifdef MATHDOKU_LOG qCDebug(KSudokuLog) << "UNUSED CELLS " << mUnusedCells; qCDebug(KSudokuLog) << "NEIGHBOUR-FLAGS" << mNeighbourFlags; #endif } diff --git a/src/generator/dlxsolver.cpp b/src/generator/dlxsolver.cpp index aa8ae53..7b9efdc 100644 --- a/src/generator/dlxsolver.cpp +++ b/src/generator/dlxsolver.cpp @@ -1,776 +1,775 @@ /**************************************************************************** * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or * * modify it under the terms of the GNU General Public License as * * published by the Free Software Foundation; either version 2 of * * the License, or (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program. If not, see . * ****************************************************************************/ #include "dlxsolver.h" #include "ksudoku_logging.h" #include "globals.h" -#include // #define DLX_LOG DLXSolver::DLXSolver (QObject * parent) : QObject (parent), mBoardValues (0), mSolutionMoves(0), mGraph (0) { #ifdef DLX_LOG qCDebug(KSudokuLog) << "DLXSolver constructor entered"; #endif mCorner = new DLXNode; clear(); } DLXSolver::~DLXSolver() { #ifdef DLX_LOG qCDebug(KSudokuLog) << "DLXSolver destructor entered"; #endif deleteAll(); delete mCorner; } void DLXSolver::printDLX (bool forced) { #ifdef DLX_LOG bool verbose = (forced || (mGraph->order() <= 5)); if ((mEndNodeNum < 0) || (mEndColNum < 0)) { qCDebug(KSudokuLog, "DLXSolver::printDLX(): EMPTY, mEndNodeNum %d, " "mEndRowNum %d, mEndColNum %d", mEndNodeNum, mEndRowNum, mEndColNum); return; } // fprintf (stderr, "\nDLX Matrix has %d cols, %d rows and %d ones\n\n", // mEndColNum + 1, mEndRowNum + 1, mEndNodeNum + 1); DLXNode * colDLX = mCorner->right; if (colDLX == mCorner) { fprintf (stderr, "DLXSolver::printDLX(): ALL COLUMNS ARE HIDDEN\n"); return; } int totGap = 0; int nRows = 0; int nNodes = 0; int lastCol = -1; QVector rowsRemaining; rowsRemaining.fill (0, mRows.count()); if (verbose) fprintf (stderr, "\n"); while (colDLX != mCorner) { int col = mColumns.indexOf(colDLX); if (verbose) fprintf (stderr, "Col %02d, %02d rows ", col, mColumns.at(col)->value); DLXNode * node = mColumns.at(col)->below; while (node != colDLX) { int rowNum = node->value; if (verbose) fprintf (stderr, "%02d ", rowNum); if (rowsRemaining.at (rowNum) == 0) { nRows++; } rowsRemaining[rowNum] = mRows.at (rowNum); nNodes++; node = node->below; } int gap = col - (lastCol + 1); if (gap > 0) { if (verbose) fprintf (stderr, "covered %02d", gap); totGap = totGap + gap; } if (verbose) fprintf (stderr, "\n"); colDLX = colDLX->right; lastCol = col; } if (verbose) fprintf (stderr, "\n"); fprintf (stderr, "Matrix NOW has %d rows, %d columns and %d ones\n", nRows, lastCol + 1 - totGap, nNodes); #else Q_UNUSED (forced); #endif } void DLXSolver::recordSolution (const int solutionNum, QList & solution) { // Extract a puzzle solution from the DLX solver into mBoardValues. There // may be many solutions, found at various times as the solver proceeds. // TODO - DLXSolver's solutions are not needed for anything in KSudoku: we // just need to know if there is more than 1 solution. In the future, // maybe each solution could be returned via a signal-slot mechanism. int order = mGraph->order(); int nCages = mGraph->cageCount(); SudokuType t = mGraph->specificType(); if (mSolutionMoves) { mSolutionMoves->clear(); } #ifdef DLX_LOG qCDebug(KSudokuLog) << "NUMBER OF ROWS IN SOLUTION" << solution.size(); #endif if ((t == Mathdoku) || (t == KillerSudoku)) { for (int n = 0; n < solution.size(); n++) { int rowNumDLX = solution.at (n)->value; int searchRow = 0; #ifdef DLX_LOG qCDebug(KSudokuLog) << " Node" << n << "row number" << rowNumDLX; #endif for (int nCage = 0; nCage < nCages; nCage++) { int cageSize = mGraph->cage (nCage).size(); int nCombos = (mPossibilitiesIndex->at (nCage + 1) - mPossibilitiesIndex->at (nCage)) / cageSize; if ((searchRow + nCombos) <= rowNumDLX) { searchRow += nCombos; continue; } int comboNum = rowNumDLX - searchRow; int comboValues = mPossibilitiesIndex->at (nCage) + (comboNum * cageSize); #ifdef DLX_LOG qCDebug(KSudokuLog) << "Solution node" << n << "cage" << nCage << mGraph->cage (nCage) << "combos" << nCombos; qCDebug(KSudokuLog) << "Search row" << searchRow << "DLX row" << rowNumDLX << "cageSize" << cageSize << "combo" << comboNum << "values at" << comboValues; #endif const QVector cage = mGraph->cage (nCage); for (const int cell : cage) { #ifdef DLX_LOG 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++; } #ifdef DLX_LOG fprintf (stderr, "\n\n"); #endif break; } } } else { // Sudoku or Roxdoku variant. for (DLXNode * node : qAsConst(solution)) { int rowNumDLX = node->value; mBoardValues [rowNumDLX/order] = (rowNumDLX % order) + 1; } } #ifdef DLX_LOG fprintf (stderr, "\nSOLUTION %d\n\n", solutionNum); printSudoku(); #else Q_UNUSED (solutionNum); #endif } void DLXSolver::retrieveSolution (BoardContents & solution) { solution = mBoardValues; } void DLXSolver::printSudoku() { // TODO - The code at SudokuBoard::print() is VERY similar... #ifdef DLX_LOG // Used for test and debug, but the format is also parsable and loadable. char nLabels[] = "123456789"; char aLabels[] = "abcdefghijklmnopqrstuvwxy"; int index, value; int order = mGraph->order(); int blockSize = mGraph->base(); int sizeX = mGraph->sizeX(); int sizeY = mGraph->sizeY(); int sizeZ = mGraph->sizeZ(); // If 2-D, depth == 1, else depth > 1. for (int k = 0; k < sizeZ; k++) { int z = (sizeZ > 1) ? (sizeZ - k - 1) : k; for (int j = 0; j < sizeY; j++) { if ((j != 0) && (j % blockSize == 0)) { fprintf (stderr, "\n"); // Gap between square blocks. } int y = (sizeZ > 1) ? (sizeY - j - 1) : j; for (int x = 0; x < sizeX; x++) { index = mGraph->cellIndex (x, y, z); value = mBoardValues.at (index); if (x % blockSize == 0) { fprintf (stderr, " "); // Gap between square blocks. } if (value == UNUSABLE) { fprintf (stderr, " '"); // Unused cell (e.g. in Samurai). } else if (value == VACANT) { fprintf (stderr, " -"); // Empty cell (to be solved). } else { value--; char label = (order > 9) ? aLabels[value] : nLabels[value]; fprintf (stderr, " %c", label); // Given cell (or clue). } } fprintf (stderr, "\n"); // End of row. } fprintf (stderr, "\n"); // Next Z or end of 2D puzzle/solution. } #endif } int DLXSolver::solveSudoku (SKGraph * graph, const BoardContents & boardValues, int solutionLimit) { // NOTE: This procedure is not actually used in KSudoku, but was used to // develop and test solveDLX(), using Sudoku and Roxdoku puzzles. It // turned out that solveSudoku(), using DLX, was not significantly // faster than the methods in the SudokuBoard class and had the // disadvantage that no method to assess puzzle difficulty could // be found for solveDLX(). mBoardValues = boardValues; // Used later for filling in a solution. mGraph = graph; int nSolutions = 0; int order = graph->order(); int boardArea = graph->size(); int nGroups = graph->cliqueCount(); int vacant = VACANT; int unusable = UNUSABLE; #ifdef DLX_LOG qCDebug(KSudokuLog) << "TEST for DLXSolver"; printSudoku(); qCDebug(KSudokuLog) << "DLXSolver::solve: Order" << order << "boardArea" << boardArea << "nGroups" << nGroups; #endif // Generate a DLX matrix for an empty Sudoku grid of the required type. // It has (boardArea*order) rows and (boardArea + nGroups*order) columns. clear(); // Empty the DLX matrix. mColumns.clear(); mRows.clear(); for (int n = 0; n < (boardArea + nGroups*order); n++) { mColumns.append (mCorner); } for (int n = 0; n < (boardArea*order); n++) { mRows.append (mCorner); } // Exclude constraints for unusable cells and already-filled cells (clues). for (int index = 0; index < boardArea; index++) { if (boardValues.at(index) != vacant) { #ifdef DLX_LOG qCDebug(KSudokuLog) << "EXCLUDE CONSTRAINT for cell" << index << "value" << boardValues.at(index); #endif mColumns[index] = 0; for (int n = 0; n < order; n++) { mRows[index*order + n] = 0; // Drop row. } if (boardValues.at(index) == unusable) { continue; } // Get a list of groups (row, column, etc.) that contain this cell. const QList groups = graph->cliqueList (index); #ifdef DLX_LOG int row = graph->cellPosY (index); int col = graph->cellPosX (index); qCDebug(KSudokuLog) << "CLUE AT INDEX" << index << "value" << boardValues.at(index) << "row" << row << "col" << col << "groups" << groups; #endif int val = boardValues.at(index) - 1; for (const int group : groups) { #ifdef DLX_LOG qCDebug(KSudokuLog) << "EXCLUDE CONSTRAINT" << (boardArea+group*order+val); #endif mColumns[boardArea + group*order + val] = 0; const QVector clique = graph->clique (group); for (const int cell : clique) { mRows[cell*order + val] = 0; // Drop row. } } } } // Create the initial set of columns. for (DLXNode * colDLX : qAsConst(mColumns)) { mEndColNum++; // If the constraint is not excluded, put an empty column in the matrix. if (colDLX != 0) { DLXNode * node = allocNode(); mColumns[mEndColNum] = node; initNode (node); addAtRight (node, mCorner); } } // Generate the initial DLX matrix. int rowNumDLX = 0; for (int index = 0; index < boardArea; index++) { // Get a list of groups (row, column, etc.) that contain this cell. const QList groups = graph->cliqueList (index); #ifdef DLX_LOG int row = graph->cellPosY (index); int col = graph->cellPosX (index); qCDebug(KSudokuLog) << " Index" << index << "row" << row << "col" << col << "groups" << groups; #endif // Generate a row for each possible value of this cell in the Sudoku // grid, representing part of a possible solution. Each row must have // 1's in columns that correspond to a constraint on the cell and on the // value (in each group to which the cell belongs --- row, column, etc). for (int possValue = 0; possValue < order; possValue++) { #ifdef DLX_LOG QString s = (mRows.at (rowNumDLX) == 0) ? "DROPPED" : "OK"; qCDebug(KSudokuLog) << "Row" << rowNumDLX << s; #endif if (mRows.at (rowNumDLX) != 0) { // Skip already-excluded rows. mRows[rowNumDLX] = 0; // Re-initialise a "live" row. addNode (rowNumDLX, index); // Mark cell fill-in constraint. for (const int group : groups) { // Mark possibly-satisfied constraints for row, column, etc. addNode (rowNumDLX, boardArea + group*order + possValue); } } rowNumDLX++; } } #ifdef DLX_LOG printDLX(true); qCDebug(KSudokuLog) << "Matrix MAX had " << mRows.count() << " rows, " << mColumns.count() << " columns and " << ((boardArea + nGroups*order)*order) << " ones"; qCDebug(KSudokuLog) << "CALL solveDLX(), solution limit" << solutionLimit; #endif // Solve the DLX-matrix equivalent of the Sudoku-style puzzle. nSolutions = solveDLX (solutionLimit); #ifdef DLX_LOG qCDebug(KSudokuLog) << "FOUND" << nSolutions << "solutions, limit" << solutionLimit; #endif return nSolutions; } int DLXSolver::solveMathdoku (SKGraph * graph, QList * solutionMoves, const QList * possibilities, const QList * possibilitiesIndex, int solutionLimit) { mSolutionMoves = solutionMoves; #ifdef DLX_LOG qCDebug(KSudokuLog) << "DLXSolver::solveMathdoku ENTERED" << possibilities->size() << "possibilities" << possibilitiesIndex->size() << "index size"; #endif int nSolutions = 0; int order = graph->order(); int nCages = graph->cageCount(); int nGroups = graph->cliqueCount(); // Save these pointers for use later, in recordSolution(). mGraph = graph; mPossibilities = possibilities; mPossibilitiesIndex = possibilitiesIndex; mBoardValues.fill (0, order * order); // Create an empty DLX matrix. clear(); mColumns.clear(); mRows.clear(); // Create the initial set of columns. for (int n = 0; n < (nCages + nGroups * order); n++) { mEndColNum++; // Put an empty column in the matrix. DLXNode * node = allocNode(); mColumns.append (node); initNode (node); addAtRight (node, mCorner); } int rowNumDLX = 0; int counter = 0; for (int n = 0; n < nCages; n++) { int size = graph->cage (n).size(); int nVals = possibilitiesIndex->at (n + 1) - possibilitiesIndex->at (n); int nCombos = nVals / size; int index = possibilitiesIndex->at (n); #ifdef DLX_LOG qCDebug(KSudokuLog) << "CAGE" << n << "of" << nCages << "size" << size << "nCombos" << nCombos << "nVals" << nVals << "index" << index << "of" << possibilities->size(); #endif for (int nCombo = 0; nCombo < nCombos; nCombo++) { mRows.append (0); // Start a row for each combo. addNode (rowNumDLX, n); // Mark the cage's fill-in constraint. counter++; #ifdef DLX_LOG qCDebug(KSudokuLog) << "Add cage-node: row" << rowNumDLX << "cage" << n << graph->cage (n); #endif const QVector cage = graph->cage (n); for (const int cell : cage ) { int possVal = possibilities->at (index); // qCDebug(KSudokuLog) << " Cell" << cell << "possVal" << possVal; const QList cliqueList = graph->cliqueList (cell); for (const int group : cliqueList) { // Poss values go from 0 to (order - 1) in DLX (so -1 here). addNode (rowNumDLX, nCages + group * order + possVal - 1); counter++; } index++; } rowNumDLX++; } } qCDebug(KSudokuLog) << "DLX MATRIX HAS" << mColumns.size() << "cols" << mRows.size() << "rows" << counter << "nodes"; nSolutions = solveDLX (solutionLimit); return nSolutions; } /* TODO - Delete this eventually. void DLXSolver::testDLX () { const int test [6][7] = { {1,0,0,1,0,0,1}, {1,0,0,1,0,0,0}, {0,0,0,1,1,0,1}, {0,0,1,0,1,1,0}, {0,1,1,0,0,1,1}, {0,1,0,0,0,0,1} }; const int w = 7; const int h = 6; fprintf (stderr, "\nTEST MATRIX\n"); for (int row = 0; row < h; row++) { for (int col = 0; col < w; col++) { fprintf (stderr, " %d", test[row][col]); } fprintf (stderr, "\n"); } fprintf (stderr, "\n"); for (int row = 0; row < h; row++) { for (int col = 0; col < w; col++) { if (test[row][col]) addNode (row, col); } } printDLX(); solveDLX (0); } */ /* HOW THE DANCING LINKS ALGORITHM WORKS IN METHOD solveDLX(). The solution algorithm must satisfy every column's constraint if it is to succeed. So it proceeds by taking one column at a time and "covering" it. In this context, "covering" can mean logically hiding the column and so reducing the size of the matrix to be solved, as happens in the method coverColumn() below. But it also means that the constraint represented by that column is "covered" or satisfied, in the sense that a payment of money can be "covered" (i.e. provided for). Whichever column is covered first, one of its non-zero values must be in a row that is part of the solution, always supposing that there is a solution. Knuth recommends to select first the columns that have the smallest number of 1's. The algorithm then tries each column in turn and each non-zero item within that column, backtracking if there are no items left in a column. When all columns have been covered, a solution has been found, but the algorithm continues to search for other solutions until the caller's solution limit is reached. The solutions are delivered via the Qt library's signal-slot mechanism. The algorithm terminates when the first column in the next solution is to be chosen, but one of the columns has no 1's in it, meaning that there can be no further solution. In principle, this can happen right at the start, because the corresponding problem is insoluble, but more likely will be after an extensive search where the solution limit parameter is zero (no limit) or the number of solutions found is less than the required limit or there is no solution, even after an extensive search. The algorithm then returns the integer number of solutions found (possibly 0). The "Dancing Links" aspect of the algorithm refers to lists of nodes that are linked in four directions (left, right, above and below) to represent columns, rows and column headers. Each node represents a 1 in the matrix. Covering a column involves unlinking it from the columns on each side of it and unlinking each row that has a 1 in that column from the rows above and below. One of the nodes in the column is included (tentatively) in the current partial solution and so the other nodes and their rows cannot be. At the same time, the matrix reduces to a sub-matrix and sub-problem. The thing is that the removed columns and rows "remember" their previous state and can easily be re-linked if backtracking becomes necessary and they need to be "uncovered". Thus the nodes, links, columns and rows can "dance" in and out of the matrix as the solution proceeds. Furthermore, the algorithm can be written without using recursion. It just needs to keep a LIFO list (i.e. a stack) of nodes tentatively included in the current solution. Using iteration should make the algorithm go fast. */ int DLXSolver::solveDLX (int solutionLimit) { int solutionCount = 0; int level = 0; DLXNode * currNode = 0; DLXNode * bestCol = 0; QList solution; bool searching = true; bool descending = true; if (mCorner->right == mCorner) { // Empty matrix, nothing to solve. qCDebug(KSudokuLog) << "solveDLX(): EMPTY MATRIX, NOTHING TO SOLVE."; return solutionCount; } while (searching) { // Find the column with the least number of rows yet to be explored. int min = mCorner->right->value; bestCol = mCorner->right; for (DLXNode * p = mCorner->right; p != mCorner; p = p->right) { if (p->value < min) { bestCol = p; min = p->value; } } #ifdef DLX_LOG qCDebug(KSudokuLog) << "solveDLX: BEST COLUMN " << mColumns.indexOf(bestCol) << " level " << level << " rows " << bestCol->value; #endif coverColumn (bestCol); currNode = bestCol->below; solution.append (currNode); #ifdef DLX_LOG fprintf (stderr, "CURRENT SOLUTION: %d rows:", solution.size()); for (DLXNode * q : qAsConst(solution)) { fprintf (stderr, " %d", q->value); } fprintf (stderr, "\n"); #endif while (descending) { if (currNode != bestCol) { // Found a row: cover all other cols of currNode's row (L to R). // Those constraints are satisfied (for now) by this row. DLXNode * p = currNode->right; while (p != currNode) { coverColumn (p->columnHeader); p = p->right; } // printDLX(); if (mCorner->right != mCorner) { break; // Start searching a new sub-matrix. } // All columns covered: a solution has been found. solutionCount++; recordSolution (solutionCount, solution); if (solutionCount == solutionLimit) { return solutionCount; } } else { // No more rows to try in this column. uncoverColumn (bestCol); if (level > 0) { // Backtrack by one level. solution.removeLast(); level--; currNode = solution.at (level); bestCol = currNode->columnHeader; #ifdef DLX_LOG qCDebug(KSudokuLog) << "BACKTRACKED TO LEVEL" << level; #endif } else { // The search is complete. return solutionCount; } } // Uncover all other columns of currNode's row (R to L). // Restores those constraints to unsatisfied state in reverse order. #ifdef DLX_LOG qCDebug(KSudokuLog) << "RESTORE !!!"; #endif DLXNode * p = currNode->left; while (p != currNode) { uncoverColumn (p->columnHeader); p = p->left; } // printDLX(); // Select next row down and continue searching for a solution. currNode = currNode->below; solution [level] = currNode; #ifdef DLX_LOG qCDebug(KSudokuLog) << "SELECT ROW" << currNode->value << "FROM COL" << mColumns.indexOf (currNode->columnHeader); #endif } // End while (descending) level++; } // End while (searching) return solutionCount; // Should never reach this point. } void DLXSolver::coverColumn (DLXNode * colDLX) { #ifdef DLX_LOG fprintf (stderr, "coverColumn: %d rows %d\n", mColumns.indexOf(colDLX), colDLX->value); #endif colDLX->left->right = colDLX->right; colDLX->right->left = colDLX->left; DLXNode * colNode = colDLX->below; while (colNode != colDLX) { DLXNode * rowNode = colNode->right; #ifdef DLX_LOG qCDebug(KSudokuLog) << "DLXSolver::coverColumn: remove DLX row" << rowNode->value; #endif while (rowNode != colNode) { rowNode->below->above = rowNode->above; rowNode->above->below = rowNode->below; rowNode->columnHeader->value--; rowNode = rowNode->right; } colNode = colNode->below; } } void DLXSolver::uncoverColumn (DLXNode * colDLX) { DLXNode * colNode = colDLX->below; while (colNode != colDLX) { DLXNode * rowNode = colNode->right; #ifdef DLX_LOG qCDebug(KSudokuLog) << "DLXSolver::uncoverColumn: return DLX row" << rowNode->value; #endif while (rowNode != colNode) { rowNode->below->above = rowNode; rowNode->above->below = rowNode; rowNode->columnHeader->value++; rowNode = rowNode->right; } colNode = colNode->below; } #ifdef DLX_LOG fprintf (stderr, "uncoverColumn: %d rows %d\n", mColumns.indexOf(colDLX), colDLX->value); #endif colDLX->left->right = colDLX; colDLX->right->left = colDLX; } void DLXSolver::clear() { #ifdef DLX_LOG qCDebug(KSudokuLog) << "============================================================="; qCDebug(KSudokuLog) << "DLXSolver::clear"; #endif // Logically clear the DLX matrix, but leave all previous nodes allocated. // This is to support faster DLX solving on second and subsequent puzzles. mEndNodeNum = -1; mEndRowNum = -1; mEndColNum = -1; initNode (mCorner); } void DLXSolver::addNode (int rowNum, int colNum) { DLXNode * header = mColumns.at (colNum); if (header == 0) { return; // This constraint is excluded (clue or unused). } // Get a node from the pool --- or create one. DLXNode * node = allocNode(); // Circularly link the node onto the end of the row. if (mRows.at (rowNum) == 0) { mRows[rowNum] = node; // First in row. initNode (node); // Linked to itself at left and right. } else { addAtRight (node, mRows.at (rowNum)); } // Circularly link the node onto the end of the column. addBelow (node, header); // Set the node's data-values. node->columnHeader = header; node->value = rowNum; // Increment the count of nodes in the column. header->value++; } DLXNode * DLXSolver::allocNode() { mEndNodeNum++; if (mEndNodeNum >= mNodes.count()) { // Allocate a node only when needed, otherwise re-use one. mNodes.append (new DLXNode); } return mNodes.at (mEndNodeNum); } void DLXSolver::initNode (DLXNode * node) { node->left = node->right = node; node->above = node->below = node; node->columnHeader = node; node->value = 0; } void DLXSolver::addAtRight (DLXNode * node, DLXNode * start) { node->right = start; node->left = start->left; start->left = node; node->left->right = node; } void DLXSolver::addBelow (DLXNode * node, DLXNode * start) { node->below = start; node->above = start->above; start->above = node; node->above->below = node; } void DLXSolver::deleteAll() { #ifdef DLX_LOG qCDebug(KSudokuLog) << "DLXSolver::deleteAll() CALLED"; #endif qDeleteAll (mNodes); // Deallocate the nodes pointed to. mNodes.clear(); mColumns.clear(); // Secondary pointers: no nodes to deallocate. mRows.clear(); } diff --git a/src/generator/mathdokugenerator.cpp b/src/generator/mathdokugenerator.cpp index 578eca6..ee86582 100644 --- a/src/generator/mathdokugenerator.cpp +++ b/src/generator/mathdokugenerator.cpp @@ -1,85 +1,84 @@ /**************************************************************************** * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or * * modify it under the terms of the GNU General Public License as * * published by the Free Software Foundation; either version 2 of * * the License, or (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program. If not, see . * ****************************************************************************/ #include "mathdokugenerator.h" #include "ksudoku_logging.h" #include "skgraph.h" #include "cagegenerator.h" -#include MathdokuGenerator::MathdokuGenerator (SKGraph * graph) : mGraph (graph) { } bool MathdokuGenerator::generateMathdokuTypes (BoardContents & puzzle, BoardContents & solution, QList * solutionMoves, Difficulty difficultyRequired) { // Cage sizes must be no more than the number of cells in a column or row. int maxSize = qMin ((2 + difficultyRequired), mGraph->order()); int maxVal = 1000; bool hideOps = false; // int maxCombos = 120; int maxCombos = 2000; int maxTries = 20; CageGenerator cageGen (solution); int numTries = 0; int numMultis = 0; int n = 0; while ((n <= 0) && (numTries < maxTries)) { numTries++; n = cageGen.makeCages (mGraph, solutionMoves, maxSize, maxVal, hideOps, maxCombos); if (n < 0) { numMultis++; } } if (numTries >= maxTries) { qCDebug(KSudokuLog) << "makeCages() FAILED after" << numTries << "tries" << numMultis << "multi-solutions"; return false; // Try another set of Sudoku cell-values. } qCDebug(KSudokuLog) << "makeCages() required" << numTries << "tries" << numMultis << "multi-solutions";; puzzle = mGraph->emptyBoard(); for (int n = 0; n < mGraph->cageCount(); n++) { if (mGraph->cage(n).count() == 1) { int index = mGraph->cage(n).at(0); puzzle[index] = solution.at(index); } } return true; } int MathdokuGenerator::solveMathdokuTypes (BoardContents & solution, QList * solutionMoves) { bool hideOps = false; int result = 0; CageGenerator cageGen (solution); result = cageGen.checkPuzzle (mGraph, solution, solutionMoves, hideOps); return result; } diff --git a/src/generator/mathdokugenerator.h b/src/generator/mathdokugenerator.h index dbe2e29..f39b73f 100644 --- a/src/generator/mathdokugenerator.h +++ b/src/generator/mathdokugenerator.h @@ -1,75 +1,74 @@ /**************************************************************************** * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or * * modify it under the terms of the GNU General Public License as * * published by the Free Software Foundation; either version 2 of * * the License, or (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program. If not, see . * ****************************************************************************/ #ifndef MATHDOKUGENERATOR_H #define MATHDOKUGENERATOR_H #include "globals.h" -#include class SKGraph; /** * @class MathdokuGenerator * @short Generator for Killer Sudoku and Mathdoku puzzles. * * Generates a Killer Sudoku or Mathdoku puzzle from a Latin Square that * satisfies Sudoku-type constraints. It acts as a controller for makeCages(). */ class MathdokuGenerator { public: explicit MathdokuGenerator (SKGraph * graph); /** * Generate a Mathdoku or Killer Sudoku puzzle. * * @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 * if too many tries were required. */ bool generateMathdokuTypes (BoardContents & puzzle, BoardContents & solution, QList * 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 * solutionMoves); private: SKGraph * mGraph; // The layout, rules and geometry of the puzzle. }; #endif // MATHDOKUGENERATOR_H diff --git a/src/generator/state.h b/src/generator/state.h index 031b2b5..08ff1a6 100644 --- a/src/generator/state.h +++ b/src/generator/state.h @@ -1,53 +1,52 @@ /**************************************************************************** * Copyright 2011 Ian Wadham * * * * This program is free software; you can redistribute it and/or * * modify it under the terms of the GNU General Public License as * * published by the Free Software Foundation; either version 2 of * * the License, or (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program. If not, see . * ****************************************************************************/ #ifndef STATE_H #define STATE_H #include -#include #include "globals.h" #include "sudokuboard.h" class State : public QObject { Q_OBJECT public: State (QObject * parent, const GuessesList & guesses, const int guessNumber, const BoardContents & values, const MoveList & moves, const MoveList & moveTypes); GuessesList guesses() { return m_guesses; } int guessNumber() { return m_guessNumber; } BoardContents values() { return m_values; } void setGuessNumber (int n) { m_guessNumber = n; } MoveList moves() { return m_moves; } MoveList moveTypes() { return m_moveTypes; } private: GuessesList m_guesses; int m_guessNumber; BoardContents m_values; MoveList m_moves; MoveList m_moveTypes; }; #endif // STATE_H diff --git a/src/generator/sudokuboard.cpp b/src/generator/sudokuboard.cpp index bfec2c0..f8ef301 100644 --- a/src/generator/sudokuboard.cpp +++ b/src/generator/sudokuboard.cpp @@ -1,1126 +1,1124 @@ /**************************************************************************** * Copyright 2011 Ian Wadham * * Copyright 2006 David Bau Original algorithms * * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or * * modify it under the terms of the GNU General Public License as * * published by the Free Software Foundation; either version 2 of * * the License, or (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program. If not, see . * ****************************************************************************/ #include "sudokuboard.h" #include "debug.h" #include "ksudoku_logging.h" #include "state.h" #include "mathdokugenerator.h" #include #include #include -#include -#include #include #include #include SudokuBoard::SudokuBoard (SKGraph * graph) : m_type (graph->specificType()), m_order (graph->order()), m_blockSize (graph->base()), m_boardSize (0), m_boardArea (graph->size()), m_overlap (0), m_nGroups (graph->cliqueCount()), m_groupSize (m_order), m_graph (graph), m_vacant (VACANT), m_unusable (UNUSABLE) { m_stats.type = m_type; m_stats.blockSize = m_blockSize; m_stats.order = m_order; m_boardSize = graph->sizeX(); // TODO - IDW. Rationalise grid sizes. qCDebug(KSudokuLog) << "SudokuBoard: type " << m_type << graph->name() << ", block " << m_blockSize << ", order " << m_order << ", BoardArea " << m_boardArea; } void SudokuBoard::setSeed() { static bool started = false; if (started) { qCDebug(KSudokuLog) << "setSeed(): RESET IS TURNED OFF"; // qsrand (m_stats.seed); // IDW test. } else { started = true; m_stats.seed = std::time(nullptr); qsrand (m_stats.seed); qCDebug(KSudokuLog) << "setSeed(): SEED = " << m_stats.seed; } } bool SudokuBoard::generatePuzzle (BoardContents & puzzle, BoardContents & solution, Difficulty difficultyRequired, Symmetry symmetry) { qCDebug(KSudokuLog) << "Entered generatePuzzle(): difficulty " << difficultyRequired << ", symmetry " << symmetry; setSeed(); SudokuType puzzleType = m_graph->specificType(); if ((puzzleType == Mathdoku) || (puzzleType == KillerSudoku)) { // Generate variants of Mathdoku (aka KenKen TM) or Killer Sudoku types. int maxTries = 10; int numTries = 0; bool success = false; while (true) { MathdokuGenerator mg (m_graph); // Find numbers to satisfy Sudoku rules: they will be the solution. solution = fillBoard(); // Generate a Mathdoku or Killer Sudoku puzzle having this solution. numTries++; success = mg.generateMathdokuTypes (puzzle, solution, &m_KSudokuMoves, difficultyRequired); if (success) { return true; } else if (numTries >= maxTries) { QWidget owner; if (KMessageBox::questionYesNo (&owner, i18n("Attempts to generate a puzzle failed after " "about 200 tries. Try again?"), i18n("Mathdoku or Killer Sudoku Puzzle")) == KMessageBox::No) { return false; // Go back to the Welcome screen. } numTries = 0; // Try again. } } } else { // Generate variants of Sudoku (2D) and Roxdoku (3D) types. return generateSudokuRoxdokuTypes (puzzle, solution, difficultyRequired, symmetry); } } bool SudokuBoard::generateSudokuRoxdokuTypes (BoardContents & puzzle, BoardContents & solution, Difficulty difficultyRequired, Symmetry symmetry) { const int maxTries = 20; int count = 0; float bestRating = 0.0; int bestDifficulty = 0; int bestNClues = 0; int bestNGuesses = 0; int bestFirstGuessAt = 0; BoardContents currPuzzle; BoardContents currSolution; QElapsedTimer t; t.start(); if (m_graph->sizeZ() > 1) { symmetry = NONE; // Symmetry not implemented in 3-D. } if (symmetry == RANDOM_SYM) { // Choose a symmetry at random. symmetry = (Symmetry) (qrand() % (int) LAST_CHOICE); } qCDebug(KSudokuLog) << "SYMMETRY IS" << symmetry; if (symmetry == DIAGONAL_1) { // If diagonal symmetry, choose between NW->SE and NE->SW diagonals. symmetry = (qrand() % 2 == 0) ? DIAGONAL_1 : DIAGONAL_2; qCDebug(KSudokuLog) << "Diagonal symmetry, choosing " << ((symmetry == DIAGONAL_1) ? "DIAGONAL_1" : "DIAGONAL_2"); } while (true) { // Fill the board with values that satisfy the Sudoku rules but are // chosen in a random way: these values are the solution of the puzzle. currSolution = this->fillBoard(); qCDebug(KSudokuLog) << "Return from fillBoard() - time to fill board:" << t.elapsed() << " msec"; // Randomly insert solution-values into an empty board until a point is // reached where all the cells in the solution can be logically deduced. currPuzzle = insertValues (currSolution, difficultyRequired, symmetry); qCDebug(KSudokuLog) << "Return from insertValues() - duration:" << t.elapsed() << " msec"; if (difficultyRequired > m_stats.difficulty) { // Make the puzzle harder by removing values at random. currPuzzle = removeValues (currSolution, currPuzzle, difficultyRequired, symmetry); qCDebug(KSudokuLog) << "Return from removeValues() - duration:" << t.elapsed() << " msec"; } Difficulty d = calculateRating (currPuzzle, 5); count++; qCInfo(KSudokuLog) << "CYCLE" << count << ", achieved difficulty" << d << ", required" << difficultyRequired << ", rating" << m_accum.rating; // Use the highest rated puzzle so far. if (m_accum.rating > bestRating) { bestRating = m_accum.rating; bestDifficulty = d; bestNClues = m_stats.nClues; bestNGuesses = m_accum.nGuesses; bestFirstGuessAt = m_stats.firstGuessAt; solution = currSolution; puzzle = currPuzzle; } // Express the rating to 1 decimal place in whatever locale we have. QString ratingStr = ki18n("%1").subs(bestRating, 0, 'f', 1).toString(); // Check and explain the Sudoku/Roxdoku puzzle-generator's results. if ((d < difficultyRequired) && (count >= maxTries)) { // Exit after max attempts? QWidget owner; int ans = KMessageBox::questionYesNo (&owner, i18n("After %1 tries, the best difficulty level achieved by the generator " "is %2, with internal difficulty rating %3, but you " "requested difficulty level %4.\n" "\n" "Do you wish to let the generator try again or accept the puzzle as is?\n" "\n" "Hint: you can try to increase the difficulty rating by doing the following: " "Continue with the 'Accept' button, choose Game -> New, then change the Symmetry setting " "to 'No Symmetry' or some low symmetry type and then use 'Generate A Puzzle' again.", maxTries, bestDifficulty, ratingStr, difficultyRequired), i18n("Difficulty Level"), KGuiItem(i18n("&Try Again")), KGuiItem(i18n("&Accept"))); if (ans == KMessageBox::Yes) { count = 0; // Continue on if the puzzle is not hard enough. continue; } break; // Exit if the puzzle is accepted. } if ((d >= difficultyRequired) || (count >= maxTries)) { QWidget owner; int ans = 0; if (m_accum.nGuesses == 0) { ans = KMessageBox::questionYesNo (&owner, i18n("It will be possible to solve the generated puzzle " "by logic alone. No guessing will be required.\n" "\n" "The internal difficulty rating is %1. There are " "%2 clues at the start and %3 moves to go.", ratingStr, bestNClues, (m_stats.nCells - bestNClues)), i18n("Difficulty Level"), KStandardGuiItem::ok(), KGuiItem(i18n("&Retry"))); } else { QString avGuessStr = ki18n("%1").subs(((float) bestNGuesses) / 5.0, 0, 'f', 1).toString(); // Format as for ratingStr. ans = KMessageBox::questionYesNo (&owner, i18n("Solving the generated puzzle will require an " "average of %1 guesses or branch points and if you " "guess wrong, backtracking will be necessary. The " "first guess should come after %2 moves.\n" "\n" "The internal difficulty rating is %3, there are " "%4 clues at the start and %5 moves to go.", avGuessStr, bestFirstGuessAt, ratingStr, bestNClues, (m_stats.nCells - bestNClues)), i18n("Difficulty Level"), KStandardGuiItem::ok(), KGuiItem(i18n("&Retry"))); } // Exit when the required difficulty or number of tries is reached. if (ans == KMessageBox::No) { count = 0; bestRating = 0.0; bestDifficulty = 0; bestNClues = 0; bestNGuesses = 0; bestFirstGuessAt = 0; continue; // Start again if the user rejects this puzzle. } break; // Exit if the puzzle is OK. } } qCDebug(KSudokuLog) << "FINAL PUZZLE" << puzzle; return true; } Difficulty SudokuBoard::calculateRating (const BoardContents & puzzle, int nSamples) { float avGuesses; float avDeduces; float avDeduced; float fracClues; m_accum.nSingles = m_accum.nSpots = m_accum.nGuesses = m_accum.nDeduces = 0; m_accum.rating = 0.0; BoardContents solution; clear (solution); setSeed(); for (int n = 0; n < nSamples; n++) { dbo1 "SOLVE PUZZLE %d\n", n); solution = solveBoard (puzzle, nSamples == 1 ? NotRandom : Random); dbo1 "PUZZLE SOLVED %d\n", n); analyseMoves (m_stats); fracClues = float (m_stats.nClues) / float (m_stats.nCells); m_accum.nSingles += m_stats.nSingles; m_accum.nSpots += m_stats.nSpots; m_accum.nGuesses += m_stats.nGuesses; m_accum.nDeduces += m_stats.nDeduces; m_accum.rating += m_stats.rating; avDeduced = float(m_stats.nSingles + m_stats.nSpots) / m_stats.nDeduces; dbo2 " Type %2d %2d: clues %3d %3d %2.1f%% %3d moves %3dP %3dS %3dG " "%3dM %3dD %3.1fR\n", m_stats.type, m_stats.order, m_stats.nClues, m_stats.nCells, fracClues * 100.0, (m_stats.nCells - m_stats.nClues), m_stats.nSingles, m_stats.nSpots, m_stats.nGuesses, (m_stats.nSingles + m_stats.nSpots + m_stats.nGuesses), m_stats.nDeduces, m_stats.rating); } avGuesses = float (m_accum.nGuesses) / nSamples; avDeduces = float (m_accum.nDeduces) / nSamples; avDeduced = float (m_accum.nSingles + m_accum.nSpots) / m_accum.nDeduces; m_accum.rating = m_accum.rating / nSamples; m_accum.difficulty = calculateDifficulty (m_accum.rating); dbo1 " Av guesses %2.1f Av deduces %2.1f" " Av per deduce %3.1f rating %2.1f difficulty %d\n", avGuesses, avDeduces, avDeduced, m_accum.rating, m_accum.difficulty); return m_accum.difficulty; } int SudokuBoard::checkPuzzle (const BoardContents & puzzle, const BoardContents & solution) { BoardContents answer = solveBoard (puzzle); if (answer.isEmpty()) { dbo1 "checkPuzzle: There is NO SOLUTION.\n"); return -1; // There is no solution. } if ((! solution.isEmpty()) && (answer != solution)) { dbo1 "checkPuzzle: The SOLUTION DIFFERS from the one supplied.\n"); return -2; // The solution differs from the one supplied. } analyseMoves (m_stats); answer.clear(); answer = tryGuesses (Random); if (! answer.isEmpty()) { dbo1 "checkPuzzle: There is MORE THAN ONE SOLUTION.\n"); return -3; // There is more than one solution. } return calculateDifficulty (m_stats.rating); } void SudokuBoard::getMoveList (QList & moveList) { moveList = m_KSudokuMoves; } BoardContents & SudokuBoard::solveBoard (const BoardContents & boardValues, GuessingMode gMode) { qCInfo(KSudokuLog) << "solveBoard()" << boardValues; m_currentValues = boardValues; return solve (gMode); } BoardContents & SudokuBoard::solve (GuessingMode gMode = Random) { // Eliminate any previous solver work. qDeleteAll (m_states); m_states.clear(); m_moves.clear(); m_moveTypes.clear(); int nClues = 0; int nCells = 0; int value = 0; for (int n = 0; n < m_boardArea; n++) { value = m_currentValues.at(n); if (value != m_unusable) { nCells++; if (value != m_vacant) { nClues++; } } } m_stats.nClues = nClues; m_stats.nCells = nCells; dbo1 "STATS: CLUES %d, CELLS %d, PERCENT %.1f\n", nClues, nCells, nClues * 100.0 / float (nCells)); // Attempt to deduce the solution in one hit. GuessesList g = deduceValues (m_currentValues, gMode); if (g.isEmpty()) { // The entire solution can be deduced by applying the Sudoku rules. dbo1 "NO GUESSES NEEDED, the solution can be entirely deduced.\n"); return m_currentValues; } // We need to use a mix of guessing, deducing and backtracking. m_states.push (new State (this, g, 0, m_currentValues, m_moves, m_moveTypes)); return tryGuesses (gMode); } BoardContents & SudokuBoard::tryGuesses (GuessingMode gMode = Random) { while (m_states.count() > 0) { GuessesList guesses = m_states.top()->guesses(); int n = m_states.top()->guessNumber(); if ((n >= guesses.count()) || (guesses.at (0) == -1)) { dbo2 "POP: Out of guesses at level %d\n", m_states.count()); delete m_states.pop(); if (!m_states.isEmpty()) { m_moves.clear(); m_moveTypes.clear(); m_moves = m_states.top()->moves(); m_moveTypes = m_states.top()->moveTypes(); } continue; } m_states.top()->setGuessNumber (n + 1); m_currentValues = m_states.top()->values(); m_moves.append (guesses.at(n)); m_moveTypes.append (Guess); m_currentValues [pairPos (guesses.at(n))] = pairVal (guesses.at(n)); dbo2 "\nNEXT GUESS: level %d, guess number %d\n", m_states.count(), n); dbo2 " Pick %d %d row %d col %d\n", pairVal (guesses.at(n)), pairPos (guesses.at(n)), pairPos (guesses.at(n))/m_boardSize + 1, pairPos (guesses.at(n))%m_boardSize + 1); guesses = deduceValues (m_currentValues, gMode); if (guesses.isEmpty()) { // NOTE: We keep the stack of states. It is needed by checkPuzzle() // for the multiple-solutions test and deleted when its parent // SudokuBoard object (i.e. this->) is deleted. return m_currentValues; } m_states.push (new State (this, guesses, 0, m_currentValues, m_moves, m_moveTypes)); } // No solution. m_currentValues.clear(); return m_currentValues; } BoardContents SudokuBoard::insertValues (const BoardContents & solution, const Difficulty required, const Symmetry symmetry) { BoardContents puzzle; BoardContents filled; QVector sequence (m_boardArea); int cell = 0; int value = 0; // Set up empty board areas. clear (puzzle); clear (filled); // Add cells in random order, but skip cells that can be deduced from them. dbo1 "Start INSERTING: %d solution values\n", solution.count()); randomSequence (sequence); int index = 0; for (int n = 0; n < m_boardArea; n++) { cell = sequence.at (n); value = filled.at (cell); if (filled.at (cell) == 0) { index = n; changeClues (puzzle, cell, symmetry, solution); changeClues (filled, cell, symmetry, solution); deduceValues (filled, Random /* NotRandom */); qCDebug(KSudokuLog) << "Puzzle:" << puzzle << "; filled" << filled; } } qCDebug(KSudokuLog) << "Puzzle:" << puzzle; while (true) { // Check the difficulty of the puzzle. solveBoard (puzzle); analyseMoves (m_stats); m_stats.difficulty = calculateDifficulty (m_stats.rating); if (m_stats.difficulty <= required) { break; // The difficulty is as required or not enough yet. } // The puzzle needs to be made easier. Add randomly-selected clues. for (int n = index; n < m_boardArea; n++) { cell = sequence.at (n); if (puzzle.at (cell) == 0) { changeClues (puzzle, cell, symmetry, solution); index = n; break; } } dbo1 "At index %d, added value %d, cell %d, row %d, col %d\n", index, solution.at (cell), cell, cell/m_boardSize + 1, cell%m_boardSize + 1); } qCDebug(KSudokuLog) << "Puzzle:" << puzzle; return puzzle; } BoardContents SudokuBoard::removeValues (const BoardContents & solution, BoardContents & puzzle, const Difficulty required, const Symmetry symmetry) { // Make the puzzle harder by removing values at random, making sure at each // step that the puzzle has a solution, the correct solution and only one // solution. Stop when these conditions can no longer be met and the // required difficulty is reached or failed to be reached with the current // (random) selection of board values. // Remove values in random order, but put them back if the solution fails. BoardContents vacant; QVector sequence (m_boardArea); int cell = 0; int value = 0; QList tailOfRemoved; // No guesses until this much of the puzzle, including clues, is filled in. float guessLimit = 0.6; int noGuesses = (int) (guessLimit * m_stats.nCells + 0.5); dbo1 "Guess limit = %.2f, nCells = %d, nClues = %d, noGuesses = %d\n", guessLimit, m_stats.nCells, m_stats.nClues, noGuesses); dbo1 "Start REMOVING:\n"); randomSequence (sequence); clear (vacant); for (int n = 0; n < m_boardArea; n++) { cell = sequence.at (n); value = puzzle.at (cell); if ((value == 0) || (value == m_unusable)) { continue; // Skip empty or unusable cells. } // Try removing this clue and its symmetry partners (if any). changeClues (puzzle, cell, symmetry, vacant); dbo1 "ITERATION %d: Removed %d from cell %d\n", n, value, cell); // Check the solution is still OK and calculate the difficulty roughly. int result = checkPuzzle (puzzle, solution); // Do not force the human solver to start guessing too soon. if ((result >= 0) && (required != Unlimited) && (m_stats.firstGuessAt <= (noGuesses - m_stats.nClues))) { dbo1 "removeValues: FIRST GUESS is too soon: move %d of %d.\n", m_stats.firstGuessAt, m_stats.nCells - m_stats.nClues); result = -4; } // If the solution is not OK, replace the removed value(s). if (result < 0) { dbo1 "ITERATION %d: Replaced %d at cell %d, check returned %d\n", n, value, cell, result); changeClues (puzzle, cell, symmetry, solution); } // If the solution is OK, check the difficulty (roughly). else { m_stats.difficulty = (Difficulty) result; dbo1 "CURRENT DIFFICULTY %d\n", m_stats.difficulty); if (m_stats.difficulty == required) { // Save removed positions while the difficulty is as required. tailOfRemoved.append (cell); dbo1 "OVERSHOOT %d at sequence %d\n", tailOfRemoved.count(), n); } else if (m_stats.difficulty > required) { // Finish if the required difficulty is exceeded. qCInfo(KSudokuLog) << "Break on difficulty - replaced" << value << "at cell" << cell << ", overshoot is" << tailOfRemoved.count(); // Replace the value involved. changeClues (puzzle, cell, symmetry, solution); break; } } } // If the required difficulty was reached and was not Unlimited, replace // half the saved values. // // This should avoid chance fluctuations in the calculated difficulty (when // the solution involves guessing) and provide a puzzle that is within the // required difficulty range. if ((required != Unlimited) && (tailOfRemoved.count() > 1)) { for (int k = 0; k < tailOfRemoved.count() / 2; k++) { cell = tailOfRemoved.takeLast(); dbo1 "Replaced clue(s) for cell %d\n", cell); changeClues (puzzle, cell, symmetry, solution); } } return puzzle; } void SudokuBoard::analyseMoves (Statistics & s) { dbo1 "\nanalyseMoves()\n"); s.nCells = m_stats.nCells; s.nClues = m_stats.nClues; s.firstGuessAt = s.nCells - s.nClues + 1; s.nSingles = s.nSpots = s.nDeduces = s.nGuesses = 0; m_KSudokuMoves.clear(); Move m; Move mType; while (! m_moves.isEmpty()) { m = m_moves.takeFirst(); mType = m_moveTypes.takeFirst(); int val = pairVal(m); int pos = pairPos(m); int row = m_graph->cellPosY (pos); int col = m_graph->cellPosX (pos); switch (mType) { case Single: dbo2 " Single Pick %d %d row %d col %d\n", val, pos, row+1, col+1); m_KSudokuMoves.append (pos); s.nSingles++; break; case Spot: dbo2 " Single Spot %d %d row %d col %d\n", val, pos, row+1, col+1); m_KSudokuMoves.append (pos); s.nSpots++; break; case Deduce: dbo2 "Deduce: Iteration %d\n", m); s.nDeduces++; break; case Guess: dbo2 "GUESS: %d %d row %d col %d\n", val, pos, row+1, col+1); m_KSudokuMoves.append (pos); if (s.nGuesses < 1) { s.firstGuessAt = s.nSingles + s.nSpots + 1; } s.nGuesses++; break; case Wrong: dbo2 "WRONG GUESS: %d %d row %d col %d\n", val, pos, row+1, col+1); break; case Result: break; } } // Calculate the empirical formula for the difficulty rating. Note that // guess-points are effectively weighted by 3, because the deducer must // always iterate one more time to establish that a guess is needed. s.rating = 2 * s.nGuesses + s.nDeduces - (float(s.nClues)/s.nCells); // Calculate the difficulty level for empirical ranges of the rating. s.difficulty = calculateDifficulty (s.rating); dbo1 " aM: Type %2d %2d: clues %3d %3d %2.1f%% %3dP %3dS %3dG " "%3dM %3dD %3.1fR D=%d F=%d\n\n", m_stats.type, m_stats.order, s.nClues, s.nCells, ((float) s.nClues / s.nCells) * 100.0, s.nSingles, s.nSpots, s.nGuesses, (s.nSingles + s.nSpots + s.nGuesses), s.nDeduces, s.rating, s.difficulty, s.firstGuessAt); } Difficulty SudokuBoard::calculateDifficulty (float rating) { // These ranges of the rating were arrived at empirically by solving a few // dozen published puzzles and comparing SudokuBoard's rating value with the // description of difficulty given by the publisher, e.g. Diabolical or Evil // puzzles gave ratings in the range 10.0 to 20.0, so became Diabolical. Difficulty d = Unlimited; if (rating < 1.7) { d = VeryEasy; } else if (rating < 2.7) { d = Easy; } else if (rating < 4.6) { d = Medium; } else if (rating < 10.0) { d = Hard; } else if (rating < 20.0) { d = Diabolical; } return d; } void SudokuBoard::print (const BoardContents & boardValues) { // Used for test and debug, but the format is also parsable and loadable. char nLabels[] = "123456789"; char aLabels[] = "abcdefghijklmnopqrstuvwxy"; int index, value; if (boardValues.size() != m_boardArea) { printf ("Error: %d board values to be printed, %d values required.\n\n", boardValues.size(), m_boardArea); return; } int depth = m_graph->sizeZ(); // If 2-D, depth == 1, else depth > 1. for (int k = 0; k < depth; k++) { int z = (depth > 1) ? (depth - k - 1) : k; for (int j = 0; j < m_graph->sizeY(); j++) { if ((j != 0) && (j % m_blockSize == 0)) { printf ("\n"); // Gap between square blocks. } int y = (depth > 1) ? (m_graph->sizeY() - j - 1) : j; for (int x = 0; x < m_graph->sizeX(); x++) { index = m_graph->cellIndex (x, y, z); value = boardValues.at (index); if (x % m_blockSize == 0) { printf (" "); // Gap between square blocks. } if (value == m_unusable) { printf (" '"); // Unused cell (e.g. in Samurai). } else if (value == 0) { printf (" -"); // Empty cell (to be solved). } else { value--; char label = (m_order > 9) ? aLabels[value] : nLabels[value]; printf (" %c", label); // Given cell (or clue). } } printf ("\n"); // End of row. } printf ("\n"); // Next Z or end of 2D puzzle/solution. } } GuessesList SudokuBoard::deduceValues (BoardContents & boardValues, GuessingMode gMode = Random) { int iteration = 0; setUpValueRequirements (boardValues); while (true) { iteration++; m_moves.append (iteration); m_moveTypes.append (Deduce); dbo2 "DEDUCE: Iteration %d\n", iteration); bool stuck = true; int count = 0; GuessesList guesses; for (int cell = 0; cell < m_boardArea; cell++) { if (boardValues.at (cell) == m_vacant) { GuessesList newGuesses; qint32 numbers = m_validCellValues.at (cell); dbo3 "Cell %d, valid numbers %03o\n", cell, numbers); if (numbers == 0) { dbo2 "SOLUTION FAILED: RETURN at cell %d\n", cell); return solutionFailed (guesses); } int validNumber = 1; while (numbers != 0) { dbo3 "Numbers = %03o, validNumber = %d\n", numbers, validNumber); if (numbers & 1) { newGuesses.append (setPair (cell, validNumber)); } numbers = numbers >> 1; validNumber++; } if (newGuesses.count() == 1) { m_moves.append (newGuesses.first()); m_moveTypes.append (Single); boardValues [cell] = pairVal (newGuesses.takeFirst()); dbo3 " Single Pick %d %d row %d col %d\n", boardValues.at (cell), cell, cell/m_boardSize + 1, cell%m_boardSize + 1); updateValueRequirements (boardValues, cell); stuck = false; } else if (stuck) { // Select a list of guesses. if (guesses.isEmpty() || (newGuesses.count() < guesses.count())) { guesses = newGuesses; count = 1; } else if (newGuesses.count() > guesses.count()) { ; } else if (gMode == Random) { if ((qrand() % count) == 0) { guesses = newGuesses; } count++; } } } // End if } // Next cell for (int group = 0; group < m_nGroups; group++) { QVector cellList = m_graph->clique (group); qint32 numbers = m_requiredGroupValues.at (group); dbo3 "Group %d, valid numbers %03o\n", group, numbers); if (numbers == 0) { continue; } int validNumber = 1; qint32 bit = 1; int cell = 0; while (numbers != 0) { if (numbers & 1) { GuessesList newGuesses; int index = group * m_groupSize; for (int n = 0; n < m_groupSize; n++) { cell = cellList.at (n); if ((m_validCellValues.at (cell) & bit) != 0) { newGuesses.append (setPair (cell, validNumber)); } index++; } if (newGuesses.isEmpty()) { dbo2 "SOLUTION FAILED: RETURN at group %d\n", group); return solutionFailed (guesses); } else if (newGuesses.count() == 1) { m_moves.append (newGuesses.first()); m_moveTypes.append (Spot); cell = pairPos (newGuesses.takeFirst()); boardValues [cell] = validNumber; dbo3 " Single Spot in Group %d value %d %d " "row %d col %d\n", group, validNumber, cell, cell/m_boardSize + 1, cell%m_boardSize + 1); updateValueRequirements (boardValues, cell); stuck = false; } else if (stuck) { // Select a list of guesses. if (guesses.isEmpty() || (newGuesses.count() < guesses.count())) { guesses = newGuesses; count = 1; } else if (newGuesses.count() > guesses.count()) { ; } else if (gMode == Random){ if ((qrand() % count) == 0) { guesses = newGuesses; } count++; } } } // End if (numbers & 1) numbers = numbers >> 1; bit = bit << 1; validNumber++; } // Next number } // Next group if (stuck) { GuessesList original = guesses; if (gMode == Random) { // Shuffle the guesses. QVector sequence (guesses.count()); randomSequence (sequence); guesses.clear(); for (int i = 0; i < original.count(); i++) { guesses.append (original.at (sequence.at (i))); } } dbo2 "Guess "); for (int i = 0; i < original.count(); i++) { dbo3 "%d,%d ", pairPos (original.at(i)), pairVal (original.at(i))); } dbo2 "\n"); dbo2 "Shuffled "); for (int i = 0; i < guesses.count(); i++) { dbo3 "%d,%d ", pairPos (guesses.at (i)), pairVal (guesses.at(i))); } dbo2 "\n"); return guesses; } } // End while (true) } GuessesList SudokuBoard::solutionFailed (GuessesList & guesses) { guesses.clear(); guesses.append (-1); return guesses; } void SudokuBoard::clear (BoardContents & boardValues) { boardValues = m_graph->emptyBoard(); // Set cells vacant or unusable. } BoardContents & SudokuBoard::fillBoard() { // Solve the empty board, thus filling it with values at random. These // values can be the starting point for generating a puzzle and also the // final solution of that puzzle. clear (m_currentValues); // Fill a central block with values 1 to m_order in random sequence. This // reduces the solveBoard() time considerably, esp. if blockSize is 4 or 5. QVector sequence (m_order); QVector cellList = m_graph->clique (m_nGroups / 2); randomSequence (sequence); for (int n = 0; n < m_order; n++) { m_currentValues [cellList.at (n)] = sequence.at (n) + 1; } solveBoard (m_currentValues); dbo1 "BOARD FILLED\n"); return m_currentValues; } void SudokuBoard::randomSequence (QVector & sequence) { if (sequence.isEmpty()) return; // Fill the vector with consecutive integers. int size = sequence.size(); for (int i = 0; i < size; i++) { sequence [i] = i; } if (size == 1) return; // Shuffle the integers. int last = size; int z = 0; int temp = 0; for (int i = 0; i < size; i++) { z = qrand() % last; last--; temp = sequence.at (z); sequence [z] = sequence.at (last); sequence [last] = temp; } } void SudokuBoard::setUpValueRequirements (BoardContents & boardValues) { // Set a 1-bit for each possible cell-value in this order of Sudoku, for // example 9 bits for a 9x9 grid with 3x3 blocks. qint32 allValues = (1 << m_order) - 1; dbo2 "Enter setUpValueRequirements()\n"); if (dbgLevel >= 2) { this->print (boardValues); } // Set bit-patterns to show what values each row, col or block needs. // The starting pattern is allValues, but bits are set to zero as the // corresponding values are supplied during puzzle generation and solving. m_requiredGroupValues.fill (0, m_nGroups); int index = 0; qint32 bitPattern = 0; for (int group = 0; group < m_nGroups; group++) { dbo3 "Group %3d ", group); QVector cellList = m_graph->clique (group); bitPattern = 0; for (int n = 0; n < m_groupSize; n++) { int value = boardValues.at (cellList.at (n)) - 1; if (value != m_unusable) { bitPattern |= (1 << value); // Add bit for each value found. } dbo3 "%3d=%2d ", cellList.at (n), value + 1); index++; } // Reverse all the bits, giving values currently not found in the group. m_requiredGroupValues [group] = bitPattern ^ allValues; dbo3 "bits %03o\n", m_requiredGroupValues.at (group)); } // Set bit-patterns to show that each cell can accept any value. Bits are // set to zero as possibilities for each cell are eliminated when solving. m_validCellValues.fill (allValues, m_boardArea); for (int i = 0; i < m_boardArea; i++) { if (boardValues.at (i) == m_unusable) { // No values are allowed in unusable cells (e.g. in Samurai type). m_validCellValues [i] = 0; } if (boardValues.at (i) != m_vacant) { // Cell is already filled in. m_validCellValues [i] = 0; } } // Now, for each cell, retain bits for values that are required by every // group to which that cell belongs. For example, if the row already has 1, // 2, 3, the column has 3, 4, 5, 6 and the block has 6, 9, then the cell // can only have 7 or 8, with bit value 192. index = 0; for (int group = 0; group < m_nGroups; group++) { QVector cellList = m_graph->clique (group); for (int n = 0; n < m_order; n++) { int cell = cellList.at (n); m_validCellValues [cell] &= m_requiredGroupValues.at (group); index++; } } dbo2 "Finished setUpValueRequirements()\n"); dbo3 "allowed:\n"); for (int i = 0; i < m_boardArea; i++) { dbo3 "'%03o', ", m_validCellValues.at (i)); if ((i + 1) % m_boardSize == 0) dbo3 "\n"); } dbo3 "needed:\n"); for (int group = 0; group < m_nGroups; group++) { dbo3 "'%03o', ", m_requiredGroupValues.at (group)); if ((group + 1) % m_order == 0) dbo3 "\n"); } dbo3 "\n"); } void SudokuBoard::updateValueRequirements (BoardContents & boardValues, int cell) { // Set a 1-bit for each possible cell-value in this order of Sudoku. qint32 allValues = (1 << m_order) - 1; // Set a complement-mask for this cell's new value. qint32 bitPattern = (1 << (boardValues.at (cell) - 1)) ^ allValues; // Show that this cell no longer requires values: it has been filled. m_validCellValues [cell] = 0; // Update the requirements for each group to which this cell belongs. const QList groupList = m_graph->cliqueList(cell); for (int group : groupList) { m_requiredGroupValues [group] &= bitPattern; QVector cellList = m_graph->clique (group); for (int n = 0; n < m_order; n++) { int cell = cellList.at (n); m_validCellValues [cell] &= bitPattern; } } } void SudokuBoard::changeClues (BoardContents & to, int cell, Symmetry type, const BoardContents & from) { int nSymm = 1; int indices[8]; nSymm = getSymmetricIndices (m_boardSize, type, cell, indices); for (int k = 0; k < nSymm; k++) { cell = indices [k]; to [cell] = from.at (cell); } } int SudokuBoard::getSymmetricIndices (int size, Symmetry type, int index, int * out) { int result = 1; out[0] = index; if (type == NONE) { return result; } int row = m_graph->cellPosY (index); int col = m_graph->cellPosX (index); int lr = size - col - 1; // For left-to-right reflection. int tb = size - row - 1; // For top-to-bottom reflection. switch (type) { case DIAGONAL_1: // Reflect a copy of the point around two central axes making its // reflection in the NW-SE diagonal the same as for NE-SW diagonal. row = tb; col = lr; // No break; fall through to case DIAGONAL_2. case DIAGONAL_2: // Reflect (col, row) in the main NW-SE diagonal by swapping coords. out[1] = m_graph->cellIndex(row, col); result = (out[1] == out[0]) ? 1 : 2; break; case CENTRAL: out[1] = (size * size) - index - 1; result = (out[1] == out[0]) ? 1 : 2; break; case SPIRAL: if ((size % 2 != 1) || (row != col) || (col != (size - 1)/2)) { result = 4; // This is not the central cell. out[1] = m_graph->cellIndex(lr, tb); out[2] = m_graph->cellIndex(row, lr); out[3] = m_graph->cellIndex(tb, col); } break; case FOURWAY: out[1] = m_graph->cellIndex(row, col); // Interchange X and Y. out[2] = m_graph->cellIndex(lr, row); // Left-to-right. out[3] = m_graph->cellIndex(row, lr); // Interchange X and Y. out[4] = m_graph->cellIndex(col, tb); // Top-to-bottom. out[5] = m_graph->cellIndex(tb, col); // Interchange X and Y. out[6] = m_graph->cellIndex(lr, tb); // Both L-R and T-B. out[7] = m_graph->cellIndex(tb, lr); // Interchange X and Y. int k; for (int n = 1; n < 8; n++) { for (k = 0; k < result; k++) { if (out[n] == out[k]) { break; // Omit duplicates. } } if (k >= result) { out[result] = out[n]; result++; // Use unique positions. } } break; case LEFT_RIGHT: out[1] = m_graph->cellIndex(lr, row); result = (out[1] == out[0]) ? 1 : 2; break; default: break; } return result; } diff --git a/src/gui/config.cpp b/src/gui/config.cpp index 9efa1c4..2cb9c2b 100644 --- a/src/gui/config.cpp +++ b/src/gui/config.cpp @@ -1,38 +1,35 @@ /*************************************************************************** * Copyright 2007 Johannes Bergmeier * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "config.h" -#include -#include -#include #include "symbols.h" namespace ksudoku { GameConfig::GameConfig(QWidget* parent) : QWidget(parent) { setupUi(this); } } diff --git a/src/gui/config.h b/src/gui/config.h index b942f4a..2c2fce0 100644 --- a/src/gui/config.h +++ b/src/gui/config.h @@ -1,41 +1,40 @@ /*************************************************************************** * Copyright 2007 Johannes Bergmeier * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #ifndef _KSUDOKUCONFIG_H_ #define _KSUDOKUCONFIG_H_ #include -#include #include #include "ui_configgame.h" namespace ksudoku { struct SymbolTable; class GameConfig : public QWidget, private Ui::ConfigGame { Q_OBJECT public: explicit GameConfig(QWidget* parent = 0); }; } #endif diff --git a/src/gui/gamevariants.cpp b/src/gui/gamevariants.cpp index 7bab077..de529b2 100644 --- a/src/gui/gamevariants.cpp +++ b/src/gui/gamevariants.cpp @@ -1,441 +1,440 @@ /*************************************************************************** * Copyright 2007 Johannes Bergmeier * * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "gamevariants.h" #include "ksudoku_logging.h" #include "ksudokugame.h" #include "serializer.h" -#include #include #include #include #include #include #include "puzzle.h" namespace ksudoku { /////////////////////////////////////////////////////////////////////////////// // class GameVariant /////////////////////////////////////////////////////////////////////////////// GameVariant::GameVariant(const QString& name, GameVariantCollection* collection) : m_name(name) { if(collection) collection->addVariant(this); } void GameVariant::setDescription(const QString& descr) { m_description = descr; } void GameVariant::setIcon(const QString& icon) { m_icon = icon; } /////////////////////////////////////////////////////////////////////////////// // class GameVariantCollection /////////////////////////////////////////////////////////////////////////////// GameVariantCollection::GameVariantCollection(QObject* parent, bool autoDel) : QAbstractListModel(parent), m_autoDelete(autoDel) { } GameVariantCollection::~GameVariantCollection() { if(m_autoDelete) qDeleteAll(m_variants); m_variants.clear(); } void GameVariantCollection::addVariant(GameVariant* variant) { int count = m_variants.count(); beginInsertRows(QModelIndex(), count, count); m_variants.append(variant); endInsertRows(); emit newVariant(variant); } int GameVariantCollection::rowCount(const QModelIndex& parent) const { Q_UNUSED(parent); return m_variants.count(); } QModelIndex GameVariantCollection::index(int row, int column, const QModelIndex &parent) const { Q_UNUSED(parent); if ((row < 0) || (row >= m_variants.count())) return QModelIndex(); return createIndex(row, column, m_variants[row]); } QVariant GameVariantCollection::data(const QModelIndex &index, int role) const { if (!index.isValid() || index.row() >= m_variants.count()) return QVariant(); if (!index.internalPointer()) return QVariant(); GameVariant* gameVariant = static_cast(index.internalPointer()); switch(role) { case Qt::DisplayRole: return gameVariant->name(); case Qt::DecorationRole: return gameVariant->icon(); case GameVariantDelegate::Description: return gameVariant->description(); } return QVariant(); } GameVariant* GameVariantCollection::variant(const QModelIndex& index) const { return static_cast(index.internalPointer()); } /////////////////////////////////////////////////////////////////////////////// // class GameVariantDelegate ////////////77///////////////////////////////////////////////////////////////// GameVariantDelegate::GameVariantDelegate(QObject* parent, QWidget * viewport) : QItemDelegate(parent), m_viewport(viewport) { } QSize GameVariantDelegate::sizeHint(const QStyleOptionViewItem& option, const QModelIndex& index) const { Q_UNUSED(index); // Fit a varying number of columns into the list-view. int viewportWidth = m_viewport->width(); int hintWidth = m_minWidth; int nItemsPerRow = viewportWidth / m_minWidth; // Expand the hinted width, so that the columns will fill the viewport. if (nItemsPerRow > 0) { int adjustment = (viewportWidth % nItemsPerRow) ? 0 : 1; // The adjustment works around a graphics glitch, when nItemsPerRow // exactly divides viewportWidth and instead of nItemsPerRow columns // we suddenly get one column less, plus a large empty space, even // though QListView::spacing() is zero. hintWidth = (viewportWidth - adjustment) / nItemsPerRow; } // Set the height to contain the icon or 4 lines of text. QSize size (hintWidth, 0); int fontHeight = option.fontMetrics.height(); if (m_iconHeight < fontHeight*4) { size.setHeight (fontHeight*4 + m_separatorPixels*3); } else { size.setHeight (m_iconHeight + m_separatorPixels*2); } return size; } void GameVariantDelegate::paint(QPainter* painter, const QStyleOptionViewItem& option, const QModelIndex& index) const { QColor bkgColor; // Calculate item's column num in list-view. Add 1 in odd-numbered rows. int nItemsPerRow = qMax (m_viewport->width() / option.rect.width(), 1); int oddColumn = index.row() % nItemsPerRow; oddColumn = oddColumn + ((index.row() / nItemsPerRow) % 2); if (option.state & QStyle::State_Selected) { bkgColor = option.palette.color(QPalette::Highlight); } else if (oddColumn % 2) { // The shading alternates along each row in the list view and // each odd-numbered row starts with a shaded item, so we have // a checkerboard pattern, regardless of whether nItemsPerRow // is odd or even (see the above calculation). bkgColor = option.palette.color(QPalette::AlternateBase); } else { bkgColor = option.palette.color(QPalette::Base); } painter->fillRect(option.rect, bkgColor); QRect contentRect = option.rect.adjusted(m_leftMargin, m_separatorPixels, -m_rightMargin, -m_separatorPixels); // Show icon QPixmap iconPixmap = QIcon::fromTheme(icon(index)).pixmap(m_iconWidth, m_iconHeight); painter->drawPixmap(contentRect.left(), (contentRect.height() - iconPixmap.height()) / 2 + contentRect.top(), iconPixmap); contentRect.adjust(iconPixmap.width() + m_separatorPixels*2, 0, 0, 0); // // Show configuration icon // if(configurable(index)) { // QPixmap configPixmap = QIcon::fromTheme( QLatin1String( "configure" ) ).pixmap(32, 32); // painter->drawPixmap(contentRect.right() - configPixmap.width(), (contentRect.height() - configPixmap.height()) / 2 + contentRect.top(), configPixmap); // contentRect.adjust(0, 0, -(configPixmap.width() + separatorPixels), 0); // } // Show Title QFont titleFont(painter->font()); titleFont.setPointSize(titleFont.pointSize() + 2); titleFont.setWeight(QFont::Bold); QPen previousPen(painter->pen()); // TODO: don't we have a function for 'color1 similar color2' if(previousPen.color() == bkgColor) { QPen p(previousPen); int color = bkgColor.rgb(); color = ~color | 0xff000000; p.setColor(color); painter->setPen(p); } QFont previousFont(painter->font()); painter->setFont(titleFont); QString titleStr = painter->fontMetrics().elidedText(title(index), Qt::ElideRight, contentRect.width()); painter->drawText(contentRect, titleStr); contentRect.adjust(0, m_separatorPixels + painter->fontMetrics().height(), 0, 0); painter->setFont(previousFont); // Show Description QTextOption wrap(Qt::AlignLeft); wrap.setWrapMode(QTextOption::WordWrap); QString descrStr = description(index); painter->drawText(contentRect, descrStr, wrap); painter->setPen(previousPen); } QString GameVariantDelegate::title(const QModelIndex& index) const { return index.model()->data(index, Qt::DisplayRole).toString(); } QString GameVariantDelegate::description(const QModelIndex& index) const { return index.model()->data(index, Description).toString(); } QString GameVariantDelegate::icon(const QModelIndex& index) const { return index.model()->data(index, Qt::DecorationRole).toString(); } bool GameVariantDelegate::configurable(const QModelIndex& index) const { const GameVariantCollection* collection = dynamic_cast(index.model()); if(!collection) return false; return collection->variant(index)->canConfigure(); } bool GameVariantDelegate::eventFilter(QObject* watched, QEvent* event) { if(event->type() == QEvent::MouseButtonPress) { return true; } // TODO insert code for handling clicks on buttons in items. return QItemDelegate::eventFilter(watched, event); } /////////////////////////////////////////////////////////////////////////////// // class SudokuGame /////////////////////////////////////////////////////////////////////////////// SudokuGame::SudokuGame(const QString& name, uint order, GameVariantCollection* collection) : GameVariant(name, collection), m_order(order), m_graph(nullptr) { // TODO load from settings m_symmetry = 0; } SudokuGame::~SudokuGame() { delete m_graph; } bool SudokuGame::canConfigure() const { return true; } bool SudokuGame::configure() { KMessageBox::information(nullptr, i18n("Configuration not yet implemented"), QLatin1String("")); return false; } bool SudokuGame::canStartEmpty() const { return true; } Game SudokuGame::startEmpty() { if(!m_graph) { m_graph = new SKGraph(m_order, TypeSudoku); m_graph->initSudoku(); } Puzzle* puzzle = new Puzzle(m_graph, false); puzzle->init(); return Game(puzzle); } Game SudokuGame::createGame(int difficulty, int symmetry) { if(!m_graph) { m_graph = new SKGraph(m_order, TypeSudoku); m_graph->initSudoku(); } Puzzle* puzzle = new Puzzle(m_graph, true); puzzle->init(difficulty, symmetry); return Game(puzzle); } KsView* SudokuGame::createView(const Game& /*game*/) const { qCDebug(KSudokuLog) << "KsView* ksudoku::SudokuGame::createView()"; return nullptr; } /////////////////////////////////////////////////////////////////////////////// // class RoxdokuGame /////////////////////////////////////////////////////////////////////////////// RoxdokuGame::RoxdokuGame(const QString& name, uint order, GameVariantCollection* collection) : GameVariant(name, collection), m_order(order), m_graph(nullptr) { m_symmetry = 0; } RoxdokuGame::~RoxdokuGame() { delete m_graph; } bool RoxdokuGame::canConfigure() const { return true; } bool RoxdokuGame::configure() { KMessageBox::information(nullptr, i18n("Configuration not yet implemented"), QLatin1String("")); return false; } bool RoxdokuGame::canStartEmpty() const { return true; } Game RoxdokuGame::startEmpty() { if(!m_graph) { m_graph = new SKGraph(m_order, TypeRoxdoku); m_graph->initRoxdoku(); } Puzzle* puzzle = new Puzzle(m_graph, false); puzzle->init(); return Game(puzzle); } Game RoxdokuGame::createGame(int difficulty, int symmetry) { if(!m_graph) { m_graph = new SKGraph(m_order, TypeRoxdoku); m_graph->initRoxdoku(); } Puzzle* puzzle = new Puzzle(m_graph, true); puzzle->init(difficulty, symmetry); return Game(puzzle); } KsView* RoxdokuGame::createView(const Game& /*game*/) const { qCDebug(KSudokuLog) << "KsView* ksudoku::RoxdokuGame::createView()"; return 0; } /////////////////////////////////////////////////////////////////////////////// // class CustomGame /////////////////////////////////////////////////////////////////////////////// CustomGame::CustomGame(const QString& name, const QUrl& url, GameVariantCollection* collection) : GameVariant(name, collection), m_url(url), m_graph(nullptr) { m_symmetry = 0; } CustomGame::~CustomGame() { delete m_graph; } bool CustomGame::canConfigure() const { return false; } bool CustomGame::configure() { return false; } bool CustomGame::canStartEmpty() const { return true; } Game CustomGame::startEmpty() { if (! createSKGraphObject()) { return Game(); } Puzzle* puzzle = new Puzzle(m_graph, false); puzzle->init(); return Game(puzzle); } Game CustomGame::createGame(int difficulty, int symmetry) { if (! createSKGraphObject()) { return Game(); } Puzzle* puzzle = new Puzzle(m_graph, true); puzzle->init(difficulty, symmetry); return Game(puzzle); } KsView* CustomGame::createView(const Game& /*game*/) const { qCDebug(KSudokuLog) << "KsView* ksudoku::CustomGame::createView()"; return 0; } bool CustomGame::createSKGraphObject() { if ((m_graph != 0) && ((m_graph->specificType() == Mathdoku) || (m_graph->specificType() == KillerSudoku))) { delete m_graph; // Re-create SKGraph for every Mathdoku or m_graph = 0; // Killer Sudoku game (re-inits cages and size). } if (m_graph == 0) { QString errorMsg; m_graph = ksudoku::Serializer::loadCustomShape(m_url, 0, errorMsg); } return (m_graph != 0); // True if the shapes/*.xml file loaded OK. } } diff --git a/src/gui/history.h b/src/gui/history.h index 8314b60..8860aa7 100644 --- a/src/gui/history.h +++ b/src/gui/history.h @@ -1,207 +1,205 @@ /*************************************************************************** * Copyright 2006-2007 Johannes Bergmeier * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #ifndef _KSUDOKUHISTORY_H_ #define _KSUDOKUHISTORY_H_ #include -#include -#include #include #include "globals.h" #include "ksudoku_types.h" namespace ksudoku { class CellInfo { public: inline CellInfo() : m_state(Marker), m_value(0), m_markers() { } inline CellInfo(ButtonState state, int value) : m_state(state), m_value(value), m_markers() { } inline CellInfo(const QBitArray& markers) : m_state(Marker), m_value(0), m_markers(markers) { } inline CellInfo(const CellInfo& info) : m_state(info.m_state), m_value(info.m_value), m_markers(info.m_markers) { } inline ButtonState state() const { return m_state; } inline int value() const { return m_value; } inline const QBitArray markers() const { return m_markers; } inline bool marker(int value) const { if(value > m_markers.size() || value == 0) return false; return m_markers[value-1]; } inline CellInfo& operator=(const CellInfo& info) { m_state = info.m_state; m_value = info.m_value; m_markers = info.m_markers; return *this; } private: ButtonState m_state; int m_value; QBitArray m_markers; }; class PuzzleState { public: PuzzleState() { } PuzzleState(int size, int values) : m_markers(values), m_values(size, 0), m_given(size) { for(int i = 0; i < values; i++) { m_markers[i] = QBitArray(size); } } public: void reset() { for(int i = 0; i < m_markers.size(); i++) { QBitArray &array = m_markers[i]; for(int j = 0; j < array.size(); j++) array.clearBit(j); } for(int i = 0; i < m_values.size(); i++) { m_values[i] = 0; m_given.clearBit(i); } } inline void setMarker(int index, int value, bool status) { if(value == 0 || value > m_markers.size()) return; m_markers[value-1].setBit(index, status); } inline void resetMarkers(int index) { for(int i = 0; i < m_markers.size(); i++) { m_markers[i].clearBit(index); } } inline void setMarkers(int index, const QBitArray& values) { if(values.size() == 0) { resetMarkers(index); return; } for(int i = 0; i < m_markers.size(); i++) { m_markers[i].setBit(index, values[i]); } } inline bool marker(int index, int value) const { if(value == 0 || value > m_markers.size()) return false; return m_markers[value-1][index]; } inline QBitArray markers(int index) const { QBitArray array(m_markers.size()); for(int i = 0; i < m_markers.size(); i++) { array.setBit(i, m_markers[i][index]); } return array; } inline void setGiven(int index, bool given) { m_given.setBit(index, given); } inline void setValue(int index, int value) { m_values[index] = value; } inline void setValue(int index, int value, bool given) { m_given.setBit(index, given); m_values[index] = value; } inline bool given(int index) const { return m_given[index]; } inline int value(int index) const { return m_values[index]; } // inline void operator=(const PuzzleState& state) { // m_markers = state.m_markers; // m_values = state.m_values; // m_given = state.m_given; // } inline void detach() { for(int i = 0; i < m_markers.size(); ++i) { // Detach m_markers // This actually is only needed once and not every loop // However this way it's more secure (m_markers.size() might be 0) m_markers[i] = m_markers[i]; // Detach from shared bit array data m_markers[i].detach(); } m_values.detach(); m_given.detach(); } inline const BoardContents allValues() const { return m_values; } /** *@note Use this method only to get size of puzzle when operating * directly on the puzzle state. */ inline int size() const { return m_values.size(); } private: QVector m_markers; BoardContents m_values; QBitArray m_given; }; class HistoryEvent { public: HistoryEvent(); HistoryEvent(int index, const CellInfo& changedCell); explicit HistoryEvent(const PuzzleState& newState); bool applyTo(PuzzleState& puzzle); bool undoOn(PuzzleState& puzzle) const; bool redoOn(PuzzleState& puzzle) const; const QVector& cellIndices() const { return m_cellsIndex; } const QVector& cellChanges() const { return m_cellsAfter; } private: void setPuzzleCell(PuzzleState& puzzle, int index, const CellInfo& cell) const; CellInfo getPuzzleCell(const PuzzleState& puzzle, int index) const; private: QVector m_cellsIndex; QVector m_cellsBefore; QVector m_cellsAfter; }; } #endif diff --git a/src/gui/ksudoku.cpp b/src/gui/ksudoku.cpp index 1358f69..0648337 100644 --- a/src/gui/ksudoku.cpp +++ b/src/gui/ksudoku.cpp @@ -1,929 +1,925 @@ /*************************************************************************** * Copyright 2005-2007 Francesco Rossi * * Copyright 2006-2007 Mick Kappenburg * * Copyright 2006-2008 Johannes Bergmeier * * Copyright 2012,2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "ksudoku.h" #include "ksudoku_logging.h" #include "globals.h" #include #include #include -#include #include #include #include #include #include #include #include #include -#include -#include #include #include -#include #include #include #include #include #include #include #include #include #include #define USE_UNSTABLE_LIBKDEGAMESPRIVATE_API #include #include "ksview.h" #include "gameactions.h" #include "renderer.h" #include "puzzle.h" // TODO #include "skgraph.h" #include "serializer.h" #include "puzzleprinter.h" #include "gamevariants.h" #include "welcomescreen.h" #include "valuelistwidget.h" #include "settings.h" #include "config.h" using namespace ksudoku; void KSudoku::onCompleted(bool isCorrect, const QTime& required, bool withHelp) { if(!isCorrect) { KMessageBox::information(this, i18n("Sorry, your solution contains mistakes.\n\nEnable \"Show errors\" in the settings to highlight them.")); return; } QString msg; int secs = QTime(0,0).secsTo(required); int mins = secs / 60; secs = secs % 60; if(withHelp) if (mins == 0) msg = i18np("Congratulations! You made it in 1 second. With some tricks.", "Congratulations! You made it in %1 seconds. With some tricks.", secs); else if (secs == 0) msg = i18np("Congratulations! You made it in 1 minute. With some tricks.", "Congratulations! You made it in %1 minutes. With some tricks.", mins); else msg = i18nc("The two parameters are strings like '2 minutes' or '1 second'.", "Congratulations! You made it in %1 and %2. With some tricks.", i18np("1 minute", "%1 minutes", mins), i18np("1 second", "%1 seconds", secs)); else if (mins == 0) msg = i18np("Congratulations! You made it in 1 second.", "Congratulations! You made it in %1 seconds.", secs); else if (secs == 0) msg = i18np("Congratulations! You made it in 1 minute.", "Congratulations! You made it in %1 minutes.", mins); else msg = i18nc("The two parameters are strings like '2 minutes' or '1 second'.", "Congratulations! You made it in %1 and %2.", i18np("1 minute", "%1 minutes", mins), i18np("1 second", "%1 seconds", secs)); onModified(true); // make sure buttons have the correct enabled state KMessageBox::information(this, msg); } // void KSudoku::updateStatusBar() // { // QString m=""; // // QWidget* current = m_tabs->currentPage(); // // if(KsView* view = dynamic_cast(current)) // // m = view->status(); // // if(currentView()) // // m = currentView()->status(); // // // TODO fix this: add new status bar generation code // // statusBar()->showMessage(m); // } KSudoku::KSudoku() : KXmlGuiWindow(), m_gameVariants(new GameVariantCollection(this, true)), m_puzzlePrinter(0) { setObjectName( QStringLiteral("ksudoku" )); m_gameWidget = 0; m_gameUI = 0; m_gameActions = 0; // then, setup our actions setupActions(); setupGUI(ToolBar | Keys | Save | Create | StatusBar); wrapper = new QWidget(); (void) new QHBoxLayout(wrapper); QMainWindow::setCentralWidget(wrapper); wrapper->show(); // Create ValueListWidget m_valueListWidget = new ValueListWidget(wrapper); wrapper->layout()->addWidget(m_valueListWidget); m_valueListWidget->setFixedWidth(60); m_welcomeScreen = new WelcomeScreen(wrapper, m_gameVariants); wrapper->layout()->addWidget(m_welcomeScreen); connect(m_welcomeScreen, &ksudoku::WelcomeScreen::newGameStarted, this, &KSudoku::startGame); setupStatusBar(m_welcomeScreen->difficulty(), m_welcomeScreen->symmetry()); showWelcomeScreen(); updateShapesList(); // QTimer *timer = new QTimer( this ); // connect( timer, SIGNAL(timeout()), this, SLOT(updateStatusBar()) ); // updateStatusBar(); // timer->start( 1000); //TODO PORT, false ); // 2 seconds single-shot timer } KSudoku::~KSudoku() { delete m_puzzlePrinter; endCurrentGame(); } void KSudoku::updateShapesList() { // TODO clear the list GameVariant* variant = 0; variant = new SudokuGame(i18n("Sudoku Standard (9x9)"), 9, m_gameVariants); variant->setDescription(i18n("The classic and fashionable game")); variant->setIcon(QStringLiteral("ksudoku-ksudoku_9x9")); #ifdef OPENGL_SUPPORT variant = new RoxdokuGame(i18n("Roxdoku 9 (3x3x3)"), 9, m_gameVariants); variant->setDescription(i18n("The Rox 3D Sudoku")); variant->setIcon(QStringLiteral("ksudoku-roxdoku_3x3x3")); #endif const QStringList gamevariantdirs = QStandardPaths::locateAll(QStandardPaths::GenericDataLocation, QStringLiteral("ksudoku"), QStandardPaths::LocateDirectory); QFileInfoList filepaths; for (const QString& gamevariantdir : gamevariantdirs) { const auto fileNames = QDir(gamevariantdir).entryInfoList(QStringList() << QStringLiteral("*.desktop"), QDir::Files | QDir::Readable | QDir::NoDotAndDotDot); filepaths.append(fileNames); } QString variantName; QString variantDescr; QString variantDataPath; QString variantIcon; for (const QFileInfo &configFileInfo : qAsConst(filepaths)) { const QDir variantDir = configFileInfo.dir(); KConfig variantConfig(configFileInfo.filePath(), KConfig::SimpleConfig); KConfigGroup group = variantConfig.group ("KSudokuVariant"); variantName = group.readEntry("Name", i18n("Missing Variant Name")); // Translated. variantDescr = group.readEntry("Description", ""); // Translated. variantIcon = group.readEntry("Icon", "ksudoku-ksudoku_9x9"); const QString variantDataFile = group.readEntry("FileName", ""); if(variantDataFile == QLatin1String("")) continue; variantDataPath = variantDir.filePath(variantDataFile); variant = new CustomGame(variantName, QUrl::fromLocalFile(variantDataPath), m_gameVariants); variant->setDescription(variantDescr); variant->setIcon(variantIcon); } // Put variants first and extra sizes last. variant = new SudokuGame(i18n("Sudoku 16x16"), 16, m_gameVariants); variant->setDescription(i18n("Sudoku with 16 symbols")); variant->setIcon(QStringLiteral("ksudoku-ksudoku_16x16")); variant = new SudokuGame(i18n("Sudoku 25x25"), 25, m_gameVariants); variant->setDescription(i18n("Sudoku with 25 symbols")); variant->setIcon(QStringLiteral("ksudoku-ksudoku_25x25")); #ifdef OPENGL_SUPPORT variant = new RoxdokuGame(i18n("Roxdoku 16 (4x4x4)"), 16, m_gameVariants); variant->setDescription(i18n("The Rox 3D sudoku with 16 symbols")); variant->setIcon(QStringLiteral("ksudoku-roxdoku_4x4x4")); variant = new RoxdokuGame(i18n("Roxdoku 25 (5x5x5)"), 25, m_gameVariants); variant->setDescription(i18n("The Rox 3D sudoku with 25 symbols")); variant->setIcon(QStringLiteral("ksudoku-roxdoku_5x5x5")); #endif } void KSudoku::startGame(const Game& game) { m_welcomeScreen->hide(); endCurrentGame(); KsView* view = new KsView(game, m_gameActions, this); view->setValueListWidget(m_valueListWidget); view->createView(); connect(view, &KsView::valueSelected, m_valueListWidget, &ksudoku::ValueListWidget::selectValue); connect(m_valueListWidget, &ksudoku::ValueListWidget::valueSelected, view, &KsView::selectValue); // connect(view, SIGNAL(valueSelected(int)), SLOT(updateStatusBar())); QWidget* widget = view->widget(); m_gameUI = view; Game g = currentGame(); g.setMessageParent(view->widget()); wrapper->layout()->addWidget(widget); widget->show(); widget->setFocus(); connect(game.interface(), &GameIFace::completed, this, &KSudoku::onCompleted); connect(game.interface(), &GameIFace::modified, this, &KSudoku::onModified); adaptActions2View(); QSizePolicy policy(QSizePolicy::Expanding, QSizePolicy::Expanding); policy.setHorizontalStretch(1); policy.setVerticalStretch(1); widget->setSizePolicy(policy); m_valueListWidget->setMaxValue(view->game().order()); m_valueListWidget->selectValue(1); m_valueListWidget->show(); SudokuType t = game.puzzle()->graph()->specificType(); bool playing = game.puzzle()->hasSolution(); if (playing && (t == Mathdoku)) { KMessageBox::information (this, i18n("Mathdoku puzzles can have any size from 3x3 up to 9x9. " "The solution is a grid in which every row and every " "column contains the available digits (1-3 up to 1-9) " "exactly once. The grid is covered with irregularly " "shaped cages.\n" "\n" "Cages of size 1 are starting-values or clues, but there " "are not many of them. Cages of larger size have a target " "value and an arithmetic operator (+-x/). The digits in " "the cage must combine together, using the operator, to " "reach the target value, e.g. '12x' means that the digits " "must multiply together to make 12. A digit can occur " "more than once in a cage, provided it occurs in " "different rows and columns.\n" "\n" "In general, larger Mathdokus are more difficult and so " "are larger cages. You can select the puzzle size in " "KSudoku's Settings dialog and the maximum cage-size by " "using KSudoku's Difficulty button."), i18n("Playing Mathdoku"), QStringLiteral("PlayingMathdoku")); } else if (playing && (t == KillerSudoku)) { KMessageBox::information (this, i18n("Killer Sudoku puzzles can have sizes 4x4 or 9x9, with " "either four 2x2 blocks or nine 3x3 blocks. The solution " "must follow Classic Sudoku rules. The difference is that " "there are few starting-values or clues (if any). Instead " "the grid is covered with irregularly shaped cages.\n" "\n" "Cages of size 1 are starting-values or clues. Cages of " "larger size have a target value and the digits in them " "must add up to that value. In Killer Sudoku, a cage " "cannot contain any digit more than once.\n" "\n" "In general, larger cages are more difficult. You can " "select the maximum cage-size by using KSudoku's " "Difficulty button."), i18n("Playing Killer Sudoku"), QStringLiteral("PlayingKillerSudoku")); } else if ((t == Mathdoku) || (t == KillerSudoku)) { KMessageBox::information (this, i18n("Mathdoku and Killer Sudoku puzzles have to be keyed in " "by working on one cage at a time. To start a cage, left " "click on any unused cell or enter a number in the cell " "that is under the cursor or enter + - / or x there. A " "small cage-label will appear in that cell. To extend the " "cage in any direction, left-click on a neigbouring cell " "or move the cursor there and type a Space.\n" "\n" "The number you type is the cage's value and it can have " "one or more digits, including zero. A cell of size 1 has " "to have a 1-digit number, as in a normal Sudoku puzzle. " "It becomes a starting-value or clue for the player.\n" "\n" "The + - / or x is the operator (Add, Subtract, Divide or " "Multiply). You must have one in cages of size 2 or more. " "In Killer Sudoku, the operator is provided automatically " "because it is always + or none.\n" "\n" "You can enter digits, operators and cells in any order. " "To complete the cage and start another cage, always " "press Return. If you make a mistake, the only thing to " "do is delete a whole cage and re-enter it. Use right " "click in the current cage or any earlier cage, if you " "wish to delete it. Alternatively, use the cursor and the " "Delete or Backspace key.\n" "\n" "When the grid is filled with cages, hit the Check " "button, to solve the puzzle and make sure there is only " "one solution. If the check fails, you have probably made " "an error somewhere in one of the cages."), i18n("Data-entry for Puzzles with Cages"), QStringLiteral("CageDataEntry")); } } void KSudoku::endCurrentGame() { m_valueListWidget->hide(); delete m_gameUI; m_gameUI = 0; adaptActions2View(); } void KSudoku::loadGame(const QUrl& Url) { QString errorMsg; const Game game = ksudoku::Serializer::load(Url, this, errorMsg); if(!game.isValid()) { KMessageBox::information(this, errorMsg); return; } startGame(game); } void KSudoku::showWelcomeScreen() { endCurrentGame(); m_welcomeScreen->show(); } void KSudoku::giveHint() { Game game = currentGame(); if(!game.isValid()) return; game.giveHint(); } void KSudoku::autoSolve() { Game game = currentGame(); if(!game.isValid()) return; game.autoSolve(); } // Check the game setup, copy the puzzle, init and solve the copy and show the // result (i.e. implement the "Check" action). If the user agrees, start play. void KSudoku::dubPuzzle() { Game game = currentGame(); if(!game.isValid()) return; if(!game.simpleCheck()) { KMessageBox::information(this, i18n("The puzzle you entered contains some errors.")); return; } // Create a new Puzzle object, with same Graph and solution flag = true. ksudoku::Puzzle* puzzle = game.puzzle()->dubPuzzle(); // Copy the given values of the puzzle, then run it through the solver. // The solution, if valid, is saved in puzzle->m_solution2. int state = puzzle->init(game.allValues()); if(state <= 0) { KMessageBox::information (this, i18n("Sorry, no solutions have been found. Please check " "that you have entered in the puzzle completely and " "correctly."), i18n("Check Puzzle")); delete puzzle; return; } else if(state == 1) { KMessageBox::information (this, i18n("The Puzzle you entered has a unique solution and " "is ready to be played."), i18n("Check Puzzle")); } else { KMessageBox::information (this, i18n("The Puzzle you entered has multiple solutions. " "Please check that you have entered in the puzzle " "completely and correctly."), i18n("Check Puzzle")); } if(KMessageBox::questionYesNo(this, i18n("Do you wish to play the puzzle now?"), i18n("Play Puzzle"), KGuiItem(i18n("Play")), KStandardGuiItem::cancel() ) == KMessageBox::Yes) { startGame(ksudoku::Game(puzzle)); } else { delete puzzle; } return; } void KSudoku::genMultiple() { //KMessageBox::information(this, i18n("Sorry, this feature is under development.")); } void KSudoku::setupActions() { m_gameActions = new ksudoku::GameActions(actionCollection(), this); m_gameActions->init(); QKeySequence shortcut; setAcceptDrops(true); KStandardGameAction::gameNew(this, SLOT(gameNew()), actionCollection()); KStandardGameAction::restart(this, SLOT(gameRestart()), actionCollection()); KStandardGameAction::load(this, SLOT(gameOpen()), actionCollection()); m_gameSave = KStandardGameAction::save(this, SLOT(gameSave()), actionCollection()); m_gameSaveAs = KStandardGameAction::saveAs(this, SLOT(gameSaveAs()), actionCollection()); KStandardGameAction::print(this, SLOT(gamePrint()), actionCollection()); KStandardGameAction::quit(this, SLOT(close()), actionCollection()); // TODO Export is disabled due to missing port to KDE4. // createAction("game_export", SLOT(gameExport()), i18n("Export")); KStandardAction::preferences(this, SLOT(optionsPreferences()), actionCollection()); // Settings: enable messages that the user marked "Do not show again". QAction* enableMessagesAct = new QAction(i18n("Enable all messages"),this); actionCollection()->addAction(QStringLiteral("enable_messages"), enableMessagesAct); connect(enableMessagesAct, &QAction::triggered, this, &KSudoku::enableMessages); //History KStandardGameAction::undo(this, SLOT(undo()), actionCollection()); KStandardGameAction::redo(this, SLOT(redo()), actionCollection()); QAction * a = KStandardGameAction::hint(this, SLOT(giveHint()), actionCollection()); // The default value (H) conflicts with the keys assigned // to add letter/numbers to the board. actionCollection()->setDefaultShortcut(a, QKeySequence(Qt::Key_F2)); KStandardGameAction::solve(this, SLOT(autoSolve()), actionCollection()); a = new QAction(this); actionCollection()->addAction( QStringLiteral( "move_dub_puzzle" ), a); a->setText(i18n("Check")); a->setIcon(QIcon::fromTheme( QStringLiteral( "games-endturn" ))); connect(a, &QAction::triggered, this, &KSudoku::dubPuzzle); addAction(a); } void KSudoku::setupStatusBar (int difficulty, int symmetry) { // Use the standard combo box for difficulty, from KDE Games library. const int nStandardLevels = 4; const KGameDifficulty::standardLevel standardLevels[nStandardLevels] = {KGameDifficulty::VeryEasy, KGameDifficulty::Easy, KGameDifficulty::Medium, KGameDifficulty::Hard}; statusBar()->addPermanentWidget (new QLabel (i18n("Difficulty"))); KGameDifficulty::init (this, this, SLOT (difficultyChanged(KGameDifficulty::standardLevel)), SLOT (difficultyChanged(int))); KGameDifficulty::addStandardLevel(KGameDifficulty::VeryEasy); KGameDifficulty::addStandardLevel(KGameDifficulty::Easy); KGameDifficulty::addStandardLevel(KGameDifficulty::Medium); KGameDifficulty::addStandardLevel(KGameDifficulty::Hard); KGameDifficulty::addCustomLevel(Diabolical, i18nc("A level of difficulty in Sudoku puzzles", "Diabolical")); KGameDifficulty::addCustomLevel(Unlimited, i18nc("A level of difficulty in Sudoku puzzles", "Unlimited")); KGameDifficulty::setRestartOnChange(KGameDifficulty::NoRestartOnChange); // Set default value of difficulty. if (difficulty < nStandardLevels) { KGameDifficulty::setLevel (standardLevels[difficulty]); } else { KGameDifficulty::setLevelCustom (difficulty); } KGameDifficulty::setEnabled (true); // Set up a combo box for symmetry of puzzle layout. statusBar()->addPermanentWidget (new QLabel (i18n("Symmetry"))); QComboBox * symmetryBox = new QComboBox (this); QObject::connect(symmetryBox, static_cast(&QComboBox::activated), this, &KSudoku::symmetryChanged); symmetryBox->setToolTip(i18nc( "Symmetry of layout of clues when puzzle starts", "Symmetry")); symmetryBox->setWhatsThis(i18n( "The symmetry of layout of the clues when the puzzle starts")); statusBar()->addPermanentWidget (symmetryBox); symmetryBox->addItem(i18nc("Symmetry of layout of clues", "Diagonal")); symmetryBox->addItem(i18nc("Symmetry of layout of clues", "Central")); symmetryBox->addItem(i18nc("Symmetry of layout of clues", "Left-Right")); symmetryBox->addItem(i18nc("Symmetry of layout of clues", "Spiral")); symmetryBox->addItem(i18nc("Symmetry of layout of clues", "Four-Way")); symmetryBox->addItem(i18nc("Symmetry of layout of clues", "Random Choice")); symmetryBox->addItem(i18n("No Symmetry")); symmetryBox->setCurrentIndex (symmetry); } void KSudoku::adaptActions2View() { Game game = currentGame(); m_gameSave->setEnabled(game.isValid()); m_gameSaveAs->setEnabled(game.isValid()); action("game_new")->setEnabled(game.isValid()); action("game_restart")->setEnabled(game.isValid()); action("game_print")->setEnabled(game.isValid()); if(game.isValid()) { bool isEnterPuzzleMode = !game.puzzle()->hasSolution(); action("move_hint")->setVisible(!isEnterPuzzleMode); action("move_solve")->setVisible(!isEnterPuzzleMode); action("move_dub_puzzle")->setVisible(isEnterPuzzleMode); action("move_undo")->setEnabled(game.canUndo()); action("move_redo")->setEnabled(game.canRedo()); action("move_hint") ->setEnabled( game.puzzle()->hasSolution()); action("move_solve") ->setEnabled( game.puzzle()->hasSolution()); action("move_dub_puzzle")->setEnabled( ! game.puzzle()->hasSolution()); } else { action("move_undo")->setEnabled(false); action("move_redo")->setEnabled(false); action("move_hint")->setVisible(false); action("move_solve")->setVisible(false); action("move_dub_puzzle")->setVisible(false); } } void KSudoku::onModified(bool /*isModified*/) { Game game = currentGame(); if(game.isValid()) { action("move_undo")->setEnabled(game.canUndo()); action("move_redo")->setEnabled(game.canRedo()); action("move_hint")->setEnabled(!game.allValuesSetAndUsable()); action("move_solve")->setEnabled(!game.wasFinished()); } } void KSudoku::undo() { Game game = currentGame(); if(!game.isValid()) return; game.interface()->undo(); if(!game.canUndo()) { action("move_undo")->setEnabled(false); } } void KSudoku::redo() { Game game = currentGame(); if(!game.isValid()) return; game.interface()->redo(); if(!game.canRedo()) { action("move_redo")->setEnabled(false); } } void KSudoku::push() { // TODO replace this with history // if(type == 0) {if(m_view) m_view->push();return;} // if(glwin) glwin->push(); } void KSudoku::pop() { // TODO replace this with history // if(type == 0) {if(m_view) m_view->pop(); return;} // if(glwin) glwin->pop(); } void KSudoku::dragEnterEvent(QDragEnterEvent * event) { // accept uri drops only if(event->mimeData()->hasUrls()) event->accept(); } void KSudoku::dropEvent(QDropEvent *event) { const QMimeData * data = event->mimeData(); if(data->hasUrls()) { QList Urls = data->urls(); if ( !Urls.isEmpty() ) { // okay, we have a URI.. process it const QUrl &Url = Urls.first(); QString errorMsg; const Game game = ksudoku::Serializer::load(Url, this, errorMsg); if(game.isValid()) startGame(game); else KMessageBox::error(this, errorMsg, i18n("Could not load game.")); } } } void KSudoku::gameNew() { // this slot is called whenever the Game->New menu is selected, // the New shortcut is pressed (usually CTRL+N) or the New toolbar // button is clicked if(!currentView()) return; // only show question when the current game hasn't been finished until now if(!m_gameUI->game().wasFinished()) { if(KMessageBox::questionYesNo(this, i18n("Do you really want to end this game in order to start a new one?"), i18nc("window title", "New Game"), KGuiItem(i18nc("button label", "New Game")), KStandardGuiItem::cancel() ) != KMessageBox::Yes) return; } showWelcomeScreen(); } void KSudoku::gameRestart() { if (!currentView()) return; auto game = currentGame(); // only show question when the current game hasn't been finished until now if (!game.wasFinished()) { if (KMessageBox::questionYesNo(this, i18n("Do you really want to restart this game?"), i18nc("window title", "Restart Game"), KGuiItem(i18nc("button label", "Restart Game")), KStandardGuiItem::cancel() ) != KMessageBox::Yes) { return; } } game.restart(); } void KSudoku::gameOpen() { // this slot is called whenever the Game->Open menu is selected, // the Open shortcut is pressed (usually CTRL+O) or the Open toolbar // button is clicked // standard filedialog const QUrl Url = QFileDialog::getOpenFileUrl(this, i18n("Open Location"), QUrl::fromLocalFile(QDir::homePath()), QString()); if (!Url.isEmpty() && Url.isValid()) { QString errorMsg; Game game = ksudoku::Serializer::load(Url, this, errorMsg); if(!game.isValid()) { KMessageBox::error(this, errorMsg, i18n("Could not load game.")); return; } game.setUrl(Url); // (new KSudoku(game))->show(); startGame(game); // delete game; } } void KSudoku::gameSave() { // this slot is called whenever the Game->Save menu is selected, // the Save shortcut is pressed (usually CTRL+S) or the Save toolbar // button is clicked // save the current file Game game = currentGame(); if(!game.isValid()) return; if(game.getUrl().isEmpty()) game.setUrl(QFileDialog::getSaveFileUrl()); if (!game.getUrl().isEmpty() && game.getUrl().isValid()) { QString errorMsg; if (!ksudoku::Serializer::store(game, game.getUrl(), this, errorMsg)) KMessageBox::error(this, errorMsg, i18n("Error Writing File")); } } void KSudoku::gameSaveAs() { // this slot is called whenever the Game->Save As menu is selected, Game game = currentGame(); if(!game.isValid()) return; game.setUrl(QFileDialog::getSaveFileUrl()); if (!game.getUrl().isEmpty() && game.getUrl().isValid()) gameSave(); } void KSudoku::gamePrint() { // This slot is called whenever the Game->Print action is selected. Game game = currentGame(); if (! game.isValid()) { KMessageBox::information (this, i18n("There seems to be no puzzle to print.")); return; } if (! m_puzzlePrinter) { m_puzzlePrinter = new PuzzlePrinter (this); } m_puzzlePrinter->print (game); } bool KSudoku::queryClose() { if (m_puzzlePrinter) { m_puzzlePrinter->endPrint(); } return true; } void KSudoku::gameExport() { //TODO PORT /* Game game = currentGame(); if(!game.isValid()) return; ksudoku::ExportDlg e(*game.puzzle(), *game.symbols() ); e.exec(); */ } void KSudoku::optionsPreferences() { if ( KConfigDialog::showDialog(QStringLiteral("settings")) ) return; KConfigDialog *dialog = new KConfigDialog(this, QStringLiteral("settings"), Settings::self()); GameConfig* gameConfig = new GameConfig(); dialog->addPage(gameConfig, i18nc("Game Section in Config", "Game"), QStringLiteral("games-config-options")); dialog->addPage(new KGameThemeSelector(dialog, Settings::self(), KGameThemeSelector::NewStuffDisableDownload), i18n("Theme"), QStringLiteral("games-config-theme")); //QT5 dialog->setHelp(QString(),"ksudoku"); connect(dialog, &KConfigDialog::settingsChanged, this, &KSudoku::updateSettings); dialog->show(); } void KSudoku::updateSettings() { Renderer::instance()->loadTheme(Settings::theme()); KsView* view = currentView(); if(view) { int order = view->game().order(); m_valueListWidget->setMaxValue(order); view->settingsChanged(); } emit settingsChanged(); } void KSudoku::difficultyChanged (KGameDifficulty::standardLevel difficulty) { qCDebug(KSudokuLog) << "Set difficulty =" << difficulty; int newDifficulty = VeryEasy; switch (difficulty) { case KGameDifficulty::VeryEasy: newDifficulty = VeryEasy; break; case KGameDifficulty::Easy: newDifficulty = Easy; break; case KGameDifficulty::Medium: newDifficulty = Medium; break; case KGameDifficulty::Hard: newDifficulty = Hard; break; default: return; } qCDebug(KSudokuLog) << "Set new difficulty =" << newDifficulty; m_welcomeScreen->setDifficulty(newDifficulty); return; } void KSudoku::difficultyChanged (int difficulty) { qCDebug(KSudokuLog) << "Set custom difficulty =" << difficulty; m_welcomeScreen->setDifficulty(difficulty); if (difficulty == Unlimited) { KMessageBox::information (this, i18n("Warning: The Unlimited difficulty level has no limit on " "how many guesses or branch points are required to solve " "the puzzle and there is no lower limit on how soon " "guessing becomes necessary.\n\n" "Please also note that the generation of this type of puzzle " "might take much longer than other ones. During this time " "KSudoku will not respond."), i18n("Warning"), QStringLiteral("WarningReUnlimited")); } } void KSudoku::symmetryChanged (int symmetry) { qCDebug(KSudokuLog) << "Set symmetry =" << symmetry; m_welcomeScreen->setSymmetry(symmetry); } // void KSudoku::changeStatusbar(const QString& text) // { // // display the text on the statusbar // statusBar()->showMessage(text); // } void KSudoku::changeCaption(const QString& text) { // display the text on the caption setCaption(text); } Game KSudoku::currentGame() const { ksudoku::KsView* view = currentView(); if(view) return view->game(); else return Game(); } ksudoku::KsView* KSudoku::currentView() const{ return m_gameUI; } void KSudoku::enableMessages() { // Enable all messages that the user has marked "Do not show again". int result = KMessageBox::questionYesNo(this, i18n("This will enable all the dialogs that you had disabled by marking " "the 'Do not show this message again' option.\n\n" "Do you want to continue?")); if (result == KMessageBox::Yes) { KMessageBox::enableAllMessages(); KSharedConfig::openConfig()->sync(); // Save the changes to disk. } } #if 0 KSudokuNewStuff::KSudokuNewStuff( KSudoku* v ) : KNewStuff( "ksudoku", (QWidget*) v ) { parent = v; } bool KSudokuNewStuff::install( const QString &fileName ) { KTar archive( fileName ); if ( !archive.open( QIODevice::ReadOnly ) ) return false; const KArchiveDirectory *archiveDir = archive.directory(); const QString destDir = QStandardPaths::writableLocation( QStandardPaths::GenericDataLocation ) + QStringLiteral("/ksudoku/"); QDir().mkpath(destDir); archiveDir->copyTo(destDir); archive.close(); //find custom shapes parent->updateShapesList(); return true; } bool KSudokuNewStuff::createUploadFile( const QString &/*fileName*/ ) { return true; } #endif diff --git a/src/gui/ksudoku_client.cpp b/src/gui/ksudoku_client.cpp index 0253223..78abae8 100644 --- a/src/gui/ksudoku_client.cpp +++ b/src/gui/ksudoku_client.cpp @@ -1,46 +1,44 @@ /*************************************************************************** * Copyright 2005-2007 Francesco Rossi * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include #include #include -#include -#include int main(int argc, char **argv) { QApplication app(argc, argv); // get our DCOP client and attach so that we may use it DCOPClient *client = app.dcopClient(); client->attach(); // do a 'send' for now BoardContents data; QDataStream ds(data, QIODevice::WriteOnly); if (argc > 1) ds << QString(argv[1]); else ds << QString("https://www.kde.org"); client->send("ksudoku", "ksudokuIface", "openURL(QString)", data); return app.exec(); } diff --git a/src/gui/ksudokugame.cpp b/src/gui/ksudokugame.cpp index 6aa6e00..1a78fca 100644 --- a/src/gui/ksudokugame.cpp +++ b/src/gui/ksudokugame.cpp @@ -1,801 +1,801 @@ /*************************************************************************** * Copyright 2007 Francesco Rossi * * Copyright 2006-2007 Mick Kappenburg * * Copyright 2006-2007 Johannes Bergmeier * * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "ksudokugame.h" #include "ksudoku_logging.h" #include "puzzle.h" #include "history.h" #include "globals.h" #include #include -#include #include #include #include +#include class QWidget; namespace ksudoku { /** * @TODO replace m_refCount with QAtomic (in KDE4 version) */ class Game::Private : public GameIFace { public: inline Private() : m_refCount(1) { } inline ~Private() { delete puzzle; } public: inline void ref() { ++m_refCount; } inline bool deref() { return !--m_refCount; } private: int m_refCount; public: // The slots of GameIFace void undo() override; void redo() override; void addCheckpoint() override; void undo2Checkpoint() override; public: inline void emitModified(bool isModified) { emit modified(isModified); } inline void emitCompleted(bool isCorrect, const QTime& required, bool withHelp) { emit completed(isCorrect, required, withHelp); } inline void emitCellChange(int index) { emit cellChange(index); } inline void emitFullChange() { emit fullChange(); } inline void emitCageChange(int cageNumP1, bool showLabel) { emit cageChange(cageNumP1, showLabel); } public: PuzzleState state; bool hadHelp : 1; bool wasFinished : 1; Puzzle* puzzle; QElapsedTimer time; int accumTime; QUrl url; QList history; int historyPos; QVector m_cage; int m_cageValue; CageOperator m_cageOperator; int m_currentCageSaved; QWidget * m_messageParent; }; void Game::Private::undo() { if(historyPos == 0) return; HistoryEvent event(history[--historyPos]); event.undoOn(state); const QVector& indices = event.cellIndices(); if(indices.count() > 10) { emit fullChange(); } else { for(int i = 0; i < indices.count(); ++i) emit cellChange(indices[i]); } emit modified(true); } void Game::Private::redo() { if(historyPos == history.count()) return; HistoryEvent event(history[historyPos++]); event.redoOn(state); const QVector& indices = event.cellIndices(); if(indices.count() > 10) { emit fullChange(); } else { for(int i = 0; i < indices.count(); ++i) emit cellChange(indices[i]); } emit modified(true); } void Game::Private::addCheckpoint() { } void Game::Private::undo2Checkpoint() { } /* * The Game */ Game::Game() : m_private(0) { } Game::Game(Puzzle* puzzle) : m_private(0) { if(!puzzle) return; m_private = new Private(); m_private->puzzle = puzzle; m_private->hadHelp = false; m_private->wasFinished = false; m_private->state = PuzzleState(size(), m_private->puzzle->order()); m_private->state.reset(); for(int i = 0; i < size(); i++) { m_private->state.setValue(i, m_private->puzzle->value(i)); if(value(i) != 0) m_private->state.setGiven(i, true); } m_private->historyPos = 0; m_private->accumTime = 0; m_private->time.start(); m_private->m_currentCageSaved = false; } Game::Game(const Game& game) : m_private(game.m_private) { if(m_private) m_private->ref(); } Game::~Game() { if(m_private && m_private->deref()) delete m_private; } Game& Game::operator=(const Game& game) { if(m_private == game.m_private) return *this; if(m_private && m_private->deref()) delete m_private; m_private = game.m_private; if(m_private) game.m_private->ref(); return *this; } bool Game::simpleCheck() const { // IDW TODO - This does nothing useful now // that connections have gone. if(!m_private) return false; qCDebug(KSudokuLog) << "BYPASSED Game::simpleCheck()"; return true; // IDW: disabled rest of test. // IDW test. Eliminated optimized[] arrays and xxxConnection() functions. } void Game::restart() { while (canUndo()) { interface()->undo(); } m_private->history.clear(); // otherwise we could do redo m_private->wasFinished = false; m_private->emitModified(true); // e.g. to update undo/redo action state } int Game::order() const { if(!m_private) return 0; return m_private->puzzle->order(); } int Game::size() const { if(!m_private) return 0; return m_private->puzzle->size(); } GameIFace* Game::interface() const { return m_private; } Puzzle* Game::puzzle() const { if(!m_private) return 0; return m_private->puzzle; } void Game::setUrl(const QUrl& url) { if(!m_private) return; m_private->url = url; } QUrl Game::getUrl() const { if(!m_private) return QUrl(); return m_private->url; } void Game::setGiven(int index, bool given) { if(!m_private) return; if(given != m_private->state.given(index)) { if(given) { doEvent(HistoryEvent(index, CellInfo(GivenValue, m_private->state.value(index)))); } else { doEvent(HistoryEvent(index, CellInfo(CorrectValue, m_private->state.value(index)))); } m_private->emitCellChange(index); m_private->emitModified(true); } } bool Game::setMarker(int index, int val, bool state) { if(!m_private) return false; if(val == 0 || val > m_private->puzzle->order()) return false; if(m_private->state.given(index)) return false; int val2 = value(index); if(val == val2) { doEvent(HistoryEvent(index, CellInfo())); } else { QBitArray markers = m_private->state.markers(index); markers.detach(); if(val2 != 0) { markers.setBit(val2 - 1, true); } markers.setBit(val - 1, state); doEvent(HistoryEvent(index, CellInfo(markers))); } // almost every time this function will change the cell m_private->emitCellChange(index); m_private->emitModified(true); return true; } void Game::setValue(int index, int val) { if(!m_private) return; // If entering in a puzzle, Mathdoku/KillerSudoku has its own procedure. if (! m_private->puzzle->hasSolution()) { if (addToCage (index, val)) { return; // Value went in a Mathdoku/KillerSudoku puzzle. } } if ((val == 32) || (val == 26)) { // Delete-action or Qt::Key_0. val = 0; // Clear the cell. } // Solve all kinds of puzzles or enter in a Sudoku or Roxdoku puzzle. if(val > m_private->puzzle->order()) return; if(m_private->state.given(index)) return; int oldvalue = value(index); doEvent(HistoryEvent(index, CellInfo(CorrectValue, val))); m_private->emitCellChange(index); m_private->emitModified(true); if(oldvalue != val) checkCompleted(); } bool Game::addToCage (int pos, int val) { SKGraph * g = m_private->puzzle->graph(); SudokuType t = g->specificType(); if ((t != Mathdoku) && (t != KillerSudoku)) { return false; // We are not keying in a cage. } #ifdef MATHDOKUENTRY_LOG qCDebug(KSudokuLog) << "Game::addToCage: pos" << pos << "action" << val; #endif if (! m_private->m_currentCageSaved) { // Start a new cage. m_private->m_cage.clear(); m_private->m_cageValue = 0; m_private->m_cageOperator = NoOperator; } if ((val != 32) && (! validCell (pos, g))) { return true; // Invalid pos and not deleting: go no further. } CageOperator cageOp = m_private->m_cageOperator; if ((val >= 1) && (val <= 9)) { // Append a non-zero digit to the cage-value. m_private->m_cageValue = 10 * m_private->m_cageValue + val; } else { switch (val) { case 24: // Qt::Key_X = multiply. cageOp = Multiply; break; case 26: // Qt::Key_0 if (m_private->m_cageValue > 0) { // Append a zero to the cage-value. m_private->m_cageValue = 10 * m_private->m_cageValue; } break; case 27: // Qt::Key_Slash. cageOp = Divide; break; case 28: // Qt::Key_Minus. cageOp = Subtract; break; case 29: // Qt::Key_Plus. cageOp = Add; break; case 30: // Left click or Qt::Key_Space = drop through and break; // add cell to cage. case 31: // Qt::Key_Return = end cage. finishCurrentCage (g); return true; break; case 32: // Right click or Delete/Bkspace = delete a whole cage. deleteCageAt (pos, g); return true; break; default: return false; break; } } // Valid keystroke and position: store and display the current cage. if (m_private->m_cage.indexOf (pos) < 0) { m_private->m_cage.append (pos); // Add cell to current cage. } if (t == KillerSudoku) { if (cageOp != NoOperator) { KMessageBox::information (messageParent(), i18n("In Killer Sudoku, the operator is always + or none " "and KSudoku automatically sets the correct choice."), i18n("Killer Sudoku Cage"), QStringLiteral("KillerCageInfo")); } // Set the operator to none or Add, depending on the cage-size. cageOp = (m_private->m_cage.size() > 1) ? Add : NoOperator; } // TODO - In Killer Sudoku, show the operator during data-entry. m_private->m_cageOperator = cageOp; // Change the last cage in the data-model in the SKGraph object. if (m_private->m_currentCageSaved) { // If new cage, skip dropping. int cageNum = g->cageCount() - 1; #ifdef MATHDOKUENTRY_LOG qCDebug(KSudokuLog) << " DROPPING CAGE" << cageNum << "m_currentCageSaved" << m_private->m_currentCageSaved << "m_cage" << m_private->m_cage; #endif g->dropCage (cageNum); } // Add a new cage or replace the previous version of the new cage. g->addCage (m_private->m_cage, m_private->m_cageOperator, m_private->m_cageValue); #ifdef MATHDOKUENTRY_LOG qCDebug(KSudokuLog) << " ADDED CAGE" << (g->cageCount() - 1) << "value" << m_private->m_cageValue << "op" << m_private->m_cageOperator << m_private->m_cage; #endif m_private->m_currentCageSaved = true; // Re-draw the boundary and label of the cage just added to the graph. // We always display the label while the cage is being keyed in. m_private->emitCageChange (g->cageCount(), true); return true; } bool Game::validCell (int pos, SKGraph * g) { // No checks of selected cell needed if it is in the current cage. if (m_private->m_cage.indexOf (pos) >= 0) { return true; } // Selected cell must not be already in another cage. for (int n = 0; n < g->cageCount(); n++) { if (g->cage(n).indexOf (pos) >= 0) { KMessageBox::information (messageParent(), i18n("The cell you have selected has already been " "used in a cage."), i18n("Error in Cage")); return false; } } // Cell must adjoin the current cage or be the first cell in it. int cageSize = m_private->m_cage.size(); if (cageSize > 0) { int ix = g->cellPosX(pos); int iy = g->cellPosY(pos); int max = g->order(); bool adjoining = false; for (int n = 0; n < cageSize; n++) { int cell = m_private->m_cage.at(n); int dx = g->cellPosX(cell) - ix; int dy = g->cellPosY(cell) - iy; if ((dy == 0) && (((ix > 0) && (dx == -1)) || ((ix < max) && (dx == 1)))) { adjoining = true; // Adjoining to left or right. break; } if ((dx == 0) && (((iy > 0) && (dy == -1)) || ((iy < max) && (dy == 1)))) { adjoining = true; // Adjoining above or below. break; } } if (! adjoining) { KMessageBox::information (messageParent(), i18n("The cell you have selected is not next to " "any cell in the cage you are creating."), i18n("Error in Cage")); return false; } } return true; } void Game::finishCurrentCage (SKGraph * g) { #ifdef MATHDOKUENTRY_LOG qCDebug(KSudokuLog) << "END CAGE: value" << m_private->m_cageValue << "op" << m_private->m_cageOperator << m_private->m_cage; #endif // If Killer Sudoku and cage-size > 1, force operator to be +. if ((g->specificType() == KillerSudoku) && (m_private->m_cage.size() > 1)) { m_private->m_cageOperator = Add; } // Validate the contents of the cage. if ((! m_private->m_currentCageSaved) || (m_private->m_cage.size() == 0)) { KMessageBox::information (messageParent(), i18n("The cage you wish to complete has no cells in it yet. " "Please click on a cell or key in + - / x or a number."), i18n("Error in Cage")); return; // Invalid - cannot finalise the cage. } else if (m_private->m_cageValue == 0) { KMessageBox::information (messageParent(), i18n("The cage you wish to complete has no value yet. " "Please key in a number with one or more digits."), i18n("Error in Cage")); return; // Invalid - cannot finalise the cage. } else if ((m_private->m_cage.size() > 1) && (m_private->m_cageOperator == NoOperator)) { KMessageBox::information (messageParent(), i18n("The cage you wish to complete has more than one cell, " "but it has no operator yet. Please key in + - / or x."), i18n("Error in Cage")); return; // Invalid - cannot finalise the cage. } else if ((m_private->m_cage.size() == 1) && (m_private->m_cageValue > g->order())) { KMessageBox::information (messageParent(), i18n("The cage you wish to complete has one cell, but its " "value is too large. A single-cell cage must have a value " "from 1 to %1 in a puzzle of this size.", g->order()), i18n("Error in Cage")); return; // Invalid - cannot finalise the cage. } // Save and display the completed cage. if (m_private->m_cage.size() == 1) { // Display digit. doEvent(HistoryEvent(m_private->m_cage.first(), CellInfo(CorrectValue, m_private->m_cageValue))); m_private->emitCellChange(m_private->m_cage.first()); m_private->emitModified(true); } // IDW TODO - Unhighlight the cage that is being entered. m_private->emitCageChange (g->cageCount(), // No label in size 1. (m_private->m_cage.size() > 1)); // Start a new cage. m_private->m_currentCageSaved = false; } void Game::deleteCageAt (int pos, SKGraph * g) { int cageNumP1 = g->cageCount(); if (cageNumP1 > 0) { // IDW TODO - Hover-hilite the cage that is to be deleted. cageNumP1 = 0; for (int n = 0; n < g->cageCount(); n++) { if (g->cage(n).indexOf (pos) >= 0) { cageNumP1 = n + 1; // This cage is to be deleted. break; } } // If the right-click was on a cage, delete it. if (cageNumP1 > 0) { if(KMessageBox::questionYesNo (messageParent(), i18n("Do you wish to delete this cage?"), i18n("Delete Cage"), KStandardGuiItem::del(), KStandardGuiItem::cancel(), QStringLiteral("CageDelConfirm")) == KMessageBox::No) { return; } if (g->cage(cageNumP1-1).size() == 1) { // Erase digit. // Delete the digit shown in a size-1 cage. doEvent(HistoryEvent(pos, CellInfo(CorrectValue, 0))); m_private->emitCellChange(pos); m_private->emitModified(true); } // Erase the cage boundary and label. m_private->emitCageChange (-cageNumP1, false); // Remove the cage from the puzzle's graph. #ifdef MATHDOKUENTRY_LOG qCDebug(KSudokuLog) << " DROP CAGE" << (cageNumP1 - 1); #endif g->dropCage (cageNumP1 - 1); if (m_private->m_cage.indexOf (pos) >= 0) { // The current cage was dropped. m_private->m_currentCageSaved = false; } } else { KMessageBox::information (messageParent(), i18n("The cell you have selected is not in any cage, " "so the Delete action will not delete anything."), i18n("Delete Cage"), QStringLiteral("CageDelMissed")); } } else { KMessageBox::information (messageParent(), i18n("The Delete action finds that there are no cages " "to delete."), i18n("Delete Cage")); #ifdef MATHDOKUENTRY_LOG qCDebug(KSudokuLog) << "NO CAGES TO DELETE."; #endif } } bool Game::allValuesSetAndUsable() const { for (int i = 0; i < size(); i++) { if (value(i) == 0) { return false; } } return true; } void Game::checkCompleted() { if(!m_private || !m_private->puzzle->hasSolution()) return; if (!allValuesSetAndUsable()) { return; } for(int i = 0; i < size(); i++) { if(value(i) != solution(i)) { m_private->emitCompleted(false, time(), m_private->hadHelp); return; } } m_private->wasFinished = true; m_private->emitCompleted(true, time(), m_private->hadHelp); } bool Game::giveHint() { if(!m_private || !m_private->puzzle->hasSolution()) return false; int moveNum = 0; int index = 0; while (true) { index = m_private->puzzle->hintIndex(moveNum); if (index < 0) { return false; // End of hint-list. } if (value(index) == 0) { break; // Hint is for a cell not yet filled. } moveNum++; } m_private->hadHelp = true; int val = solution(index); doEvent(HistoryEvent(index, CellInfo(GivenValue, val))); m_private->emitCellChange(index); m_private->emitModified(true); checkCompleted(); return true; } bool Game::autoSolve() { if(!m_private || !m_private->puzzle->hasSolution()) return false; m_private->hadHelp = true; PuzzleState newState(size(), m_private->puzzle->order()); newState.reset(); for(int i = 0; i < size(); ++i) { int val = solution(i); newState.setValue(i, val); newState.setGiven(i, true); } doEvent(HistoryEvent(newState)); m_private->emitFullChange(); m_private->emitModified(true); m_private->wasFinished = true; m_private->emitCompleted(true, time(), true); return true; } int Game::value(int index) const { if(!m_private) return 0; return m_private->state.value(index); } int Game::solution(int index) const { if(!m_private) return 0; return m_private->puzzle->solution(index); } bool Game::given(int index) const { if(!m_private) return false; return m_private->state.given(index); } bool Game::marker(int index, int val) const { if(!m_private) return false; return m_private->state.marker(index, val); } ksudoku::ButtonState Game::buttonState(int index) const { if(!m_private) return WrongValue; if(given(index)) return GivenValue; if(value(index) == 0) return Marker; if(value(index) == solution(index)) return CorrectValue; if(solution(index)) return WrongValue; return CorrectValue; } CellInfo Game::cellInfo(int index) const { if(!m_private) return CellInfo(WrongValue, 0); if(given(index)) return CellInfo(GivenValue, value(index)); if(value(index) == 0) return CellInfo(m_private->state.markers(index)); if(value(index) == solution(index)) return CellInfo(CorrectValue, value(index)); if(solution(index)) return CellInfo(WrongValue, value(index)); return CellInfo(CorrectValue, value(index)); } const BoardContents Game::allValues() const { if(!m_private) return BoardContents(); return m_private->state.allValues(); } QTime Game::time() const { if(!m_private) return QTime(); return QTime(0,0).addMSecs(msecsElapsed()); } int Game::msecsElapsed() const { if(!m_private) return 0; return (m_private->accumTime + m_private->time.elapsed()); } void Game::setTime(int msecs) const { if(!m_private) return; m_private->accumTime = msecs; m_private->time.start(); } // History void Game::doEvent(const HistoryEvent& event) { if(!m_private) return; HistoryEvent hisEvent(event); // Remove events after current history position m_private->history.erase(m_private->history.begin()+(m_private->historyPos), m_private->history.end()); // Append event hisEvent.applyTo(m_private->state); m_private->history.append(hisEvent); // always append after applying m_private->historyPos++; } int Game::historyLength() const { if(!m_private) return 0; return m_private->history.count(); } HistoryEvent Game::historyEvent(int i) const { if(!m_private || i >= m_private->history.count()) return HistoryEvent(); return m_private->history[i]; } bool Game::canUndo() const { if(!m_private) return false; return m_private->historyPos != 0; } bool Game::canRedo() const { if(!m_private) return false; return m_private->historyPos != m_private->history.count(); } bool Game::userHadHelp() const { if(!m_private) return false; return m_private->hadHelp; } bool Game::wasFinished() const { if(!m_private) return false; return m_private->wasFinished; } void Game::setUserHadHelp(bool hadHelp) { if(!m_private) return; m_private->hadHelp = hadHelp; } void Game::setMessageParent(QWidget * messageParent) { if (m_private) { m_private->m_messageParent = messageParent; } } QWidget * Game::messageParent() { return (m_private ? m_private->m_messageParent : 0); } } diff --git a/src/gui/views/ArcBall.h b/src/gui/views/ArcBall.h index 95e231f..39a7553 100644 --- a/src/gui/views/ArcBall.h +++ b/src/gui/views/ArcBall.h @@ -1,489 +1,488 @@ /** KempoApi: The Turloc Toolkit *****************************/ /** * * **/ /** ** ** Filename: ArcBall.h **/ /** ** Version: Common **/ /** ** **/ /** **/ /** Arcball class for mouse manipulation. **/ /** **/ /** **/ /** **/ /** **/ /** (C) 1999-2003 Tatewake.com **/ /** History: **/ /** 08/17/2003 - (TJG) - Creation **/ /** 09/23/2003 - (TJG) - Bug fix and optimization **/ /** 09/25/2003 - (TJG) - Version for NeHe Basecode users **/ /** **/ /*************************************************************/ #ifndef _ArcBall_h #define _ArcBall_h #include "math.h" // Needed for sqrtf // 8<--Snip here if you have your own math types/funcs-->8 //Only support assertions in debug builds #ifdef _DEBUG # include "assert.h" #else # define assert(x) { } #endif -#include #ifdef Q_OS_MAC #include #include #elif defined(Q_WS_WIN) #include #include // Header File For The OpenGL32 Library #include // Header File For The GLu32 Library #else #include // Header File For The OpenGL32 Library #include // Header File For The GLu32 Library #endif //Math types derived from the KempoApi tMath library typedef union Tuple2f_t { struct { GLfloat X, Y; } s; GLfloat T[2]; } Tuple2fT; //A generic 2-element tuple that is represented by single-precision floating point x,y coordinates. typedef union Tuple3f_t { struct { GLfloat X, Y, Z; } s; GLfloat T[3]; } Tuple3fT; //A generic 3-element tuple that is represented by single precision-floating point x,y,z coordinates. typedef union Tuple4f_t { struct { GLfloat X, Y, Z, W; } s; GLfloat T[4]; } Tuple4fT; //A 4-element tuple represented by single-precision floating point x,y,z,w coordinates. typedef union Matrix3f_t { struct { //column major union { GLfloat M00; GLfloat XX; GLfloat SX; }; //XAxis.X and Scale X union { GLfloat M10; GLfloat XY; }; //XAxis.Y union { GLfloat M20; GLfloat XZ; }; //XAxis.Z union { GLfloat M01; GLfloat YX; }; //YAxis.X union { GLfloat M11; GLfloat YY; GLfloat SY; }; //YAxis.Y and Scale Y union { GLfloat M21; GLfloat YZ; }; //YAxis.Z union { GLfloat M02; GLfloat ZX; }; //ZAxis.X union { GLfloat M12; GLfloat ZY; }; //ZAxis.Y union { GLfloat M22; GLfloat ZZ; GLfloat SZ; }; //ZAxis.Z and Scale Z } s; GLfloat M[9]; } Matrix3fT; //A single precision floating point 3 by 3 matrix. typedef union Matrix4f_t { struct { //column major union { GLfloat M00; GLfloat XX; GLfloat SX; }; //XAxis.X and Scale X union { GLfloat M10; GLfloat XY; }; //XAxis.Y union { GLfloat M20; GLfloat XZ; }; //XAxis.Z union { GLfloat M30; GLfloat XW; }; //XAxis.W union { GLfloat M01; GLfloat YX; }; //YAxis.X union { GLfloat M11; GLfloat YY; GLfloat SY; }; //YAxis.Y and Scale Y union { GLfloat M21; GLfloat YZ; }; //YAxis.Z union { GLfloat M31; GLfloat YW; }; //YAxis.W union { GLfloat M02; GLfloat ZX; }; //ZAxis.X union { GLfloat M12; GLfloat ZY; }; //ZAxis.Y union { GLfloat M22; GLfloat ZZ; GLfloat SZ; }; //ZAxis.Z and Scale Z union { GLfloat M32; GLfloat ZW; }; //ZAxis.W union { GLfloat M03; GLfloat TX; }; //Trans.X union { GLfloat M13; GLfloat TY; }; //Trans.Y union { GLfloat M23; GLfloat TZ; }; //Trans.Z union { GLfloat M33; GLfloat TW; GLfloat SW; }; //Trans.W and Scale W } s; GLfloat M[16]; } Matrix4fT; //A single precision floating point 4 by 4 matrix. //"Inherited" types #define Point2fT Tuple2fT //A 2 element point that is represented by single precision floating point x,y coordinates. #define Quat4fT Tuple4fT //A 4 element unit quaternion represented by single precision floating point x,y,z,w coordinates. #define Vector2fT Tuple2fT //A 2-element vector that is represented by single-precision floating point x,y coordinates. #define Vector3fT Tuple3fT //A 3-element vector that is represented by single-precision floating point x,y,z coordinates. //Custom math, or speed overrides #define FuncSqrt sqrtf //utility macros //assuming IEEE-754(GLfloat), which i believe has max precision of 7 bits # define Epsilon 1.0e-5 //Math functions /** * Sets the value of this tuple to the vector sum of itself and tuple t1. * @param t1 the other tuple */ inline static void Point2fAdd(Point2fT* NewObj, const Tuple2fT* t1) { assert(NewObj && t1); NewObj->s.X += t1->s.X; NewObj->s.Y += t1->s.Y; } /** * Sets the value of this tuple to the vector difference of itself and tuple t1 (this = this - t1). * @param t1 the other tuple */ inline static void Point2fSub(Point2fT* NewObj, const Tuple2fT* t1) { assert(NewObj && t1); NewObj->s.X -= t1->s.X; NewObj->s.Y -= t1->s.Y; } /** * Sets this vector to be the vector cross product of vectors v1 and v2. * @param v1 the first vector * @param v2 the second vector */ inline static void Vector3fCross(Vector3fT* NewObj, const Vector3fT* v1, const Vector3fT* v2) { Vector3fT Result; //safe not to initialize assert(NewObj && v1 && v2); // store on stack once for aliasing-safty // i.e. safe when a.cross(a, b) Result.s.X = (v1->s.Y * v2->s.Z) - (v1->s.Z * v2->s.Y); Result.s.Y = (v1->s.Z * v2->s.X) - (v1->s.X * v2->s.Z); Result.s.Z = (v1->s.X * v2->s.Y) - (v1->s.Y * v2->s.X); //copy result back *NewObj = Result; } /** * Computes the dot product of the this vector and vector v1. * @param v1 the other vector */ inline static GLfloat Vector3fDot(const Vector3fT* NewObj, const Vector3fT* v1) { assert(NewObj && v1); return (NewObj->s.X * v1->s.X) + (NewObj->s.Y * v1->s.Y) + (NewObj->s.Z * v1->s.Z); } /** * Returns the squared length of this vector. * @return the squared length of this vector */ inline static GLfloat Vector3fLengthSquared(const Vector3fT* NewObj) { assert(NewObj); return (NewObj->s.X * NewObj->s.X) + (NewObj->s.Y * NewObj->s.Y) + (NewObj->s.Z * NewObj->s.Z); } /** * Returns the length of this vector. * @return the length of this vector */ inline static GLfloat Vector3fLength(const Vector3fT* NewObj) { assert(NewObj); return FuncSqrt(Vector3fLengthSquared(NewObj)); } inline static void Matrix3fSetZero(Matrix3fT* NewObj) { NewObj->s.M00 = NewObj->s.M01 = NewObj->s.M02 = NewObj->s.M10 = NewObj->s.M11 = NewObj->s.M12 = NewObj->s.M20 = NewObj->s.M21 = NewObj->s.M22 = 0.0f; } /** * Sets this Matrix3 to identity. */ inline static void Matrix3fSetIdentity(Matrix3fT* NewObj) { Matrix3fSetZero(NewObj); //then set diagonal as 1 NewObj->s.M00 = NewObj->s.M11 = NewObj->s.M22 = 1.0f; } /** * Sets the value of this matrix to the matrix conversion of the * quaternion argument. * @param q1 the quaternion to be converted */ //$hack this can be optimized some(if s == 0) inline static void Matrix3fSetRotationFromQuat4f(Matrix3fT* NewObj, const Quat4fT* q1) { GLfloat n, s; GLfloat xs, ys, zs; GLfloat wx, wy, wz; GLfloat xx, xy, xz; GLfloat yy, yz, zz; assert(NewObj && q1); n = (q1->s.X * q1->s.X) + (q1->s.Y * q1->s.Y) + (q1->s.Z * q1->s.Z) + (q1->s.W * q1->s.W); s = (n > 0.0f) ? (2.0f / n) : 0.0f; xs = q1->s.X * s; ys = q1->s.Y * s; zs = q1->s.Z * s; wx = q1->s.W * xs; wy = q1->s.W * ys; wz = q1->s.W * zs; xx = q1->s.X * xs; xy = q1->s.X * ys; xz = q1->s.X * zs; yy = q1->s.Y * ys; yz = q1->s.Y * zs; zz = q1->s.Z * zs; NewObj->s.XX = 1.0f - (yy + zz); NewObj->s.YX = xy - wz; NewObj->s.ZX = xz + wy; NewObj->s.XY = xy + wz; NewObj->s.YY = 1.0f - (xx + zz); NewObj->s.ZY = yz - wx; NewObj->s.XZ = xz - wy; NewObj->s.YZ = yz + wx; NewObj->s.ZZ = 1.0f - (xx + yy); } /** * Sets the value of this matrix to the result of multiplying itself * with matrix m1. * @param m1 the other matrix */ inline static void Matrix3fMulMatrix3f(Matrix3fT* NewObj, const Matrix3fT* m1) { Matrix3fT Result; //safe not to initialize assert(NewObj && m1); // alias-safe way. Result.s.M00 = (NewObj->s.M00 * m1->s.M00) + (NewObj->s.M01 * m1->s.M10) + (NewObj->s.M02 * m1->s.M20); Result.s.M01 = (NewObj->s.M00 * m1->s.M01) + (NewObj->s.M01 * m1->s.M11) + (NewObj->s.M02 * m1->s.M21); Result.s.M02 = (NewObj->s.M00 * m1->s.M02) + (NewObj->s.M01 * m1->s.M12) + (NewObj->s.M02 * m1->s.M22); Result.s.M10 = (NewObj->s.M10 * m1->s.M00) + (NewObj->s.M11 * m1->s.M10) + (NewObj->s.M12 * m1->s.M20); Result.s.M11 = (NewObj->s.M10 * m1->s.M01) + (NewObj->s.M11 * m1->s.M11) + (NewObj->s.M12 * m1->s.M21); Result.s.M12 = (NewObj->s.M10 * m1->s.M02) + (NewObj->s.M11 * m1->s.M12) + (NewObj->s.M12 * m1->s.M22); Result.s.M20 = (NewObj->s.M20 * m1->s.M00) + (NewObj->s.M21 * m1->s.M10) + (NewObj->s.M22 * m1->s.M20); Result.s.M21 = (NewObj->s.M20 * m1->s.M01) + (NewObj->s.M21 * m1->s.M11) + (NewObj->s.M22 * m1->s.M21); Result.s.M22 = (NewObj->s.M20 * m1->s.M02) + (NewObj->s.M21 * m1->s.M12) + (NewObj->s.M22 * m1->s.M22); //copy result back to this *NewObj = Result; } inline static void Matrix4fSetRotationScaleFromMatrix4f(Matrix4fT* NewObj, const Matrix4fT* m1) { assert(NewObj && m1); NewObj->s.XX = m1->s.XX; NewObj->s.YX = m1->s.YX; NewObj->s.ZX = m1->s.ZX; NewObj->s.XY = m1->s.XY; NewObj->s.YY = m1->s.YY; NewObj->s.ZY = m1->s.ZY; NewObj->s.XZ = m1->s.XZ; NewObj->s.YZ = m1->s.YZ; NewObj->s.ZZ = m1->s.ZZ; } /** * Performs SVD on this matrix and gets scale and rotation. * Rotation is placed into rot3, and rot4. * @param rot3 the rotation factor(Matrix3d). if null, ignored * @param rot4 the rotation factor(Matrix4) only upper 3x3 elements are changed. if null, ignored * @return scale factor */ inline static GLfloat Matrix4fSVD(const Matrix4fT* NewObj, Matrix3fT* rot3, Matrix4fT* rot4) { GLfloat s, n; assert(NewObj); // this is a simple svd. // Not complete but fast and reasonable. // See comment in Matrix3d. s = FuncSqrt( ( (NewObj->s.XX * NewObj->s.XX) + (NewObj->s.XY * NewObj->s.XY) + (NewObj->s.XZ * NewObj->s.XZ) + (NewObj->s.YX * NewObj->s.YX) + (NewObj->s.YY * NewObj->s.YY) + (NewObj->s.YZ * NewObj->s.YZ) + (NewObj->s.ZX * NewObj->s.ZX) + (NewObj->s.ZY * NewObj->s.ZY) + (NewObj->s.ZZ * NewObj->s.ZZ) ) / 3.0f ); if (rot3) //if pointer not null { //this->getRotationScale(rot3); rot3->s.XX = NewObj->s.XX; rot3->s.XY = NewObj->s.XY; rot3->s.XZ = NewObj->s.XZ; rot3->s.YX = NewObj->s.YX; rot3->s.YY = NewObj->s.YY; rot3->s.YZ = NewObj->s.YZ; rot3->s.ZX = NewObj->s.ZX; rot3->s.ZY = NewObj->s.ZY; rot3->s.ZZ = NewObj->s.ZZ; // zero-div may occur. n = 1.0f / FuncSqrt( (NewObj->s.XX * NewObj->s.XX) + (NewObj->s.XY * NewObj->s.XY) + (NewObj->s.XZ * NewObj->s.XZ) ); rot3->s.XX *= n; rot3->s.XY *= n; rot3->s.XZ *= n; n = 1.0f / FuncSqrt( (NewObj->s.YX * NewObj->s.YX) + (NewObj->s.YY * NewObj->s.YY) + (NewObj->s.YZ * NewObj->s.YZ) ); rot3->s.YX *= n; rot3->s.YY *= n; rot3->s.YZ *= n; n = 1.0f / FuncSqrt( (NewObj->s.ZX * NewObj->s.ZX) + (NewObj->s.ZY * NewObj->s.ZY) + (NewObj->s.ZZ * NewObj->s.ZZ) ); rot3->s.ZX *= n; rot3->s.ZY *= n; rot3->s.ZZ *= n; } if (rot4) //if pointer not null { if (rot4 != NewObj) { Matrix4fSetRotationScaleFromMatrix4f(rot4, NewObj); // private method } // zero-div may occur. n = 1.0f / FuncSqrt( (NewObj->s.XX * NewObj->s.XX) + (NewObj->s.XY * NewObj->s.XY) + (NewObj->s.XZ * NewObj->s.XZ) ); rot4->s.XX *= n; rot4->s.XY *= n; rot4->s.XZ *= n; n = 1.0f / FuncSqrt( (NewObj->s.YX * NewObj->s.YX) + (NewObj->s.YY * NewObj->s.YY) + (NewObj->s.YZ * NewObj->s.YZ) ); rot4->s.YX *= n; rot4->s.YY *= n; rot4->s.YZ *= n; n = 1.0f / FuncSqrt( (NewObj->s.ZX * NewObj->s.ZX) + (NewObj->s.ZY * NewObj->s.ZY) + (NewObj->s.ZZ * NewObj->s.ZZ) ); rot4->s.ZX *= n; rot4->s.ZY *= n; rot4->s.ZZ *= n; } return s; } inline static void Matrix4fSetRotationScaleFromMatrix3f(Matrix4fT* NewObj, const Matrix3fT* m1) { assert(NewObj && m1); NewObj->s.XX = m1->s.XX; NewObj->s.YX = m1->s.YX; NewObj->s.ZX = m1->s.ZX; NewObj->s.XY = m1->s.XY; NewObj->s.YY = m1->s.YY; NewObj->s.ZY = m1->s.ZY; NewObj->s.XZ = m1->s.XZ; NewObj->s.YZ = m1->s.YZ; NewObj->s.ZZ = m1->s.ZZ; } inline static void Matrix4fMulRotationScale(Matrix4fT* NewObj, GLfloat scale) { assert(NewObj); NewObj->s.XX *= scale; NewObj->s.YX *= scale; NewObj->s.ZX *= scale; NewObj->s.XY *= scale; NewObj->s.YY *= scale; NewObj->s.ZY *= scale; NewObj->s.XZ *= scale; NewObj->s.YZ *= scale; NewObj->s.ZZ *= scale; } /** * Sets the rotational component (upper 3x3) of this matrix to the matrix * values in the T precision Matrix3d argument; the other elements of * this matrix are unchanged; a singular value decomposition is performed * on this object's upper 3x3 matrix to factor out the scale, then this * object's upper 3x3 matrix components are replaced by the passed rotation * components, and then the scale is reapplied to the rotational * components. * @param m1 T precision 3x3 matrix */ inline static void Matrix4fSetRotationFromMatrix3f(Matrix4fT* NewObj, const Matrix3fT* m1) { GLfloat scale; assert(NewObj && m1); scale = Matrix4fSVD(NewObj, NULL, NULL); Matrix4fSetRotationScaleFromMatrix3f(NewObj, m1); Matrix4fMulRotationScale(NewObj, scale); } // 8<--Snip here if you have your own math types/funcs-->8 typedef class ArcBall_t { protected: inline void _mapToSphere(const Point2fT* NewPt, Vector3fT* NewVec) const; public: //Create/Destroy ArcBall_t(GLfloat NewWidth, GLfloat NewHeight); ~ArcBall_t() { /* nothing to do */ } //Set new bounds inline void setBounds(GLfloat NewWidth, GLfloat NewHeight) { assert((NewWidth > 1.0f) && (NewHeight > 1.0f)); //Set adjustment factor for width/height this->AdjustWidth = 1.0f / ((NewWidth - 1.0f) * 0.5f); this->AdjustHeight = 1.0f / ((NewHeight - 1.0f) * 0.5f); } //Mouse down void click(const Point2fT* NewPt); //Mouse drag, calculate rotation void drag(const Point2fT* NewPt, Quat4fT* NewRot); protected: Vector3fT StVec; //Saved click vector Vector3fT EnVec; //Saved drag vector GLfloat AdjustWidth; //Mouse bounds width GLfloat AdjustHeight; //Mouse bounds height } ArcBallT; #endif diff --git a/src/gui/views/ksview.cpp b/src/gui/views/ksview.cpp index 30c0e20..9d56060 100644 --- a/src/gui/views/ksview.cpp +++ b/src/gui/views/ksview.cpp @@ -1,128 +1,126 @@ /*************************************************************************** * Copyright 2007 Francesco Rossi * * Copyright 2006-2007 Mick Kappenburg * * Copyright 2006-2008 Johannes Bergmeier * * Copyright 2012 Ian Wadham * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "ksview.h" #include "ksudokugame.h" #include "settings.h" -#include -#include #include "puzzle.h" #ifdef OPENGL_SUPPORT #include "roxdokuview.h" #endif #include "view2d.h" namespace ksudoku{ KsView::KsView(const Game& game, GameActions* gameActions, QObject* parent) : QObject(parent), m_game(game), m_gameActions(gameActions), m_viewWidget(0) { m_symbolTable = 0; m_currentValue = 1; m_valueListWidget = 0; } KsView::~KsView() { delete m_viewWidget; } void KsView::createView() { GameType type = m_game.puzzle()->gameType(); switch(type) { case TypeSudoku: { setWidget(new View2D(0, m_game, m_gameActions)); break; } case TypeCustom: { #ifdef OPENGL_SUPPORT if(m_game.puzzle()->graph()->sizeZ() > 1) { // TODO - IDW - Add a parent widget. Memory leak? setWidget(new RoxdokuView(m_game, m_gameActions, 0)); } else { setWidget(new View2D(0, m_game, m_gameActions)); } #else setWidget(new View2D(0, m_game, m_gameActions)); #endif break; } #ifdef OPENGL_SUPPORT case TypeRoxdoku: { // TODO - IDW - Add a parent widget. Memory leak? setWidget(new RoxdokuView(m_game, m_gameActions, 0)); break; } #endif default: // TODO this will not work break; } QObject* view = m_view->widget(); connect(view, SIGNAL(valueSelected(int)), SLOT(selectValue(int))); connect(this, SIGNAL(valueSelected(int)), view, SLOT(selectValue(int))); connect(parent(), SIGNAL(settingsChanged()), view, SLOT(settingsChanged())); settingsChanged(); } void KsView::selectValue(int value) { if(value == m_currentValue) return; m_currentValue = value; emit valueSelected(value); } SymbolTable* KsView::symbolTable() const { return m_symbolTable; } void KsView::setSymbolTable(SymbolTable* table) { m_symbolTable = table; emit symbolsChanged(table); } void KsView::setWidget(QWidget* widget) { m_viewWidget = widget; emit flagsChanged(m_flags); emit symbolsChanged(m_symbolTable); m_view = dynamic_cast(widget); } void KsView::settingsChanged() { ViewFlags flags; if(Settings::showErrors()) flags |= ShowErrors; if(Settings::showHighlights()) flags |= ShowHighlights; setFlags(flags); } } diff --git a/src/gui/views/renderer.cpp b/src/gui/views/renderer.cpp index c4e5bf8..19967d8 100644 --- a/src/gui/views/renderer.cpp +++ b/src/gui/views/renderer.cpp @@ -1,427 +1,426 @@ /*************************************************************************** * Copyright 2008 Johannes Bergmeier * * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "renderer.h" #include "ksudoku_logging.h" -#include #include #include #include #define USE_UNSTABLE_LIBKDEGAMESPRIVATE_API #include #include "settings.h" namespace ksudoku { Renderer* Renderer::instance() { static Renderer instance; return &instance; } Renderer::Renderer() { m_renderer = new QSvgRenderer(); m_cache = new KImageCache(QStringLiteral("ksudoku-cache"), 3*1024); m_mathdokuStyle = false; if(!loadTheme(Settings::theme())) qCDebug(KSudokuLog) << "Failed to load any game theme!"; } Renderer::~Renderer() { delete m_cache; delete m_renderer; } bool Renderer::loadTheme(const QString& themeName) { bool discardCache = !m_currentTheme.isEmpty(); if(!m_currentTheme.isEmpty() && m_currentTheme == themeName) { qCDebug(KSudokuLog) << "Notice: loading the same theme"; return true; // this is not an error } m_currentTheme = themeName; KGameTheme theme; if(themeName.isEmpty() || !theme.load(themeName)) { qCDebug(KSudokuLog) << "Failed to load theme" << Settings::theme(); qCDebug(KSudokuLog) << "Trying to load default"; if(!theme.loadDefault()) return false; discardCache = true; m_currentTheme = "default"; } bool res = m_renderer->load(theme.graphics()); qCDebug(KSudokuLog) << "loading" << theme.graphics(); if(!res) return false; if(discardCache) { qCDebug(KSudokuLog) << "discarding cache"; m_cache->clear(); } fillNameHashes(); return true; } void Renderer::fillNameHashes() { m_borderNames = QVector(); m_borderNames << ""; m_borderNames << "1"; m_borderNames << "2"; m_borderNames << "12"; m_borderNames << "3"; m_borderNames << "13"; m_borderNames << "23"; m_borderNames << "123"; m_borderNames << "4"; m_borderNames << "14"; m_borderNames << "24"; m_borderNames << "124"; m_borderNames << "34"; m_borderNames << "134"; m_borderNames << "234"; m_borderNames << "1234"; m_borderTypes << QString(); m_borderTypes << "row"; m_borderTypes << "column"; m_borderTypes << "block"; m_borderTypes << "special"; m_borderTypes << "block"; // Use block-type borders for cages. m_borderTypes << "special"; m_borderTypes << "special"; m_borderTypes << QString(); m_borderTypes << "row_h"; m_borderTypes << "column_h"; m_borderTypes << "block_h"; m_borderTypes << "special_h"; m_borderTypes << "block_h"; // Use block-type borders for cages. m_borderTypes << "special_h"; m_borderTypes << "special_h"; m_specialNames << "cell"; m_specialNames << "cell_preset"; m_specialNames << "cell"; m_specialNames << "cell_mistake"; m_specialNames << "cursor"; m_specialNames << "valuelist_item"; m_specialNames << "valuelist_selector"; m_special3dNames << "cell3d"; m_special3dNames << "cell3d_preset"; m_special3dNames << "cell3d"; m_special3dNames << "cell3d_mistake"; m_special3dNames << "cursor"; m_special3dNames << "valuelist_item"; m_special3dNames << "valuelist_selector"; // TODO get this hardcoded values from the SVG file // m_markerName << "markers9" << "markers9" //... } QPixmap Renderer::renderBackground(const QSize& size) const { if(!m_renderer->isValid() || size.isEmpty()) return QPixmap(); QPixmap pix; QString cacheName = QString("background_%1x%2").arg(size.width()).arg(size.height()); if(!m_cache->findPixmap(cacheName, &pix)) { pix = QPixmap(size); pix.fill(Qt::transparent); QPainter p(&pix); m_renderer->render(&p, "background"); p.end(); m_cache->insertPixmap(cacheName, pix); } return pix; } /** Moves a point from its relative position to the base rect (0,0,1,1) to a relative position to rect @p to */ QPointF fromBasetoRect(const QPointF& p, const QRectF& to) { return QPointF(p.x()*to.width()+to.left(), p.y()*to.height()+to.top()); } /** Moves a point from its relative position to rect @p from to a relative position to the base rect (0,0,1,1) */ QPointF fromRectToBase(const QRectF& p, const QRectF& from) { return QPointF((p.x()-from.left())/from.width(), (p.y()-from.top())/from.height()); } /** Moves a point from its relative position to rect @p from to a relative position to rect @p to */ QPointF fromRectToRect(const QPointF& p, const QRectF& from, const QRectF& to) { return QPointF((p.x()-from.left())*to.width()/from.width()+to.left(), (p.y()-from.top())*to.height()/from.height()+to.top()); } QPixmap Renderer::renderSpecial(SpecialType type, int size) const { if(!m_renderer->isValid() || size == 0) return QPixmap(); //only show the errors if the option has been set if(!Settings::showErrors() && type == SpecialCellMistake ) type = SpecialCell; QString cacheName = QString("special_%1_%2").arg(m_specialNames[type]).arg(size); QPixmap pix; if(!m_cache->findPixmap(cacheName, &pix)) { pix = QPixmap(size, size); pix.fill(Qt::transparent); QPainter p(&pix); // NOTE fix for Qt's QSvgRenderer size reporting bug QRectF r(m_renderer->boundsOnElement(m_specialNames[type])); QRectF from(r.adjusted(+0.5,+0.5,-0.5,-0.5)); QRectF to(QRectF(0,0,size,size)); r.setTopLeft(fromRectToRect(r.topLeft(), from, to)); r.setBottomRight(fromRectToRect(r.bottomRight(), from, to)); m_renderer->render(&p, m_specialNames[type], r); p.end(); m_cache->insertPixmap(cacheName, pix); } return pix; } QPixmap Renderer::renderSymbol(int symbol, int size, int max, SymbolType type) const { if(!m_renderer->isValid() || size == 0) return QPixmap(); QString set; if(max <= 9) { set = "symbol"; } else { set = "symbol25"; } QString cacheName = QString("%1_%2_%3_%4").arg(set).arg(symbol).arg(size).arg(type); QPixmap pix; if(!m_cache->findPixmap(cacheName, &pix)) { pix = QPixmap(size, size); pix.fill(Qt::transparent); QPainter p(&pix); // NOTE fix for Qt's QSvgRenderer size reporting bug QRectF r(m_renderer->boundsOnElement("symbol_1")); QRectF from(m_renderer->boundsOnElement("cell_symbol")); from.adjust(+0.5,+0.5,-0.5,-0.5); // << this is the fix QRectF to(QRectF(0,0,size,size)); r.setTopLeft(fromRectToRect(r.topLeft(), from, to)); r.setBottomRight(fromRectToRect(r.bottomRight(), from, to)); switch(type) { case SymbolPreset: if(m_renderer->elementExists(QString("%1_%2_preset").arg(set).arg(symbol))) { m_renderer->render(&p, QString("%1_%2_preset").arg(set).arg(symbol), r); } else { m_renderer->render(&p, QString("%1_%2").arg(set).arg(symbol), r); } break; case SymbolEdited: if(m_renderer->elementExists(QString("%1_%2_edited").arg(set).arg(symbol))) { m_renderer->render(&p, QString("%1_%2_edited").arg(set).arg(symbol), r); } else { m_renderer->render(&p, QString("%1_%2").arg(set).arg(symbol), r); } break; } p.end(); m_cache->insertPixmap(cacheName, pix); } return pix; } QPixmap Renderer::renderSymbolOn(QPixmap pixmap, int symbol, int color, int max, SymbolType type) const { // We use a smaller size of symbol in Mathdoku and Killer // Sudoku, to allow space for the cage labels. int size = m_mathdokuStyle ? (pixmap.width()+1)*3/4 : pixmap.width(); int offset = m_mathdokuStyle ? (pixmap.width()+7)/8 : 0; QPixmap symbolPixmap = renderSymbol(symbol, size, max, type); if(color) { // TODO this does not work, need some other way, maybe hardcode color into NumberType QPainter p(&symbolPixmap); p.setCompositionMode(QPainter::CompositionMode_Multiply); p.setBrush(QBrush(QColor(128,128,128,255))); p.drawRect(0, 0, size, size); p.setCompositionMode(QPainter::CompositionMode_DestinationOver); p.drawPixmap(0, 0, pixmap); p.end(); return symbolPixmap; } else { QPainter p(&pixmap); p.drawPixmap(offset, offset, symbolPixmap); p.end(); return pixmap; } } QPixmap Renderer::renderMarker(int symbol, int range, int size) const { if(!m_renderer->isValid() || size == 0) return QPixmap(); QString set; if(range <= 9) { set = "symbol"; } else { set = "symbol25"; } // TODO this is a hardcoded list of possible marker-groupings // replace it with a test for possible markers if(range <= 9) { range = 9; } else if(range <= 16) { range = 16; } else { range = 25; } QString groupName = QString("markers%1").arg(range); QString cacheName = QString("%1_%2_%3").arg(groupName).arg(symbol).arg(size); QPixmap pix; if(!m_cache->findPixmap(cacheName, &pix)) { pix = QPixmap(size, size); pix.fill(Qt::transparent); QPainter p(&pix); // NOTE fix for Qt's QSvgRenderer size reporting bug QRectF r(m_renderer->boundsOnElement(QString("%1_%2").arg(groupName).arg(symbol))); QRectF from(m_renderer->boundsOnElement(QString("cell_%1").arg(groupName))); from.adjust(+0.5,+0.5,-0.5,-0.5); // << this is the fix QRectF to(QRectF(0,0,size,size)); r.setTopLeft(fromRectToRect(r.topLeft(), from, to)); r.setBottomRight(fromRectToRect(r.bottomRight(), from, to)); m_renderer->render(&p, QString("%1_%2").arg(set).arg(symbol), r); p.end(); m_cache->insertPixmap(cacheName, pix); } return pix; } QPixmap Renderer::renderMarkerOn(QPixmap pixmap, int symbol, int range, int color) const { // TODO maybe it would be good to directly integrate the renderMarker implementation and // make renderMarker be based on this method. (same for renderSymbol and renderSymbolOn) // We use a smaller size of marker in Mathdoku and Killer // Sudoku, to allow space for the cage labels. int size = m_mathdokuStyle ? (pixmap.width()+1)*3/4 : pixmap.width(); QPixmap symbolPixmap = renderMarker(symbol, range, size); if(color) { QPainter p(&symbolPixmap); p.setCompositionMode(QPainter::CompositionMode_Multiply); p.setBrush(QBrush(QColor(128,128,128,255))); p.drawRect(0, 0, size, size); p.setCompositionMode(QPainter::CompositionMode_DestinationOver); p.drawPixmap(0, 0, pixmap); p.end(); return symbolPixmap; } else { QPainter p(&pixmap); // Offset the marker from 0,0 in Mathdoku and Killer Sudoku. int offset = m_mathdokuStyle ? (size + 7)/8 : 0; p.drawPixmap(offset, 2*offset, symbolPixmap); p.end(); return pixmap; } } QPixmap Renderer::renderCageLabelOn(QPixmap pixmap, const QString & cageLabel) { // TODO - Do font setup once during resize? Put 0+-x/ in themes? int size = pixmap.width(); QPainter p(&pixmap); p.setPen(QString("white")); // Text is white on a dark rectangle. p.setBrush(Qt::SolidPattern); // Cage label uses top 1/4 of pixmap and text is 1/6 height of pixmap. QFont f = p.font(); f.setBold(true); f.setPixelSize((size+5)/6); p.setFont(f); QFontMetrics fm(f); int w = fm.boundingRect(cageLabel).width(); // Width of text. int h = fm.height(); // Total height of font. int a = fm.ascent(); // Height from baseline of font. int m = fm.boundingRect(QChar('1')).width()/2; // Left-right margin = 1/2 width of '1'. // Paint background rect: text must be visible in light and dark themes. p.fillRect(size/6 - m, (size + 3)/4 - a, w + 2*m, h, Qt::darkGray); // Note: Origin of text is on baseline to left of first character. p.drawText(size/6, (size+3)/4, cageLabel); p.end(); return pixmap; } QPixmap Renderer::renderBorder(int border, GroupTypes type, int size) const { if(!m_renderer->isValid() || size == 0) return QPixmap(); QString cacheName = QString("contour_%1_%2_%3").arg(m_borderTypes[type]).arg(m_borderNames[border]).arg(size); QPixmap pix; if(!m_cache->findPixmap(cacheName, &pix)) { pix = QPixmap(size, size); pix.fill(Qt::transparent); QPainter p(&pix); // NOTE fix for Qt's QSvgRenderer size reporting bug QRectF r(m_renderer->boundsOnElement(QString("%1_%2").arg(m_borderTypes[type]).arg(m_borderNames[border]))); QRectF from(r.adjusted(+0.5,+0.5,-0.5,-0.5)); QRectF to(QRectF(0,0,size,size)); r.setTopLeft(fromRectToRect(r.topLeft(), from, to)); r.setBottomRight(fromRectToRect(r.bottomRight(), from, to)); m_renderer->render(&p, QString("%1_%2").arg(m_borderTypes[type]).arg(m_borderNames[border]), r); p.end(); m_cache->insertPixmap(cacheName, pix); } return pix; } QPixmap Renderer::renderSpecial3D(SpecialType type, int size) const { if(!m_renderer->isValid() || size == 0) return QPixmap(); QString cacheName = QString("special_%1_%2").arg(m_special3dNames[type]).arg(size); QPixmap pix; if(!m_cache->findPixmap(cacheName, &pix)) { pix = QPixmap(size, size); pix.fill(Qt::transparent); QPainter p(&pix); // NOTE fix for Qt's QSvgRenderer size reporting bug QRectF r(m_renderer->boundsOnElement(m_special3dNames[type])); QRectF from(r.adjusted(+0.5,+0.5,-0.5,-0.5)); QRectF to(QRectF(0,0,size,size)); r.setTopLeft(fromRectToRect(r.topLeft(), from, to)); r.setBottomRight(fromRectToRect(r.bottomRight(), from, to)); m_renderer->render(&p, m_special3dNames[type], r); p.end(); m_cache->insertPixmap(cacheName, pix); } return pix; } } diff --git a/src/gui/views/roxdokuview.h b/src/gui/views/roxdokuview.h index ec5d094..b020ec4 100644 --- a/src/gui/views/roxdokuview.h +++ b/src/gui/views/roxdokuview.h @@ -1,138 +1,135 @@ /*************************************************************************** * Copyright 2005-2007 Francesco Rossi * * Copyright 2006-2007 Mick Kappenburg * * Copyright 2006-2008 Johannes Bergmeier * * Copyright 2012 Ian Wadham * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #ifndef ROXDOKUVIEW_h #define ROXDOKUVIEW_h #include -#include #include -#include -#include #include #include #include "ArcBall.h" #include "ksudokugame.h" #include "ksview.h" class SKGraph; namespace ksudoku{ class Game; class GameActions; /** * GUI for a Roxdoku puzzle. */ class RoxdokuView : public QGLWidget, public ViewInterface { Q_OBJECT public: RoxdokuView(const ksudoku::Game &game, GameActions * gameActions, QWidget * parent = 0); ~RoxdokuView(); virtual QString status() const; void initializeGL() override; void resizeGL(int w, int h ) override; QWidget* widget() override { return this; } public slots: void selectValue(int value) override; void settingsChanged(); void enterValue(int value); signals: void valueSelected(int value); // Never used but connected to protected: void paintGL() override; void myDrawCube(bool highlight, int cell, GLfloat x, GLfloat y, GLfloat z, bool outside); void Selection(int mouse_x, int mouse_y); void mouseReleaseEvent ( QMouseEvent * e )override { if(e->button() == Qt::LeftButton) m_isClicked = false; } void mousePressEvent ( QMouseEvent * e )override { if(e->button() == Qt::LeftButton) m_isClicked = true; } void mouseMoveEvent(QMouseEvent* e) override; void mouseDoubleClickEvent(QMouseEvent* e) override; void wheelEvent (QWheelEvent* e)override { m_wheelmove += e->angleDelta().y() * .02; updateGL(); } private slots: void delayOver(); private: void loadSettings(); Game m_game; SKGraph * m_graph; int m_base; int m_order; int m_size; int m_width; int m_height; int m_depth; char m_selected_number; ArcBallT * m_arcBall; bool m_isClicked; bool m_isRClicked; bool m_isDragging; int m_selection; int m_lastSelection; QVector m_highlights; float m_dist; float m_wheelmove; GLuint m_texture[2][26]; bool m_guidedMode; bool m_showHighlights; float m_selectionSize; float m_highlightedSize; float m_unhighlightedSize; float m_outerCellSize; bool m_darkenOuterCells; QTimer * m_delayTimer; bool m_timeDelay; }; } #endif diff --git a/src/gui/views/view2d.cpp b/src/gui/views/view2d.cpp index 6936b1e..7f4b86c 100644 --- a/src/gui/views/view2d.cpp +++ b/src/gui/views/view2d.cpp @@ -1,805 +1,804 @@ /*************************************************************************** * Copyright 2008 Johannes Bergmeier * * Copyright 2015 Ian Wadham #include #include #include "puzzle.h" #include "gameactions.h" #include "settings.h" namespace ksudoku { struct ColoredValue { ColoredValue() : value(0), color(0) { } ColoredValue(int v, int c) : value(v), color(c) { } int value; int color; }; class CellGraphicsItem : public QGraphicsPixmapItem { public: CellGraphicsItem(QPoint pos, int id, View2DScene* scene); public: void resize(int gridSize); QPoint pos() const { return m_pos; } void showCursor(QGraphicsItem* cursor); void setType(SpecialType type); void setCageLabel (const QString &cageLabel); void setValues(const QVector &values); protected: void hoverEnterEvent(QGraphicsSceneHoverEvent* event) override; void mousePressEvent(QGraphicsSceneMouseEvent* event) override; private: void updatePixmap(); private: View2DScene* m_scene; QPoint m_pos; SpecialType m_type; QVector m_values; QString m_cageLabel; int m_id; int m_size; int m_range; }; CellGraphicsItem::CellGraphicsItem(QPoint pos, int id, View2DScene* scene) { setAcceptHoverEvents(true); setShapeMode(QGraphicsPixmapItem::BoundingRectShape); m_pos = pos; m_size = 0; m_scene = scene; m_id = id; m_type = SpecialCell; m_range = scene->maxValue(); } void CellGraphicsItem::resize(int gridSize) { m_size = gridSize * 2; setPos(m_pos.x()*m_size, m_pos.y()*m_size); updatePixmap(); } void CellGraphicsItem::showCursor(QGraphicsItem* cursor) { cursor->setParentItem(this); cursor->setZValue(1); } void CellGraphicsItem::hoverEnterEvent(QGraphicsSceneHoverEvent* event) { Q_UNUSED(event); m_scene->hover(m_id); } void CellGraphicsItem::mousePressEvent(QGraphicsSceneMouseEvent* event) { switch(event->button()) { case Qt::LeftButton: m_scene->press(m_id); break; case Qt::RightButton: m_scene->press(m_id, true); break; default: break; } } void CellGraphicsItem::setType(SpecialType type) { if(type == m_type) return; m_type = type; updatePixmap(); } void CellGraphicsItem::setValues(const QVector &values) { m_values = values; updatePixmap(); } void CellGraphicsItem::setCageLabel(const QString &cageLabel) { m_cageLabel = cageLabel; } void CellGraphicsItem::updatePixmap() { if(m_size == 0) return; hide(); QPixmap pic = Renderer::instance()->renderSpecial(m_type, m_size); switch(m_type) { case SpecialCell: case SpecialCellMistake: if(!m_values.isEmpty()) { pic = Renderer::instance()->renderSymbolOn(pic, m_values[0].value, m_values[0].color, m_range, SymbolEdited); } break; case SpecialCellPreset: if(!m_values.isEmpty()) { pic = Renderer::instance()->renderSymbolOn(pic, m_values[0].value, 0, m_range, SymbolPreset); } break; case SpecialCellMarkers: { for(int i = m_values.size()-1; i >= 0; --i) { pic = Renderer::instance()->renderMarkerOn(pic, m_values[i].value, m_range, 0); } } break; default: break; // TODO maybe assert as this is not allowed to occur } if (! m_cageLabel.isEmpty()) { pic = Renderer::instance()->renderCageLabelOn(pic, m_cageLabel); } setPixmap(pic); show(); } struct GroupGraphicItemSegment { QPoint pos; int shape; QGraphicsPixmapItem* standard; QGraphicsPixmapItem* highlighted; }; class GroupGraphicsItem : public QGraphicsItemGroup { public: GroupGraphicsItem(const QVector &cells, bool isCage = false); ~GroupGraphicsItem(); void hideBlockBorder (bool visible); public: void resize(int gridSize, bool highlight); void setHighlight(bool highlight); void setHighlight(const QPoint& pos, bool highlight); private: int border(int tl, int tr, int bl, int br, int given); void detectType(); void createContour(); void createSegment(const QPoint& pos, int shape); private: GroupTypes m_type; QVector m_cells; QVector m_segments; bool m_isCage; // Is the group a cage, as in Killer Sudoku or Mathdoku? bool m_borderVisible; }; GroupGraphicsItem::GroupGraphicsItem(const QVector &cells, bool isCage) { m_cells = cells; m_isCage = isCage; m_borderVisible = true; setEnabled(false); setAcceptedMouseButtons(Qt::NoButton); detectType(); if (isCage) { // Draw border around cage, even if it is all in one row or column. m_type = GroupCage; setZValue(4); } createContour(); if(!m_cells.contains(QPoint(1,1))) setHighlight(false); } GroupGraphicsItem::~GroupGraphicsItem() { QVector::iterator segment; for(segment = m_segments.begin(); segment != m_segments.end(); ++segment) { if(segment->highlighted) delete segment->highlighted; if(segment->standard) delete segment->standard; } } void GroupGraphicsItem::hideBlockBorder (bool hide) { if ((m_type == GroupBlock) && hide) { m_borderVisible = false; } } void GroupGraphicsItem::detectType() { int x = m_cells[0].x(); int y = m_cells[0].y(); for(int i = 1; i < m_cells.size(); ++i) { if(x != m_cells[i].x()) x = -1; if(y != m_cells[i].y()) y = -1; } m_type = GroupNone; if(x==-1) m_type |= GroupRow; if(y==-1) m_type |= GroupColumn; // Row and column highlights must go above the GroupBlock boundary-line. // It really looks better to have the block highlight on top of the row // and column highlights, especially with cages or jigsaw-type blocks. // TODO - Might also be a good idea to reduce opacity of row and column. if(m_type == GroupColumn) setZValue(3); else if(m_type == GroupRow) setZValue(3); else if(m_type == GroupBlock) setZValue(4); } void GroupGraphicsItem::createContour() { for(int i = 0; i < m_cells.size(); ++i) { int x = m_cells[i].x(); int y = m_cells[i].y(); int idx[9]; // Find neighbours of cell (x, y). idx[0] = m_cells.indexOf(QPoint(x-1, y-1)); // North West. idx[1] = m_cells.indexOf(QPoint(x, y-1)); // North. idx[2] = m_cells.indexOf(QPoint(x+1, y-1)); // North East. idx[3] = m_cells.indexOf(QPoint(x-1, y )); // West. idx[4] = i; // Self. idx[5] = m_cells.indexOf(QPoint(x+1, y )); // East. idx[6] = m_cells.indexOf(QPoint(x-1, y+1)); // South West. idx[7] = m_cells.indexOf(QPoint(x, y+1)); // South. idx[8] = m_cells.indexOf(QPoint(x+1, y+1)); // South East. // A cage can consist of one cell with a border. if((m_type != GroupCage) && idx[1] == -1 && idx[3] == -1 && idx[5] == -1 && idx[7] == -1) { // No adjoining neighbour to N, S, E or W. m_type = GroupSpecial; // Used in the "X" of XSudoku. setZValue(4); // Same height as row or column. } int b; if((b = border(idx[0],idx[1],idx[3],idx[4],3))) { createSegment(QPoint(x,y), b); } if((b = border(idx[1],idx[2],idx[4],idx[5],2))) { createSegment(QPoint(x+1,y), b); } if((b = border(idx[3],idx[4],idx[6],idx[7],1))) { createSegment(QPoint(x,y+1), b); } if((b = border(idx[4],idx[5],idx[7],idx[8],0))) { createSegment(QPoint(x+1,y+1), b); } } } void GroupGraphicsItem::createSegment(const QPoint& pos, int shape) { GroupGraphicItemSegment segment; segment.pos = pos*2 - QPoint(1,1); segment.shape = shape; // Row and column groups are drawn only when highlighted. // Block groups have a boundary-line, but no middle unless highlighted. // Special groups (disjoint cells) have a special color. switch(m_type & GroupUnhighlightedMask) { case GroupRow: case GroupColumn: segment.standard = 0; break; case GroupBlock: case GroupCage: segment.standard = (shape == 15) ? 0 // No middle. : new QGraphicsPixmapItem(this); break; default: // Special Group segment.standard = new QGraphicsPixmapItem(this); break; } // All groups have highlighting. segment.highlighted = new QGraphicsPixmapItem(this); segment.highlighted->setVisible(false); m_segments << segment; } int GroupGraphicsItem::border(int tl, int tr, int bl, int br, int given) { switch(given) { case 0: if(tr > tl || bl > tl || br > tl) return 0; break; case 1: if(tl > tr || bl > tr || br > tr) return 0; break; case 2: if(tl > bl || tr > bl || br > bl) return 0; break; case 3: if(tl > br || tr > br || bl > br) return 0; break; } int b = ((tl!=-1)?1:0) | ((tr!=-1)?2:0) | ((bl!=-1)?4:0) | ((br!=-1)?8:0); return b; } void GroupGraphicsItem::setHighlight(bool highlight) { if(((m_type & GroupHighlight) == GroupHighlight) == highlight) return; QVector::iterator segment; for(segment = m_segments.begin(); segment != m_segments.end(); ++segment) { if (segment->highlighted) { segment->highlighted->setVisible(highlight); if ((m_type & GroupBlock) == GroupBlock) { // Block highlight goes on top of row, column and special // highlights. Block boundary-line goes underneath them. setZValue(highlight ? 8 : 4); } if (m_type == GroupSpecial) { // Special highlight goes on top of unhighlighted special cell. setZValue(highlight ? 9 : 4); } } if(segment->standard) { segment->standard->setVisible(!highlight); } } m_type ^= GroupHighlight; } void GroupGraphicsItem::setHighlight(const QPoint& pos, bool highlight) { setHighlight(m_cells.contains(pos) && highlight); } void GroupGraphicsItem::resize(int gridSize, bool highlight) { int size = gridSize*2; Renderer* r = Renderer::instance(); highlight = (m_type == GroupCage); // IDW test. highlight = true; // IDW test. GroupTypes standard = m_type & GroupUnhighlightedMask; GroupTypes highlighted = m_type | GroupHighlight; QVector::iterator segment; for(segment = m_segments.begin(); segment != m_segments.end(); ++segment) { QPointF pos = segment->pos*gridSize; // Has standard pixmap item? if(m_borderVisible && segment->standard) { QPixmap pic = r->renderBorder(segment->shape, standard, size); segment->standard->setPixmap(pic); segment->standard->setOffset(pos); } // Highlights on and has highlighted pixmap item? if(m_borderVisible && highlight && segment->highlighted) { QPixmap pic = r->renderBorder(segment->shape, highlighted, size); segment->highlighted->setPixmap(pic); segment->highlighted->setOffset(pos); } } } View2DScene::View2DScene(GameActions* gameActions) { m_gameActions = gameActions; m_background = 0; m_groupLayer = 0; m_cellLayer = 0; m_cursorPos = 0; m_cursor = 0; m_highlightsOn = false; } View2DScene::~View2DScene() { delete m_cursor; // needs to be deleted before cells // groups need to be deleted before m_groupLayer QVector::iterator group; for(group = m_groups.begin(); group != m_groups.end(); ++group) { delete *group; } // cells need to be deleted before m_cellLayer QVector::iterator cell; for(cell = m_cells.begin(); cell != m_cells.end(); ++cell) { delete *cell; } delete m_background; delete m_groupLayer; delete m_cellLayer; } void View2DScene::init(const Game& game) { m_selectedValue = 1; m_game = game; // Set the order of the layers. m_background = new QGraphicsPixmapItem(); m_background->setZValue(-7); // Background. addItem(m_background); m_groupLayer = new QGraphicsItemGroup(); m_groupLayer->setZValue(-1); // Boundary-lines and highlighting. addItem(m_groupLayer); m_cellLayer = new QGraphicsItemGroup(); m_cellLayer->setZValue(0); // Cell outlines and shading. m_cellLayer->setHandlesChildEvents(false); addItem(m_cellLayer); SKGraph* g = m_game.puzzle()->graph(); Renderer::instance()->setMathdokuStyle((g->specificType() == Mathdoku) || (g->specificType() == KillerSudoku)); m_cells.resize(m_game.size()); m_cursorPos = -1; for(int i = 0; i < m_game.size(); ++i) { // Do not paint unusable cells (e.g. gaps in Samurai puzzles). if (game.value(i) == UNUSABLE) { m_cells[i] = 0; continue; } m_cells[i] = new CellGraphicsItem(QPoint(g->cellPosX(i), g->cellPosY(i)), i, this); m_cells[i]->setParentItem(m_cellLayer); if(game.given(i)) // TODO - Implement allCellsLookSame preference. m_cells[i]->setType(SpecialCellPreset); // m_cells[i]->setType(SpecialCell); // IDW test. else m_cells[i]->setType(SpecialCell); if(game.value(i)) m_cells[i]->setValues(QVector() << ColoredValue(game.value(i),0)); else m_cells[i]->setValues(QVector()); if(m_cursorPos < 0) m_cursorPos = i; } m_groups.resize(g->cliqueCount() + g->cageCount()); // IDW TODO - Draw Killer Sudoku cages inside cell borders? // Anyway, show 3x3 and 2x2 blocks in Killer Sudoku somehow. bool hasBothBlocksAndCages = (g->specificType() == KillerSudoku); for(int i = 0; i < g->cliqueCount(); ++i) { // Set the shape of each group. QVector idx = g->clique(i); QVector pts = QVector(idx.size()); for(int j = 0; j < idx.size(); ++j) { pts[j] = QPoint(g->cellPosX(idx[j]), g->cellPosY(idx[j])); } m_groups[i] = new GroupGraphicsItem(pts); m_groups[i]->setParentItem(m_groupLayer); // Avoid ugly crossings of cages and blocks in Killer Sudoku. // Hide borders of blocks if there can be cages in the puzzle. m_groups[i]->hideBlockBorder (hasBothBlocksAndCages); } for(int i = 0; i < g->cageCount(); ++i) { // Create a cage: draw the label for all cages except size 1. initCageGroup (i, (g->cage(i).size() > 1)); } m_cursor = new QGraphicsPixmapItem(); addItem(m_cursor); hover(m_cursorPos); connect(m_game.interface(), SIGNAL(cellChange(int)), this, SLOT(update(int))); connect(m_game.interface(), SIGNAL(fullChange()), this, SLOT(update())); connect(m_game.interface(), &GameIFace::cageChange, this, &View2DScene::updateCage); connect(m_gameActions, &GameActions::selectValue, this, &View2DScene::selectValue); connect(m_gameActions, SIGNAL(enterValue(int)), this, SLOT(enterValue(int))); connect(m_gameActions, SIGNAL(markValue(int)), this, SLOT(flipMarkValue(int))); connect(m_gameActions, &GameActions::move, this, &View2DScene::moveCursor); // Fix bug 188162 by ensuring that all markers, as well as cells, are // updated and displayed after a Load action. update(-1); } void View2DScene::initCageGroup (int cageNum, bool drawLabel) { // Set the graphical shape and look of a Mathdoku or KillerSudoku cage. SKGraph* g = m_game.puzzle()->graph(); int offset = g->cliqueCount(); QVector idx = g->cage(cageNum); QVector pts = QVector(idx.size()); for(int j = 0; j < idx.size(); ++j) { pts[j] = QPoint(g->cellPosX(idx[j]), g->cellPosY(idx[j])); } m_groups[offset + cageNum] = new GroupGraphicsItem(pts, true); m_groups[offset + cageNum]->setParentItem(m_groupLayer); // Set the label of the cage (value and operator), but, in a single-cell // cage, draw it only during data-entry of the first cell of a cage. if (! drawLabel) { m_cells[g->cageTopLeft(cageNum)]->setCageLabel(QString()); } else if (drawLabel || (g->cage(cageNum).size() > 1)) { QString str = QString::number(g->cageValue(cageNum)); if (g->specificType() == Mathdoku) { // No op shown in KillerSudoku. str = str + QStringLiteral(" /-x+").mid(g->cageOperator(cageNum), 1); } m_cells[g->cageTopLeft(cageNum)]->setCageLabel(str); } } void View2DScene::setSceneSize(const QSize& size) { // Called from View2D::resizeEvent() and View2D::settingsChanged(). m_highlightsOn = Settings::showHighlights(); m_background->setPixmap(Renderer::instance()->renderBackground(size)); SKGraph* g = m_game.puzzle()->graph(); setSceneRect(QRectF(0, 0, size.width(), size.height())); int width = size.width() / (g->sizeX()+1); int height = size.height() / (g->sizeY()+1); int grid = qMin(width, height) / 2; int offsetX = size.width()/2 - g->sizeX()*grid; int offsetY = size.height()/2 - g->sizeY()*grid; m_groupLayer->setPos(offsetX, offsetY); m_cellLayer->setPos(offsetX, offsetY); for(int i = 0; i < m_game.size(); ++i) { if(m_cells[i] == 0) continue; m_cells[i]->resize(grid); } for (ksudoku::GroupGraphicsItem* group : qAsConst(m_groups)) { group->resize(grid, m_highlightsOn); } m_cursor->setPixmap(Renderer::instance()->renderSpecial(SpecialCursor, grid*2)); } void View2DScene::hover(int cell) { m_cursorPos = cell; // qCDebug(KSudokuLog) << "hover cell" << cell << m_cells[cell]; QPoint pos(m_cells[cell]->pos()); for (GroupGraphicsItem* item : qAsConst(m_groups)) { item->setHighlight(pos, m_highlightsOn); } m_cells[cell]->showCursor(m_cursor); } void View2DScene::press(int cell, bool rightButton) { // IDW TODO - Can we save the type and entry mode just once somewhere? if (! m_game.puzzle()->hasSolution()) { // Keying in a puzzle. Is it a Mathdoku or Killer Sudoku type? // If so, right click ==> delete cage: left click ==> add a cell. SKGraph * g = m_game.puzzle()->graph(); SudokuType t = g->specificType(); if ((t == Mathdoku) || (t == KillerSudoku)) { // If it is, delete or add a cell in the cage being entered. if (m_game.addToCage (cell, rightButton ? 32 : 30)) { return; } } } // Normal mouse actions for working on any kind of KSudoku puzzle. if(rightButton) { m_game.flipMarker(cell, m_selectedValue); } else { if(m_game.given(cell)) { selectValue(m_game.value(cell)); } else { m_game.setValue(cell, m_selectedValue); } } } void View2DScene::update(int cell) { if(cell < 0) { for(int i = 0; i < m_game.size(); ++i) { if(m_cells[i] == 0) continue; update(i); } } else { if(m_cells[cell] == 0) return; CellInfo cellInfo = m_game.cellInfo(cell); QVector values; switch(cellInfo.state()) { case GivenValue: // TODO - Implement allCellsLookSame preference. m_cells[cell]->setType(SpecialCellPreset); // m_cells[cell]->setType(SpecialCell); // IDW test. if(cellInfo.value()) values << ColoredValue(cellInfo.value(),0); m_cells[cell]->setValues(values); break; case CorrectValue: m_cells[cell]->setType(SpecialCell); if(cellInfo.value()) values << ColoredValue(cellInfo.value(),0); m_cells[cell]->setValues(values); break; case WrongValue: case ObviouslyWrong: m_cells[cell]->setType(SpecialCellMistake); if(cellInfo.value()) values << ColoredValue(cellInfo.value(),0); m_cells[cell]->setValues(values); break; case Marker: { m_cells[cell]->setType(SpecialCellMarkers); for(int i = 1; i <= m_game.size(); ++i) { if(cellInfo.marker(i)) values << ColoredValue(i,0); } m_cells[cell]->setValues(values); } break; } } } void View2DScene::updateCage (int cageNumP1, bool drawLabel) { if (cageNumP1 == 0) { qCDebug(KSudokuLog) << "ERROR: View2DScene::updateCage: cageNumP1 == 0."; return; } SKGraph* g = m_game.puzzle()->graph(); int offset = g->cliqueCount(); bool deleting = (cageNumP1 < 0); int cageNum = deleting ? (-cageNumP1 - 1) : (cageNumP1 - 1); if ((cageNum >= 0) && (m_groups.count() > (offset + cageNum))){ // Remove the cage-label from its scene-cell item. m_cells[g->cageTopLeft(cageNum)]->setCageLabel(QString()); // Remove the cage-graphics from the scene. removeItem (m_groups.at (offset + cageNum)); delete m_groups.at (offset + cageNum); m_groups[offset + cageNum] = 0; // Re-use or remove this later. } else { // Start adding a cage-group to the scene. m_groups.resize(g->cliqueCount() + g->cageCount()); } if (!deleting && (cageNum >= 0)) { // Create or re-create the cage that is being entered in. initCageGroup (cageNum, drawLabel); // IDW TODO - Should NOT need hilite settings, NOT hilite row/col. // IDW TODO - May need to doctor LOCAL CLASS GroupGraphicsItem for // hilite, deletion and removal of cage-label to happen. m_groups[offset + cageNum]->setHighlight (true); } else { // Deleting a cage: finish removing graphics item from scene-data. m_groups.remove (offset + cageNum); } // Invoke the method in View2DScene that triggers a re-draw. setSceneSize (views().first()->size()); } void View2DScene::selectValue(int value) { m_selectedValue = value; emit valueSelected( value ); } void View2DScene::enterValue(int value, int cell) { if(value >= 0) { if(cell >= 0) { m_game.setValue(cell, value); } else { m_game.setValue(m_cursorPos, value); } } else { if(cell >= 0) { m_game.setValue(cell, m_selectedValue); } else { m_game.setValue(m_cursorPos, m_selectedValue); } } } void View2DScene::markValue(int value, int cell, bool set) { if(value >= 0) { if(cell >= 0) { m_game.setMarker(cell, value, set); } else { m_game.setMarker(m_cursorPos, value, set); } } else { if(cell >= 0) { m_game.setMarker(cell, m_selectedValue, set); } else { m_game.setMarker(m_cursorPos, m_selectedValue, set); } } } void View2DScene::flipMarkValue(int value, int cell) { if(value >= 0) { if(cell >= 0) { m_game.flipMarker(cell, value); } else { m_game.flipMarker(m_cursorPos, value); } } else { if(cell >= 0) { m_game.flipMarker(cell, m_selectedValue); } else { m_game.flipMarker(m_cursorPos, m_selectedValue); } } } void View2DScene::moveCursor(int dx, int dy) { SKGraph* g = m_game.puzzle()->graph(); QPoint oldPos = m_cells[m_cursorPos]->pos(); QPoint relPos; int newCursorPos = -1; if(dx < 0) relPos.setX(-1); else if(dx > 0) relPos.setX(+1); if(dy < 0) relPos.setY(-1); else if(dy > 0) relPos.setY(+1); QPoint newPos = oldPos + relPos; while(newPos != oldPos && newCursorPos == -1) { if(newPos.x() < 0) newPos.setX(g->sizeX()-1); if(newPos.x() >= g->sizeX()) newPos.setX(0); if(newPos.y() < 0) newPos.setY(g->sizeY()-1); if(newPos.y() >= g->sizeY()) newPos.setY(0); for(int i = 0; i < m_game.size(); ++i) { if(m_cells[i] == 0) continue; if(m_cells[i]->pos() == newPos) { newCursorPos = i; break; } } newPos += relPos; } if(newCursorPos >= 0) hover(newCursorPos); } void View2DScene::wheelEvent(QGraphicsSceneWheelEvent* event) { if(event->orientation() != Qt::Vertical) return; if(event->delta() < 0) { m_selectedValue++; if(m_selectedValue > m_game.order()) m_selectedValue = 1; } else if(event->delta() > 0) { m_selectedValue--; if(m_selectedValue < 1) m_selectedValue = m_game.order(); } emit valueSelected(m_selectedValue); } View2D::View2D(QWidget *parent, const Game& game, GameActions* gameActions) : QGraphicsView(parent) { setVerticalScrollBarPolicy(Qt::ScrollBarAlwaysOff); setHorizontalScrollBarPolicy(Qt::ScrollBarAlwaysOff); setFrameStyle(QFrame::NoFrame); setAlignment( Qt::AlignLeft | Qt::AlignTop ); m_scene = new View2DScene(gameActions); m_scene->init(game); setScene(m_scene); gameActions->associateWidget(this); connect(m_scene, &View2DScene::valueSelected, this, &View2D::valueSelected); } View2D::~View2D() { delete m_scene; } void View2D::resizeEvent(QResizeEvent* e) { if(e) QGraphicsView::resizeEvent(e); if(m_scene) m_scene->setSceneSize(size()); } void View2D::selectValue(int value) { if(!m_scene) return; m_scene->selectValue(value); } void View2D::settingsChanged() { m_scene->setSceneSize(size()); } } diff --git a/src/gui/welcomescreen.cpp b/src/gui/welcomescreen.cpp index e1b56de..35ba822 100644 --- a/src/gui/welcomescreen.cpp +++ b/src/gui/welcomescreen.cpp @@ -1,209 +1,208 @@ /*************************************************************************** * Copyright 2007 Johannes Bergmeier * * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "welcomescreen.h" -#include #include #include #include #include "ksudokugame.h" #include "globals.h" #include "puzzle.h" Q_DECLARE_METATYPE(ksudoku::GameVariant*) namespace ksudoku { WelcomeScreen::WelcomeScreen(QWidget* parent, GameVariantCollection* collection) : QFrame(parent), m_collection(collection) { setupUi(this); // Get gameListWidget by loading from welcomescreen.ui. // Set the screen to display a multi-column list of puzzle-types, with // vertical scrolling. GameVariantDelegate::sizeHint() calculates the // number of columns and their width when it works out the size of the // item's display-area. QItemDelegate* delegate = new GameVariantDelegate(this, gameListWidget->viewport()); gameListWidget->setWrapping(true); gameListWidget->setResizeMode(QListView::Adjust); gameListWidget->setUniformItemSizes(true); gameListWidget->setFlow(QListView::LeftToRight); // Avoid a resize loop (with the scrollbar appearing and disappearing) // if ever the number of items and display-columns hits a bad combo. gameListWidget->setVerticalScrollBarPolicy(Qt::ScrollBarAlwaysOn); gameListWidget->setModel(m_collection); gameListWidget->setItemDelegate(delegate); gameListWidget->setVerticalScrollMode(QListView::ScrollPerPixel); gameListWidget->setSelectionBehavior(QAbstractItemView::SelectRows); gameListWidget->setSelectionMode(QAbstractItemView::SingleSelection); // Get the previous puzzle configuration. KConfigGroup gameGroup (KSharedConfig::openConfig(), "KSudokuGame"); m_selectedPuzzle = gameGroup.readEntry("SelectedPuzzle", 0); m_difficulty = gameGroup.readEntry("Difficulty", (int) VeryEasy); m_symmetry = gameGroup.readEntry("Symmetry" , (int) CENTRAL); // This has to be a deferred call (presumably to allow the view's setup // to complete), otherwise the selection fails to appear. QMetaObject::invokeMethod (this, "setSelectedVariant", Qt::QueuedConnection, Q_ARG (int, m_selectedPuzzle)); connect(gameListWidget->selectionModel(), &QItemSelectionModel::currentChanged, this, &WelcomeScreen::onCurrentVariantChange); connect(getNewGameButton, &QPushButton::clicked, this, &WelcomeScreen::getNewVariant); // TODO disabled due to missing per-game config dialog // connect(configureGameButton, SIGNAL(clicked(bool)), this, SLOT(configureVariant())); // connect(playGameButton, SIGNAL(clicked(bool)), this, SLOT(playVariant())); // Disable old create-game code. // connect(gameListWidget, SIGNAL(doubleClicked(QModelIndex)), this, SLOT(playVariant())); // Disable old create-game code. connect(startEmptyButton, &QPushButton::clicked, this, &WelcomeScreen::startEmptyGame); connect(puzzleGeneratorButton, &QPushButton::clicked, this, &WelcomeScreen::generatePuzzle); connect(gameListWidget, &QListView::doubleClicked, this, &WelcomeScreen::generatePuzzle); // GHNS is not implemented yet, so don't show an unuseful button getNewGameButton->hide(); } GameVariant* WelcomeScreen::selectedVariant() const { QModelIndex index = gameListWidget->currentIndex(); return m_collection->variant(index); } void WelcomeScreen::setSelectedVariant(int row) { gameListWidget->setCurrentIndex(gameListWidget->model()->index(row,0)); } int WelcomeScreen::difficulty() const { return m_difficulty; } void WelcomeScreen::setDifficulty(int difficulty) { m_difficulty = difficulty; } int WelcomeScreen::symmetry() const { return m_symmetry; } void WelcomeScreen::setSymmetry(int symmetry) { m_symmetry = symmetry; } void WelcomeScreen::onCurrentVariantChange() { GameVariant* variant = selectedVariant(); if(!variant) { // TODO disabled due to missing per-game config dialog // configureGameButton->setEnabled(false); // playGameButton->setEnabled(false); puzzleGeneratorButton->setEnabled(false); return; } // TODO disabled due to missing per-game config dialog // configureGameButton->setEnabled(variant->canConfigure()); startEmptyButton->setEnabled(variant->canStartEmpty()); // playGameButton->setEnabled(true); puzzleGeneratorButton->setEnabled(true); } void WelcomeScreen::getNewVariant() { KMessageBox::information(this, i18n("GetNewVariant not implemented"), QLatin1String("")); } void WelcomeScreen::configureVariant() { GameVariant* variant = selectedVariant(); if(!variant) return; variant->configure(); } void WelcomeScreen::startEmptyGame() { GameVariant* variant = selectedVariant(); if(!variant) { KMessageBox::sorry(this, i18n("Please select a puzzle variant."), i18n("Unable to start puzzle")); return; } Game game = variant->startEmpty(); if (! game.isValid()) { KMessageBox::sorry(this, i18n("Unable to create an empty puzzle of the chosen variant; please try another."), i18n("Unable to start puzzle")); return; } emit newGameStarted(game, variant); } void WelcomeScreen::playVariant() { return; // Disable old game-creation code. GameVariant* variant = selectedVariant(); if(!variant) { KMessageBox::sorry(this, i18n("Please select a puzzle variant."), i18n("Unable to start puzzle")); return; } Game game = variant->createGame(difficulty(), 0); if(!game.isValid()) { KMessageBox::sorry(this, i18n("Unable to start a puzzle of the chosen variant; please try another."), i18n("Unable to start puzzle")); return; } emit newGameStarted(game, variant); } void WelcomeScreen::generatePuzzle() { GameVariant* variant = selectedVariant(); if(!variant) { KMessageBox::sorry(this, i18n("Please select a puzzle variant."), i18n("Unable to start puzzle")); return; } Game game = variant->createGame(difficulty(), symmetry()); if(!game.isValid()) { KMessageBox::sorry(this, i18n("Unable to generate a puzzle of the chosen variant; please try another."), i18n("Unable to start puzzle")); return; } // Save the selected puzzle configuration. QModelIndex index = gameListWidget->currentIndex(); m_selectedPuzzle = index.row(); KConfigGroup gameGroup (KSharedConfig::openConfig(), "KSudokuGame"); gameGroup.writeEntry("SelectedPuzzle", m_selectedPuzzle); gameGroup.writeEntry("Difficulty", m_difficulty); gameGroup.writeEntry("Symmetry" , m_symmetry); gameGroup.sync(); // Ensure that the entry goes to disk. // If the user abandoned puzzle-generation, stay on the Welcome Screen // and allow the user to change the Difficulty, etc. of the puzzle. if (game.puzzle()->hasSolution()) { emit newGameStarted(game, variant); // OK, start playing. } } } diff --git a/src/logic/puzzle.cpp b/src/logic/puzzle.cpp index d190fac..cfcdfbb 100644 --- a/src/logic/puzzle.cpp +++ b/src/logic/puzzle.cpp @@ -1,122 +1,121 @@ /*************************************************************************** * Copyright 2007 Francesco Rossi * * Copyright 2006-2007 Mick Kappenburg * * Copyright 2006-2007 Johannes Bergmeier * * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "puzzle.h" #include -#include #include "sudokuboard.h" #include "mathdokugenerator.h" namespace ksudoku { Puzzle::Puzzle(SKGraph *graph, bool withSolution) : m_withSolution(withSolution) , m_graph(graph) , m_difficulty(0) , m_symmetry(0) , m_initialized(false) { } int Puzzle::value(int index) const { return ((index < m_puzzle.size()) ? m_puzzle.at(index) : 0); } int Puzzle::solution(int index) const { return ((index < m_solution.size()) ? m_solution.at(index) : 0); } int Puzzle::hintIndex(int moveNum) const { return ((moveNum >= m_hintList.count()) ? -1 : m_hintList.at(moveNum)); } bool Puzzle::init() { if(m_initialized) return false; if(m_withSolution) return false; // Set up an empty puzzle. The user will enter his/her own puzzle. if(m_graph) { m_puzzle = m_graph->emptyBoard(); } return true; } bool Puzzle::init(int difficulty, int symmetry) { if(m_initialized) return false; SudokuBoard * board = new SudokuBoard (m_graph); // Generate a puzzle and its solution. bool success = board->generatePuzzle (m_puzzle, m_solution, (Difficulty) difficulty, (Symmetry) symmetry); if (success) { board->getMoveList (m_hintList); } // Too many tries at generating a puzzle that meets the user's reqs. else { m_puzzle.clear(); // Wipe the puzzle and its solution. m_solution.clear(); } delete board; return success; } int Puzzle::init(const BoardContents & values) { if(m_initialized) return -1; int result = -1; SudokuType t = m_graph->specificType(); // Save the puzzle values and solution (if any). m_puzzle = values; m_hintList.clear(); if ((t != Mathdoku) && (t != KillerSudoku)) { SudokuBoard * board = new SudokuBoard (m_graph); m_solution = board->solveBoard (m_puzzle); // Get SudokuBoard to check the solution. result = board->checkPuzzle (m_puzzle); if (result != 0) { board->getMoveList (m_hintList); } if (result >= 0) { result = 1; // There is one solution. } else if (result == -1) { result = 0; // There is no solution. } else { result = 2; // There is more than one solution. } delete board; } else { MathdokuGenerator mg (m_graph); result = mg.solveMathdokuTypes (m_solution, &m_hintList); } return result; } } diff --git a/src/logic/skgraph.cpp b/src/logic/skgraph.cpp index 0f78aa2..4283339 100644 --- a/src/logic/skgraph.cpp +++ b/src/logic/skgraph.cpp @@ -1,252 +1,251 @@ /*************************************************************************** * Copyright 2005-2007 Francesco Rossi * * Copyright 2006-2007 Mick Kappenburg * * Copyright 2006-2008 Johannes Bergmeier * * Copyright 2012 Ian Wadham * * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "skgraph.h" #include #include -#include SKGraph::SKGraph(int order, ksudoku::GameType type) { m_order = order; m_base = 3; for (int n = 2; n <= 5; n++) { if (m_order == n * n) { m_base = n; } } m_type = type; } SKGraph::~SKGraph() { clearCages(); } void SKGraph::initSudoku() { m_name = QStringLiteral("PlainSudoku"); m_specificType = Plain; m_sizeX = m_order; m_sizeY = m_order; m_sizeZ = 1; m_emptyBoard.fill (UNUSABLE, size()); initSudokuGroups(0, true); indexCellsToCliques(); } void SKGraph::initSudokuGroups(int pos, bool withBlocks) { // initSudokuGroups() sets up rows and columns in a Sudoku grid of size // (m_order*m_order) cells. Its first parameter (usually 0) shows where // on the whole board the grid goes. This is relevant in Samurai and // related layouts. Its second attribute is true if square-block groups // are required or false if not (e.g. as in a Jigsaw or Mathdoku type). m_structures << SudokuGroups << pos << (withBlocks ? 1 : 0); QVector rowc, colc, blockc; for(int i = 0; i < m_order; ++i) { rowc.clear(); colc.clear(); blockc.clear(); for(int j = 0; j < m_order; ++j) { rowc << pos + j*m_sizeY + i; colc << pos + i*m_sizeY + j; blockc << pos + ((i/m_base)*m_base + j%m_base) * m_sizeY + (i%m_base)*m_base + j/m_base; } addClique(rowc); addClique(colc); if (withBlocks) { addClique(blockc); } } } void SKGraph::initRoxdoku() { m_name = QStringLiteral("Roxdoku"); m_specificType = Roxdoku; m_sizeX = m_base; m_sizeY = m_base; m_sizeZ = m_base; m_emptyBoard.fill (UNUSABLE, size()); initRoxdokuGroups(0); indexCellsToCliques(); } void SKGraph::initRoxdokuGroups(int pos) { // initRoxdokuGroups() sets up the intersecting planes in a // 3-D Roxdoku grid. Its only parameter shows where in the entire // three-dimensional layout the grid goes. m_structures << RoxdokuGroups << pos << 1; QVector xFace, yFace, zFace; int x = cellPosX(pos); int y = cellPosY(pos); int z = cellPosZ(pos); for (int i = 0; i < m_base; i++) { xFace.clear(); yFace.clear(); zFace.clear(); for (int j = 0; j < m_base; j++) { for (int k = 0; k < m_base; k++) { // Intersecting faces at relative (0,0,0), (1,1,1), etc. xFace << cellIndex (x + i, y + j, z + k); yFace << cellIndex (x + k, y + i, z + j); zFace << cellIndex (x + j, y + k, z + i); } } addClique(xFace); addClique(yFace); addClique(zFace); } } void SKGraph::addCliqueStructure(const QVector &data) { m_structures << Clique << m_cliques.count() << 0; addClique(data); } void SKGraph::addClique(const QVector &data) { // Add to the cliques (groups) list. m_cliques << data; for (int n = 0; n < data.size(); n++) { // Set cells in groups VACANT: cells not in groups are UNUSABLE. m_emptyBoard [data.at(n)] = VACANT; } } void SKGraph::addCage(const QVector &cage, CageOperator cageOperator, int cageValue) { // Add to the cages list. m_cages.append (new Cage); Cage * newCage = m_cages.last(); newCage->cage = cage; newCage->cageOperator = cageOperator; newCage->cageValue = cageValue; // Calculate cageTopLeft cell (used for displaying operator and value). int topY = m_order; int leftX = m_order; newCage->cageTopLeft = 0; for (const int cell : cage) { if (cellPosY(cell) > topY) { continue; // Below the best so far. } else if ((cellPosY(cell) == topY) && (cellPosX(cell) > leftX)) { continue; // Same height as best but to the right. } newCage->cageTopLeft = cell; topY = cellPosY(cell); leftX = cellPosX(cell); } } void SKGraph::dropCage(int cageNum) { if (cageNum >= m_cages.count()) { return; } delete m_cages.at (cageNum); m_cages.remove (cageNum); } void SKGraph::clearCages() { // Clear previous cages (if any). if (! m_cages.isEmpty()) { qDeleteAll (m_cages); m_cages.clear(); } } void SKGraph::initCustom(const QString & name, SudokuType specificType, int order, int sizeX, int sizeY, int sizeZ, int ncliques) { // The Serializer's deserializer methods will add groups (or cliques). m_name = name; m_specificType = specificType; m_order = order; m_sizeX = sizeX; m_sizeY = sizeY; m_sizeZ = sizeZ; m_emptyBoard.fill (UNUSABLE, size()); } void SKGraph::endCustom() { indexCellsToCliques(); } void SKGraph::indexCellsToCliques() { QMultiMap cellsToCliques; int nCliques = cliqueCount(); int nCells = size(); for (int g = 0; g < nCliques; g++) { QVector cellList = clique(g); for (int n = 0; n < m_order; n++) { cellsToCliques.insert (cellList.at (n), g); } } m_cellIndex.fill (0, nCells + 1); m_cellCliques.fill (0, nCliques * m_order); int index = 0; for (int cell = 0; cell < nCells; cell++) { m_cellIndex [cell] = index; const QList cliqueList = cellsToCliques.values (cell); for (int g : cliqueList) { m_cellCliques [index] = g; index++; } } m_cellIndex [nCells] = index; } const QList SKGraph::cliqueList(int cell) const { // NOTE: We could have used QMultiMap::values(int cell) to // access this index, but the index's main usage is on an inner loop // of the generator/solver and execution time is a concern there. QList cells; int start = m_cellIndex.at(cell); int end = m_cellIndex.at(cell + 1); for (int n = start; n < end; n++) { cells << m_cellCliques.at(n); } return cells; } diff --git a/src/main.cpp b/src/main.cpp index 71b34c4..bc4c5e2 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -1,106 +1,105 @@ /*************************************************************************** * Copyright 2005-2007 Francesco Rossi * * Copyright 2006-2007 Mick Kappenburg * * Copyright 2006-2007 Johannes Bergmeier * * Copyright 2015 Ian Wadham * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * ***************************************************************************/ #include "ksudoku.h" #include #include #include #include #include #include -#include #include #include #include #include static const char description[] = I18N_NOOP("KSudoku - Sudokus and more"); static const char version[] = "1.4"; int main(int argc, char **argv) { qsrand(std::time(nullptr)); QApplication app(argc, argv); KLocalizedString::setApplicationDomain("ksudoku"); KAboutData about(QStringLiteral("ksudoku"), i18n("KSudoku"), version, i18n(description), KAboutLicense::GPL_V2, i18n("(c) 2005-2007 The KSudoku Authors"), QString(), QStringLiteral("https://games.kde.org/game.php?game=ksudoku")); about.addAuthor( i18n("Francesco Rossi"), i18n("KSudoku Author"), QStringLiteral("redsh@email.it") ); about.addAuthor( i18n("Johannes Bergmeier"), i18n("Maintainer"), QStringLiteral("Johannes.Bergmeier@gmx.net") ); about.addAuthor( i18n("Ian Wadham"), i18n("New puzzle generator and solver"), QStringLiteral("iandw.au@gmail.com") ); about.addAuthor( i18n("Mick Kappenburg"), i18n("Printing and export of 0.4"), QStringLiteral("ksudoku@kappendburg.net")); about.addAuthor( i18n("Thanks to NeHe for OpenGL tutorials"), QString(), QStringLiteral("nehe.gamedev.net")); about.addCredit( i18n("David Bau"), i18n("Algorithms for new puzzle generator and solver at davidbau.com/archives/2006/09/04/sudoku_generator.html"), QLatin1String("")); KAboutData::setApplicationData(about); app.setOrganizationDomain(QStringLiteral("kde.org")); app.setWindowIcon(QIcon::fromTheme(QStringLiteral("ksudoku"))); QCommandLineParser parser; about.setupCommandLine(&parser); parser.addPositionalArgument(QStringLiteral("[URL]"), i18n( "Document to open" )); parser.process(app); about.processCommandLine(&parser); KCrash::initialize(); // register ourselves as a dcop client // app.dcopClient()->registerAs(app.name(), false); //TODO PORT KConfigDialogManager::changedMap()->insert(QStringLiteral("ksudoku::SymbolConfigListWidget"), SIGNAL(itemChanged(QListWidgetItem*))); // see if we are starting with session management /*if (app.isRestored()) { RESTORE(KSudoku); } else {*/ KSudoku *widget = new KSudoku; widget->show(); // no session.. just start up normally if (parser.positionalArguments().count() != 0) { for (int i = 0; i < parser.positionalArguments().count(); ++i) { widget->loadGame(QUrl::fromUserInput(parser.positionalArguments().at(i), QDir::currentPath())); } } //} //TODO PORT return app.exec(); }