1 /**************************************************************************** 2 * Copyright 2015 Ian Wadham <iandw.au@gmail.com> * 3 * * 4 * This program is free software; you can redistribute it and/or * 5 * modify it under the terms of the GNU General Public License as * 6 * published by the Free Software Foundation; either version 2 of * 7 * the License, or (at your option) any later version. * 8 * * 9 * This program is distributed in the hope that it will be useful, * 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 12 * GNU General Public License for more details. * 13 * * 14 * You should have received a copy of the GNU General Public License * 15 * along with this program. If not, see <http://www.gnu.org/licenses/>. * 16 ****************************************************************************/ 17 18 #ifndef DLXSOLVER_H 19 #define DLXSOLVER_H 20 21 #include <QList> 22 #include <QObject> 23 24 #include "globals.h" 25 #include "skgraph.h" 26 27 struct DLXNode // Represents a 1 in a sparse matrix 28 // containing only ones and zeroes. 29 { 30 DLXNode * left; // Link to next node left. 31 DLXNode * right; // Link to next node right. 32 DLXNode * above; // Link to next node above. 33 DLXNode * below; // Link to next node below. 34 35 DLXNode * columnHeader; // Link to top of column. 36 int value; // In col header: count of ones in col. 37 // In node: row-number of node. 38 }; 39 40 /** 41 * @class DLXSolver dlxsolver.h 42 * @short Provides a solver, based on the DLX algorithm, for Sudoku variants. 43 * 44 * This solver can handle all variants of Sudoku puzzles supported by KSudoku, 45 * including classical 9x9 Sudokus, 2-D variants, 3-D variants, Killer Sudoku 46 * and MathDoku (aka KenKen TM). 47 * 48 * Killer and MathDoku puzzles have cages in which all the numbers must satisfy 49 * an arithmetic constraint, as well as satisfying the usual Sudoku constraints 50 * (using all numbers exactly once each in a column, row or group). Killer 51 * Sudokus have 9x9 cells and nine 3x3 boxes, but there are no clues and each 52 * cage must add up to a prescribed total. MathDokus can have N x N cells, for 53 * N >= 3, but no boxes. Each cage has an operator (+, -, multiply or divide) 54 * which must be used to reach the required value. In Killers and Mathdokus, a 55 * cage with just one cell is effectively a clue. 56 * 57 * The DLX algorithm (aka Dancing Links) is due to Donald Knuth. 58 */ 59 class DLXSolver : public QObject 60 { 61 Q_OBJECT 62 public: 63 explicit DLXSolver (QObject * parent); 64 ~DLXSolver() override; 65 66 /** 67 * Takes any of the various kinds of 2-D Sudoku or 3-D Roxdoku puzzle 68 * supported by the KSudoku application program and converts it into a 69 * sparse matrix of constraints and possible solution values for each 70 * vacant cell. It then calls the solveDLX method to solve the puzzle, 71 * using Donald Knuth's Dancing Links (DLX) algorithm. The algorithm can 72 * find zero, one or any number of solutions, each of which can converted 73 * back into a KSudoku grid containing a solution. 74 * 75 * Each column in the DLX matrix represents a constraint that must be 76 * satisfied. In a Classic 9x9 Sudoku, there are 81 constraints to say that 77 * each cell must be filled in exactly once. Then there are 9x9 constraints 78 * to say that each of the 9 Sudoku columns must contain the numbers 1 to 9 79 * exactly once. Similarly for the 9 Sudoku rows and the 9 3x3 boxes. In 80 * total, there are 81 + 9x9 + 9x9 + 9x9 = 324 constraints and so there are 81 * 324 columns in the DLX matrix. 82 * 83 * Each row in the DLX matrix represents a position in the Sudoku grid and 84 * a value (1 to 9) that might go there. If it does, it will satisfy 4 of 85 * the constraints: filling in a cell and putting that value in a column, a 86 * row and a 3x3 box. That possibility is represented by a 1 in that row in 87 * each of the corresponding constraint columns. Thus there are 4 ones in 88 * each row of the 9x9 Sudoku's DLX matrix and in total there 9x81 = 729 89 * rows, representing a possible 1 to 9 in each of 81 cells. 90 * 91 * A solution to the 9x9 Sudoku will consist of a set of 81 rows such that 92 * each column contains a single 1. That means that each constraint is 93 * satisfied exactly once, as required by the rules of Sudoku. Each of the 94 * successful 81 rows will still contain its original four 1's, representing 95 * the constraints the corresponding Sudoku cell and value satisfies. 96 * 97 * Applying clues reduces the rows to be found by whatever the number of 98 * clues is --- and it also reduces the size of the DLX matrix considerably. 99 * For example, for a 9x9 Classic Sudoku, the size can reduce from 729x324 100 * to 224x228 or even less. Furthermore, many of the remaining columns 101 * contain a single 1 already, so the solution becomes quite fast. 102 * 103 * KSudoku can handle other sizes and shapes of Sudoku puzzle, including the 104 * 3-D Roxdoku puzzles. For example, an XSudoku is like a Classic 9x9 puzzle 105 * except that the two diagonals must each contain the numbers 1 to 9 once 106 * and once only. In DLX, this can be represented by 18 additional columns 107 * to represent the constraints on the diagonals. Also a group of 9 cells 108 * might not have a simple row, column or 3x3 box shape, as in a jigsaw 109 * type of Sudoku or a 3-D Roxdoku, and a Samurai Sudoku has five 9x9 110 * grids overlapping inside a 21x21 array of cells, some of which must NOT 111 * be used. All this is represented by lists of cells in the SKGraph object, 112 * known as "cliques" or "groups". So, in the more general case, each group 113 * of 9 cells will have its own 9 constraints or DLX matrix columns. 114 * 115 * @param graph An SKGraph object representing the size, geometric 116 * layout and rules of the particular kind of puzzle. 117 * @param boardValues A vector containing clue values, vacant cells and 118 * unused values for the puzzle and its layout. 119 * @param solutionLimit A limit to the number of solutions to be delivered 120 * where 0 = no limit, 1 gets the first solution only 121 * and 2 is used to test if there is > 1 solution. 122 * 123 * @return The number of solutions found (0 to solutionLimit). 124 */ 125 int solveSudoku (SKGraph * graph, const BoardContents & boardValues, 126 int solutionLimit = 2); 127 128 /** 129 * Takes a Mathdoku or Killer Sudoku puzzle and converts it into a sparse 130 * matrix of constraints and possible solution values for each cage. The 131 * constraints are that each cage must be filled in and that each column 132 * and row of the puzzle solution must follow Sudoku rules (blocks too, in 133 * Killer Sudoku). The possible solutions are represented by one DLX row per 134 * possible set of numbers for each cage. The solveDLX() method is then used 135 * to test that the puzzle has one and only one solution, which consists of 136 * a subset of the original DLX rows (i.e. one set of numbers per cage). For 137 * more detail, see solveSudoku(). 138 * 139 * @param graph An SKGraph object representing the size, geometric 140 * layout and rules of the particular kind of puzzle, 141 * as well as its cage layouts, values and operators. 142 * @param solutionMoves A pointer that returns an ordered list of cells 143 * found by the solver when it reaches a solution. 144 * @param possibilities A pointer to a list of possible values for all the 145 * cells in all the cages. 146 * @param possibilitiesIndex 147 * An index into the possibilities list, with one 148 * index-entry per cage, plus an end-of-list index. 149 * @param solutionLimit A limit to the number of solutions to be delivered 150 * where 0 = no limit, 1 gets the first solution only 151 * and 2 is used to test if there is > 1 solution. 152 * 153 * @return The number of solutions found (0 to solutionLimit). 154 */ 155 int solveMathdoku (SKGraph * graph, QList<int> * solutionMoves, 156 const QList<int> * possibilities, 157 const QList<int> * possibilitiesIndex, 158 int solutionLimit = 2); 159 160 /** 161 * Copy back to the caller the last solution found by the solver. 162 * 163 * @param solution A BoardContents object to receive the solution. 164 */ 165 void retrieveSolution (BoardContents & solution); 166 167 // void testDLX(); // TODO - Delete this eventually. 168 169 private: 170 /** 171 * Takes a sparse matrix of ones and zeroes and solves the Exact Cover 172 * Problem for it, using Donald Knuth's Dancing Links (DLX) algorithm. 173 * 174 * A solution is a subset of rows which, when combined, have a single 1 in 175 * each column. If each DLX column represents a constraint or condition that 176 * must be satisfied exactly once and each row represents a possible part of 177 * the solution, then the whole matrix can represent a problem such as 178 * Sudoku or Mathdoku and the subset of rows can represent a solution to 179 * that Sudoku or Mathdoku. A particular matrix can have 0, 1 or any number 180 * of Exact Cover solutions, as can the corresponding puzzle. 181 * 182 * See the code in file dlxsolver.cpp for a description of the algorithm. 183 * 184 * @param solutionLimit A limit to the number of solutions to be delivered 185 * where 0 = no limit, 1 gets the first solution only 186 * and 2 is used to test if there is > 1 solution. 187 * 188 * @return The number of solutions found (0 to solutionLimit). 189 * Actual solutions are returned progressively a Qt 190 * signal-slot mechanism. 191 */ 192 int solveDLX (int solutionLimit); 193 194 /** 195 * Temporarily remove a column from the DLX matrix, along with all of the 196 * rows that have nodes (1's) in this column. 197 * 198 * @param colDLX A pointer to the header of the column. 199 */ 200 void coverColumn (DLXNode * colDLX); 201 202 /** 203 * Re-insert a column into the DLX matrix, along with all of the rows that 204 * have nodes (1's) in this column. 205 * 206 * @param colDLX A pointer to the header of the column. 207 */ 208 void uncoverColumn (DLXNode * colDLX); 209 210 void recordSolution (const int solutionNum, QList<DLXNode *> & solution); 211 212 // Empty the DLX matrix, but do not deallocate the nodes. 213 void clear(); 214 215 // Add a node (i.e. a 1) to the sparse DLX matrix. 216 void addNode (int rowNum, int colNum); 217 218 // Get a node-structure, allocating or re-using as needed. 219 DLXNode * allocNode(); 220 221 // Initialise a node to point to itself and contain value 0. 222 void initNode (DLXNode * node); 223 224 // Circularly link a node to the end of a DLX matrix row. 225 void addAtRight (DLXNode * node, DLXNode * start); 226 227 // Circularly link a node to the end of a DLX matrix column. 228 void addBelow (DLXNode * node, DLXNode * start); 229 230 // Deallocate all nodes. 231 void deleteAll(); 232 233 DLXNode * mCorner; 234 QList<DLXNode *> mColumns; 235 QList<DLXNode *> mRows; 236 QList<DLXNode *> mNodes; 237 int mEndColNum; 238 int mEndRowNum; 239 int mEndNodeNum; 240 241 BoardContents mBoardValues; // Holds Sudoku problem and solution. 242 QList<int> * mSolutionMoves; // Sequence of cells used in solution. 243 SKGraph * mGraph; 244 const QList<int> * mPossibilities; 245 const QList<int> * mPossibilitiesIndex; 246 247 // Print the current state of the Sudoku puzzle. 248 void printSudoku(); 249 250 // Print DLX matrix (default is to skip printing those that are too large). 251 void printDLX (bool forced = false); 252 }; 253 254 #endif // DLXSOLVER_H 255