File indexing completed on 2024-05-05 08:08:52
0001 /*************************************************************************** 0002 * Copyright 2005-2007 Francesco Rossi <redsh@email.it> * 0003 * Copyright 2006 Mick Kappenburg <ksudoku@kappendburg.net> * 0004 * Copyright 2006-2008 Johannes Bergmeier <johannes.bergmeier@gmx.net> * 0005 * Copyright 2012 Ian Wadham <iandw.au@gmail.com> * 0006 * Copyright 2015 Ian Wadham <iandw.au@gmail.com> * 0007 * * 0008 * This program is free software; you can redistribute it and/or modify * 0009 * it under the terms of the GNU General Public License as published by * 0010 * the Free Software Foundation; either version 2 of the License, or * 0011 * (at your option) any later version. * 0012 * * 0013 * This program is distributed in the hope that it will be useful, * 0014 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 0015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 0016 * GNU General Public License for more details. * 0017 * * 0018 * You should have received a copy of the GNU General Public License * 0019 * along with this program; if not, write to the * 0020 * Free Software Foundation, Inc., * 0021 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. * 0022 ***************************************************************************/ 0023 0024 #ifndef SKGRAPH_H 0025 #define SKGRAPH_H 0026 0027 #include <QList> 0028 #include <QString> 0029 0030 #include "ksudoku_types.h" 0031 #include "globals.h" 0032 0033 /** 0034 * @class SKGraph skgraph.h 0035 * @short Generalized data representing a Sudoku puzzle size, shape and rules. 0036 * 0037 * SKGraph is an abstract class that can represent any type or size of Sudoku 0038 * puzzle layout, either in two dimensions or three. Together with the Puzzle 0039 * class (see src/logic/puzzle.h) it forms the core of KSudoku and is used by 0040 * the puzzle generator/solver (see src/generator/sudokuboard.h), the 2-D and 0041 * 3-D views, the Save action and the Load action (see src/gui/serializer.h). 0042 * 0043 * The data structures in SKGraph can be generated by program, as in Roxdoku 0044 * and Classic Sudoku, or loaded from XML files in the src/shapes sub-directory. 0045 * See the methods initSudoku(), initRoxdoku() and initCustom() in SKGraph. 0046 * 0047 * The basic attributes are: 0048 * 0049 * order The number of symbols (digits or letters) to be used when 0050 * solving a puzzle of this type and size (e.g. 9, but can be 0051 * 4, 16 or 25). 0052 * sizeX The number of cells in the X direction. 0053 * sizeY The number of cells in the Y direction. 0054 * sizeZ The number of cells in the Z direction. 0055 * 0056 * A conventional two-dimensional type of puzzle has a square grid, where 0057 * sizeX = sizeY and sizeZ = 1. A three-dimensional type of puzzle (Roxdoku) 0058 * has a three-dimensional grid with sizeZ > 1. 0059 * 0060 * The actual contents of a puzzle or solution are represented as a vector of 0061 * integers (see classes Puzzle and SudokuBoard). SKGraph provides methods to 0062 * convert both ways between XYZ co-ordinates and a cell index (or cell number) 0063 * in a vector representing a puzzle or solution. The total size of the vector 0064 * is (sizeX * sizeY * sizeZ) cells, but in some types of puzzle not all cells 0065 * are used (e.g. the gaps between the five sub-grids of a Samurai puzzle). 0066 * 0067 * Finally, the cells are organised into groups (or cliques) which represent 0068 * everything that needs to be known about the rules and structure of a 0069 * particular type of puzzle. Each group or clique has as many members as 0070 * there are symbols in the puzzle (i.e. that number = order). Each member 0071 * of a group is a cell number (or index) representing a cell that is in the 0072 * group. A group may represent a row, a column, a block of some shape (not 0073 * necessarily square) or a plane within a 3-D grid. The fact that each 0074 * row, column, block or plane must contain each symbol exactly once is the 0075 * cardinal rule of Sudoku puzzles in general. 0076 * 0077 * For example, the XSudoku puzzle type has order 9 and 29 groups (or cliques) 0078 * of 9 cells each: 9 rows, 9 columns and 9 blocks 3x3 square, plus 2 diagonals, 0079 * which must also contain the numbers 1 to 9 in that type of Sudoku. A Roxdoku 0080 * puzzle of order 16 has a cubic grid containing 12 planes, each 4x4 cells 0081 * square and each having 16 cells to be filled with the letters A to P. There 0082 * are three sets of 4 planes, which are perpendicular to the X, Y and Z 0083 * directions respectively. 0084 * 0085 * For brevity and the convenience of classes using SKGraph, the groups or 0086 * cliques are organised into high-level structures such as a square grid (with 0087 * rows and columns, but with or without square blocks), a large NxNxN cube or a 0088 * special block, such as a diagonal in XSudoku or an irregularly shaped block 0089 * in jigsaw-type puzzles. These structures also make it easier to write XML 0090 * files for new 2-D puzzle shapes and open the way for 3-D puzzles containing 0091 * more than one NxNxN cube overlapping in various ways. 0092 * 0093 * Cages, introduced in May-June 2015, are a new data-structure to support 0094 * Killer Sudoku and Mathdoku (aka KenKen TM) types of puzzle. A cage is an 0095 * irregular group of cells with size 1 to puzzle-order. Cages are imposed over 0096 * a Latin Square of digits, as used in 2-D Sudokus. A cage of size 1 is 0097 * equivalent to a clue or given value in a Sudoku. Cages of size 2 or more 0098 * provide the rest of the clues. In Mathdoku, each such cage has an arithmetic 0099 * operator (+-x/) and a value that is calculated, using that operator and 0100 * the hidden solution-values of the cells in the cage. The user has to work 0101 * out what the solutions are from the clues in the cages and the regular 0102 * Sudoku rules for rows and columns (but not blocks). In Killer Sudoku, there 0103 * are the usual 3x3 or 2x2 Sudoku blocks and the only operator is addition. 0104 * Note that a Mathdoku puzzle can have any size from 3x3 up to 9x9, but a 0105 * Killer Sudoku can have sizes 4x4 or 9x9 only. 0106 */ 0107 0108 class SKGraph 0109 { 0110 public: 0111 explicit SKGraph(int order = 9, ksudoku::GameType type = ksudoku::TypeSudoku); 0112 virtual ~SKGraph(); 0113 0114 inline int order() const { return m_order; } 0115 inline int base() const { return m_base; } 0116 0117 inline int sizeX() const { return m_sizeX; } 0118 inline int sizeY() const { return m_sizeY; } 0119 inline int sizeZ() const { return m_sizeZ; } 0120 0121 inline int size() const { return m_sizeX * m_sizeY * m_sizeZ; } 0122 0123 inline int cellIndex(uint x, uint y, uint z = 0) const 0124 { 0125 return (x * m_sizeY + y) * m_sizeZ + z; 0126 } 0127 inline int cellPosX(int i) const { 0128 if(! (m_sizeX && m_sizeY && m_sizeZ)) return 0; 0129 return i / m_sizeZ / m_sizeY; 0130 } 0131 inline int cellPosY(int i) const { 0132 if(! (m_sizeX && m_sizeY && m_sizeZ)) return 0; 0133 return i / m_sizeZ % m_sizeY; 0134 } 0135 inline int cellPosZ(int i) const { 0136 if(! (m_sizeX && m_sizeY && m_sizeZ)) return 0; 0137 return i % m_sizeZ; 0138 } 0139 0140 // Get the total number of groups (cliques) -- rows, columns and blocks. 0141 inline int cliqueCount() const { return m_cliques.count(); } 0142 0143 // Get a list of the cells in a group (clique). 0144 QList<int> clique(int i) const { return m_cliques[i]; } 0145 0146 // Get a list of the groups (cliques) to which a cell belongs. 0147 const QList<int> cliqueList(int cell) const; 0148 0149 // High-level structure types are a square grid, a large cube or a 0150 // special or irregularly-shaped group, as in XSudoku or jigsaw types. 0151 enum StructureType { SudokuGroups, RoxdokuGroups, Clique }; 0152 0153 // Get the total number of high-level structures. 0154 inline int structureCount() const 0155 { return m_structures.count()/3; } 0156 0157 // Get the type of a structure (square, cube, etc.). 0158 inline StructureType structureType(int n) const 0159 { return (StructureType) m_structures.at(n*3); } 0160 0161 // Get the position of a structure within the puzzle-vector. 0162 inline int structurePosition(int n) const 0163 { return m_structures.at(n*3 + 1); } 0164 0165 // Find out whether a 2-D structure has square blocks or not. 0166 inline bool structureHasBlocks(int n) const 0167 { return m_structures.at(n*3 + 2); } 0168 0169 // Add a special or irregularly-shaped group to the list of structures. 0170 void addCliqueStructure(const QList<int> &data); 0171 0172 // Add a cage (applicable to Mathdoku or Killer Sudoku puzzles only). 0173 void addCage(const QList<int> &cage, CageOperator cageOperator, 0174 int cageValue); 0175 0176 // Remove a cage (when keying in a Mathdoku or Killer Sudoku puzzle). 0177 void dropCage(int cageNum); 0178 0179 // Get the total number of cages (0 if not Mathdoku or Killer Sudoku).. 0180 inline int cageCount() const { return m_cages.count(); } 0181 0182 // Get a list of the cells in a cage. 0183 QList<int> cage(int i) const { return m_cages.at(i)->cage; } 0184 0185 // Get the mathematical operator of a cage (+ - * or /). 0186 CageOperator cageOperator(int i) const 0187 { return m_cages.at(i)->cageOperator; } 0188 0189 // Get the calculated value of the cells in a cage. 0190 int cageValue(int i) const { return m_cages.at(i)->cageValue; } 0191 0192 // Get the top left cell in a cage. 0193 int cageTopLeft(int i) const { return m_cages.at(i)->cageTopLeft; } 0194 0195 // Clear cages used in a previous puzzle, if any. 0196 void clearCages(); 0197 0198 inline const QString & name() const { return m_name; } 0199 inline ksudoku::GameType type() const { return m_type; } 0200 virtual SudokuType specificType() const { return m_specificType; } 0201 0202 void initSudoku(); 0203 void initSudokuGroups(int pos = 0, bool withBlocks = true); 0204 0205 void initRoxdoku(); 0206 void initRoxdokuGroups(int pos = 0); 0207 0208 void initCustom(const QString & name, SudokuType specificType, 0209 int order, int sizeX, int sizeY, int sizeZ); 0210 void endCustom(); 0211 0212 inline const BoardContents & emptyBoard() const { return m_emptyBoard; } 0213 0214 protected: 0215 int m_order; 0216 int m_base; 0217 int m_sizeX, m_sizeY, m_sizeZ; 0218 0219 // High-level structures, 3 values/structure: structure type (see enum), 0220 // structure position and whether the structure includes square blocks. 0221 QList<int> m_structures; 0222 0223 // Low-level structures (rows, columns and blocks) also known as groups. 0224 QList<QList<int> > m_cliques; 0225 0226 QList<int> m_cellIndex; // Index of cells to cliques. 0227 QList<int> m_cellCliques; // Second level of the index. 0228 0229 // Cages are for Mathdoku and Killer Sudoku puzzles only, else empty. 0230 struct Cage { 0231 QList<int> cage; // The cells in the cage. 0232 CageOperator cageOperator; // The mathematical operator. 0233 int cageValue; // The value to be calculated. 0234 int cageTopLeft; // The top-left (display) cell. 0235 }; 0236 QList<Cage *> m_cages; 0237 0238 QString m_name; 0239 ksudoku::GameType m_type; 0240 SudokuType m_specificType; 0241 0242 BoardContents m_emptyBoard; 0243 0244 private: 0245 void addClique(const QList<int> &data); 0246 0247 // For efficiency, make an index from cells to the groups (cliques) 0248 // where they belong. 0249 void indexCellsToCliques(); 0250 }; 0251 0252 #endif