1 /*************************************************************************** 2 * Copyright 2005-2007 Francesco Rossi <redsh@email.it> * 3 * Copyright 2006 Mick Kappenburg <ksudoku@kappendburg.net> * 4 * Copyright 2006-2008 Johannes Bergmeier <johannes.bergmeier@gmx.net> * 5 * Copyright 2012 Ian Wadham <iandw.au@gmail.com> * 6 * Copyright 2015 Ian Wadham <iandw.au@gmail.com> * 7 * * 8 * This program is free software; you can redistribute it and/or modify * 9 * it under the terms of the GNU General Public License as published by * 10 * the Free Software Foundation; either version 2 of the License, or * 11 * (at your option) any later version. * 12 * * 13 * This program is distributed in the hope that it will be useful, * 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 16 * GNU General Public License for more details. * 17 * * 18 * You should have received a copy of the GNU General Public License * 19 * along with this program; if not, write to the * 20 * Free Software Foundation, Inc., * 21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * 22 ***************************************************************************/ 23 24 #ifndef SKGRAPH_H 25 #define SKGRAPH_H 26 27 #include <QList> 28 #include <QString> 29 #include <QVector> 30 31 #include "ksudoku_types.h" 32 #include "globals.h" 33 34 /** 35 * @class SKGraph skgraph.h 36 * @short Generalized data representing a Sudoku puzzle size, shape and rules. 37 * 38 * SKGraph is an abstract class that can represent any type or size of Sudoku 39 * puzzle layout, either in two dimensions or three. Together with the Puzzle 40 * class (see src/logic/puzzle.h) it forms the core of KSudoku and is used by 41 * the puzzle generator/solver (see src/generator/sudokuboard.h), the 2-D and 42 * 3-D views, the Save action and the Load action (see src/gui/serializer.h). 43 * 44 * The data structures in SKGraph can be generated by program, as in Roxdoku 45 * and Classic Sudoku, or loaded from XML files in the src/shapes sub-directory. 46 * See the methods initSudoku(), initRoxdoku() and initCustom() in SKGraph. 47 * 48 * The basic attributes are: 49 * 50 * order The number of symbols (digits or letters) to be used when 51 * solving a puzzle of this type and size (e.g. 9, but can be 52 * 4, 16 or 25). 53 * sizeX The number of cells in the X direction. 54 * sizeY The number of cells in the Y direction. 55 * sizeZ The number of cells in the Z direction. 56 * 57 * A conventional two-dimensional type of puzzle has a square grid, where 58 * sizeX = sizeY and sizeZ = 1. A three-dimensional type of puzzle (Roxdoku) 59 * has a three-dimensional grid with sizeZ > 1. 60 * 61 * The actual contents of a puzzle or solution are represented as a vector of 62 * integers (see classes Puzzle and SudokuBoard). SKGraph provides methods to 63 * convert both ways between XYZ co-ordinates and a cell index (or cell number) 64 * in a vector representing a puzzle or solution. The total size of the vector 65 * is (sizeX * sizeY * sizeZ) cells, but in some types of puzzle not all cells 66 * are used (e.g. the gaps between the five sub-grids of a Samurai puzzle). 67 * 68 * Finally, the cells are organised into groups (or cliques) which represent 69 * everything that needs to be known about the rules and structure of a 70 * particular type of puzzle. Each group or clique has as many members as 71 * there are symbols in the puzzle (i.e. that number = order). Each member 72 * of a group is a cell number (or index) representing a cell that is in the 73 * group. A group may represent a row, a column, a block of some shape (not 74 * necessarily square) or a plane within a 3-D grid. The fact that each 75 * row, column, block or plane must contain each symbol exactly once is the 76 * cardinal rule of Sudoku puzzles in general. 77 * 78 * For example, the XSudoku puzzle type has order 9 and 29 groups (or cliques) 79 * of 9 cells each: 9 rows, 9 columns and 9 blocks 3x3 square, plus 2 diagonals, 80 * which must also contain the numbers 1 to 9 in that type of Sudoku. A Roxdoku 81 * puzzle of order 16 has a cubic grid containing 12 planes, each 4x4 cells 82 * square and each having 16 cells to be filled with the letters A to P. There 83 * are three sets of 4 planes, which are perpendicular to the X, Y and Z 84 * directions respectively. 85 * 86 * For brevity and the convenience of classes using SKGraph, the groups or 87 * cliques are organised into high-level structures such as a square grid (with 88 * rows and columns, but with or without square blocks), a large NxNxN cube or a 89 * special block, such as a diagonal in XSudoku or an irregularly shaped block 90 * in jigsaw-type puzzles. These structures also make it easier to write XML 91 * files for new 2-D puzzle shapes and open the way for 3-D puzzles containing 92 * more than one NxNxN cube overlapping in various ways. 93 * 94 * Cages, introduced in May-June 2015, are a new data-structure to support 95 * Killer Sudoku and Mathdoku (aka KenKen TM) types of puzzle. A cage is an 96 * irregular group of cells with size 1 to puzzle-order. Cages are imposed over 97 * a Latin Square of digits, as used in 2-D Sudokus. A cage of size 1 is 98 * equivalent to a clue or given value in a Sudoku. Cages of size 2 or more 99 * provide the rest of the clues. In Mathdoku, each such cage has an arithmetic 100 * operator (+-x/) and a value that is calculated, using that operator and 101 * the hidden solution-values of the cells in the cage. The user has to work 102 * out what the solutions are from the clues in the cages and the regular 103 * Sudoku rules for rows and columns (but not blocks). In Killer Sudoku, there 104 * are the usual 3x3 or 2x2 Sudoku blocks and the only operator is addition. 105 * Note that a Mathdoku puzzle can have any size from 3x3 up to 9x9, but a 106 * Killer Sudoku can have sizes 4x4 or 9x9 only. 107 */ 108 109 class SKGraph 110 { 111 public: 112 explicit SKGraph(int order = 9, ksudoku::GameType type = ksudoku::TypeSudoku); 113 virtual ~SKGraph(); 114 order()115 inline int order() const { return m_order; } base()116 inline int base() const { return m_base; } 117 sizeX()118 inline int sizeX() const { return m_sizeX; } sizeY()119 inline int sizeY() const { return m_sizeY; } sizeZ()120 inline int sizeZ() const { return m_sizeZ; } 121 size()122 inline int size() const { return m_sizeX * m_sizeY * m_sizeZ; } 123 124 inline int cellIndex(uint x, uint y, uint z = 0) const 125 { 126 return (x * m_sizeY + y) * m_sizeZ + z; 127 } cellPosX(int i)128 inline int cellPosX(int i) const { 129 if(! (m_sizeX && m_sizeY && m_sizeZ)) return 0; 130 return i / m_sizeZ / m_sizeY; 131 } cellPosY(int i)132 inline int cellPosY(int i) const { 133 if(! (m_sizeX && m_sizeY && m_sizeZ)) return 0; 134 return i / m_sizeZ % m_sizeY; 135 } cellPosZ(int i)136 inline int cellPosZ(int i) const { 137 if(! (m_sizeX && m_sizeY && m_sizeZ)) return 0; 138 return i % m_sizeZ; 139 } 140 141 // Get the total number of groups (cliques) -- rows, columns and blocks. cliqueCount()142 inline int cliqueCount() const { return m_cliques.count(); } 143 144 // Get a list of the cells in a group (clique). clique(int i)145 QVector<int> clique(int i) const { return m_cliques[i]; } 146 147 // Get a list of the groups (cliques) to which a cell belongs. 148 const QList<int> cliqueList(int cell) const; 149 150 // High-level structure types are a square grid, a large cube or a 151 // special or irregularly-shaped group, as in XSudoku or jigsaw types. 152 enum StructureType { SudokuGroups, RoxdokuGroups, Clique }; 153 154 // Get the total number of high-level structures. structureCount()155 inline int structureCount() const 156 { return m_structures.count()/3; } 157 158 // Get the type of a structure (square, cube, etc.). structureType(int n)159 inline StructureType structureType(int n) const 160 { return (StructureType) m_structures.at(n*3); } 161 162 // Get the position of a structure within the puzzle-vector. structurePosition(int n)163 inline int structurePosition(int n) const 164 { return m_structures.at(n*3 + 1); } 165 166 // Find out whether a 2-D structure has square blocks or not. structureHasBlocks(int n)167 inline bool structureHasBlocks(int n) const 168 { return m_structures.at(n*3 + 2); } 169 170 // Add a special or irregularly-shaped group to the list of structures. 171 void addCliqueStructure(const QVector<int> &data); 172 173 // Add a cage (applicable to Mathdoku or Killer Sudoku puzzles only). 174 void addCage(const QVector<int> &cage, CageOperator cageOperator, 175 int cageValue); 176 177 // Remove a cage (when keying in a Mathdoku or Killer Sudoku puzzle). 178 void dropCage(int cageNum); 179 180 // Get the total number of cages (0 if not Mathdoku or Killer Sudoku).. cageCount()181 inline int cageCount() const { return m_cages.count(); } 182 183 // Get a list of the cells in a cage. cage(int i)184 QVector<int> cage(int i) const { return m_cages.at(i)->cage; } 185 186 // Get the mathematical operator of a cage (+ - * or /). cageOperator(int i)187 CageOperator cageOperator(int i) const 188 { return m_cages.at(i)->cageOperator; } 189 190 // Get the calculated value of the cells in a cage. cageValue(int i)191 int cageValue(int i) const { return m_cages.at(i)->cageValue; } 192 193 // Get the top left cell in a cage. cageTopLeft(int i)194 int cageTopLeft(int i) const { return m_cages.at(i)->cageTopLeft; } 195 196 // Clear cages used in a previous puzzle, if any. 197 void clearCages(); 198 name()199 inline const QString & name() const { return m_name; } type()200 inline ksudoku::GameType type() const { return m_type; } specificType()201 virtual SudokuType specificType() const { return m_specificType; } 202 203 void initSudoku(); 204 void initSudokuGroups(int pos = 0, bool withBlocks = true); 205 206 void initRoxdoku(); 207 void initRoxdokuGroups(int pos = 0); 208 209 void initCustom(const QString & name, SudokuType specificType, 210 int order, int sizeX, int sizeY, int sizeZ, int ncliques); 211 void endCustom(); 212 emptyBoard()213 inline const BoardContents & emptyBoard() const { return m_emptyBoard; } 214 215 protected: 216 int m_order; 217 int m_base; 218 int m_sizeX, m_sizeY, m_sizeZ; 219 220 // High-level structures, 3 values/structure: structure type (see enum), 221 // structure position and whether the structure includes square blocks. 222 QVector<int> m_structures; 223 224 // Low-level structures (rows, columns and blocks) also known as groups. 225 QVector<QVector<int> > m_cliques; 226 227 QVector<int> m_cellIndex; // Index of cells to cliques. 228 QVector<int> m_cellCliques; // Second level of the index. 229 230 // Cages are for Mathdoku and Killer Sudoku puzzles only, else empty. 231 struct Cage { 232 QVector<int> cage; // The cells in the cage. 233 CageOperator cageOperator; // The mathematical operator. 234 int cageValue; // The value to be calculated. 235 int cageTopLeft; // The top-left (display) cell. 236 }; 237 QVector<Cage *> m_cages; 238 239 QString m_name; 240 ksudoku::GameType m_type; 241 SudokuType m_specificType; 242 243 BoardContents m_emptyBoard; 244 245 private: 246 void addClique(const QVector<int> &data); 247 248 // For efficiency, make an index from cells to the groups (cliques) 249 // where they belong. 250 void indexCellsToCliques(); 251 }; 252 253 #endif 254