/* * qqwing - A Sudoku solver and generator * Copyright (C) 2006-2014 Stephen Ostermiller http://ostermiller.org/ * Copyright (C) 2007 Jacques Bensimon (jacques@ipm.com) * Copyright (C) 2011 Jean Guillerez (j.guillerez - orange.fr) * Copyright (C) 2014 Michael Catanzaro (mcatanzaro@gnome.org) * * 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 QQWING_HPP #define QQWING_HPP #include #include namespace qqwing { using namespace std; class LogItem; const int GRID_SIZE = 3; const int ROW_COL_SEC_SIZE = GRID_SIZE*GRID_SIZE; const int SEC_GROUP_SIZE = ROW_COL_SEC_SIZE*GRID_SIZE; const int BOARD_SIZE = ROW_COL_SEC_SIZE*ROW_COL_SEC_SIZE; const int POSSIBILITY_SIZE = BOARD_SIZE*ROW_COL_SEC_SIZE; /** * The version of QQwing, e.g. 1.2.3 */ string getVersion(); /** * The board containing all the memory structures and * methods for solving or generating sudoku puzzles. */ class SudokuBoard { public: enum PrintStyle { ONE_LINE, COMPACT, READABLE, CSV }; enum Difficulty { UNKNOWN, SIMPLE, EASY, INTERMEDIATE, EXPERT }; enum Symmetry { NONE, ROTATE90, ROTATE180, MIRROR, FLIP, RANDOM }; SudokuBoard(); bool setPuzzle(int* initPuzzle); const int* getPuzzle(); const int* getSolution(); void printPuzzle(); void printSolution(); bool solve(); /** * Count the number of solutions to the puzzle */ int countSolutions(); /** * Count the number of solutions to the puzzle * but return two any time there are two or * more solutions. This method will run much * falter than countSolutions() when there * are many possible solutions and can be used * when you are interested in knowing if the * puzzle has zero, one, or multiple solutions. */ int countSolutionsLimited(); /** * return true if the puzzle has a solution * and only a single solution */ bool hasUniqueSolution(); bool isSolved(); void printSolveHistory(); void setRecordHistory(bool recHistory); void setLogHistory(bool logHist); void setPrintStyle(PrintStyle ps); bool generatePuzzle(); bool generatePuzzleSymmetry(SudokuBoard::Symmetry symmetry); int getGivenCount(); int getSingleCount(); int getHiddenSingleCount(); int getNakedPairCount(); int getHiddenPairCount(); int getBoxLineReductionCount(); int getPointingPairTripleCount(); int getGuessCount(); int getBacktrackCount(); void printSolveInstructions(); SudokuBoard::Difficulty getDifficulty(); string getDifficultyAsString(); ~SudokuBoard(); private: /** * The 81 integers that make up a sudoku puzzle. * Givens are 1-9, unknowns are 0. * Once initialized, this puzzle remains as is. * The answer is worked out in "solution". */ int* puzzle; /** * The 81 integers that make up a sudoku puzzle. * The solution is built here, after completion * all will be 1-9. */ int* solution; /** * Recursion depth at which each of the numbers * in the solution were placed. Useful for backing * out solve branches that don't lead to a solution. */ int* solutionRound; /** * The 729 integers that make up a the possible * values for a Sudoku puzzle. (9 possibilities * for each of 81 squares). If possibilities[i] * is zero, then the possibility could still be * filled in according to the Sudoku rules. When * a possibility is eliminated, possibilities[i] * is assigned the round (recursion level) at * which it was determined that it could not be * a possibility. */ int* possibilities; /** * An array the size of the board (81) containing each * of the numbers 0-n exactly once. This array may * be shuffled so that operations that need to * look at each cell can do so in a random order. */ int* randomBoardArray; /** * An array with one element for each position (9), in * some random order to be used when trying each * position in turn during guesses. */ int* randomPossibilityArray; /** * Whether or not to record history */ bool recordHistory; /** * Whether or not to print history as it happens */ bool logHistory; /** * A list of moves used to solve the puzzle. * This list contains all moves, even on solve * branches that did not lead to a solution. */ vector* solveHistory; /** * A list of moves used to solve the puzzle. * This list contains only the moves needed * to solve the puzzle, but doesn't contain * information about bad guesses. */ vector* solveInstructions; /** * The style with which to print puzzles and solutions */ PrintStyle printStyle; /** * The last round of solving */ int lastSolveRound; bool reset(); bool singleSolveMove(int round); bool onlyPossibilityForCell(int round); bool onlyValueInRow(int round); bool onlyValueInColumn(int round); bool onlyValueInSection(int round); bool solve(int round); int countSolutions(bool limitToTwo); int countSolutions(int round, bool limitToTwo); bool guess(int round, int guessNumber); bool isImpossible(); void rollbackRound(int round); bool pointingRowReduction(int round); bool rowBoxReduction(int round); bool colBoxReduction(int round); bool pointingColumnReduction(int round); bool hiddenPairInRow(int round); bool hiddenPairInColumn(int round); bool hiddenPairInSection(int round); void mark(int position, int round, int value); int findPositionWithFewestPossibilities(); bool handleNakedPairs(int round); int countPossibilities(int position); bool arePossibilitiesSame(int position1, int position2); void addHistoryItem(LogItem* l); void shuffleRandomArrays(); void print(int* sudoku); void rollbackNonGuesses(); void clearPuzzle(); void printHistory(vector* v); bool removePossibilitiesInOneFromTwo(int position1, int position2, int round); }; } #endif