File indexing completed on 2024-04-21 04:05:04

 /***************************************************************************
  *   Copyright 2005-2007 Francesco Rossi <redsh@email.it>                  *
  *   Copyright 2006      Mick Kappenburg <ksudoku@kappendburg.net>         *
  *   Copyright 2006-2008 Johannes Bergmeier <johannes.bergmeier@gmx.net>   *
  *   Copyright 2012      Ian Wadham <iandw.au@gmail.com>                   *
  *   Copyright 2015      Ian Wadham <iandw.au@gmail.com>                   *
  *                                                                         *
  *   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 SKGRAPH_H
 #define SKGRAPH_H
 
 #include <QList>
 #include <QString>
 
 #include "ksudoku_types.h"
 #include "globals.h"
 
 /**
  * @class SKGraph  skgraph.h
  * @short Generalized data representing a Sudoku puzzle size, shape and rules.
  *
  * SKGraph is an abstract class that can represent any type or size of Sudoku
  * puzzle layout, either in two dimensions or three.  Together with the Puzzle
  * class (see src/logic/puzzle.h) it forms the core of KSudoku and is used by
  * the puzzle generator/solver (see src/generator/sudokuboard.h), the 2-D and
  * 3-D views, the Save action and the Load action (see src/gui/serializer.h).
  *
  * The data structures in SKGraph can be generated by program, as in Roxdoku
  * and Classic Sudoku, or loaded from XML files in the src/shapes sub-directory.
  * See the methods initSudoku(), initRoxdoku() and initCustom() in SKGraph.
  *
  * The basic attributes are:
  *
  *      order     The number of symbols (digits or letters) to be used when
  *                solving a puzzle of this type and size (e.g. 9, but can be
  *                4, 16 or 25).
  *      sizeX     The number of cells in the X direction.
  *      sizeY     The number of cells in the Y direction.
  *      sizeZ     The number of cells in the Z direction.
  *
  * A conventional two-dimensional type of puzzle has a square grid, where
  * sizeX = sizeY and sizeZ = 1.  A three-dimensional type of puzzle (Roxdoku)
  * has a three-dimensional grid with sizeZ > 1.
  *
  * The actual contents of a puzzle or solution are represented as a vector of
  * integers (see classes Puzzle and SudokuBoard).  SKGraph provides methods to
  * convert both ways between XYZ co-ordinates and a cell index (or cell number)
  * in a vector representing a puzzle or solution.  The total size of the vector
  * is (sizeX * sizeY * sizeZ) cells, but in some types of puzzle not all cells
  * are used (e.g. the gaps between the five sub-grids of a Samurai puzzle).
  *
  * Finally, the cells are organised into groups (or cliques) which represent
  * everything that needs to be known about the rules and structure of a
  * particular type of puzzle.  Each group or clique has as many members as
  * there are symbols in the puzzle (i.e. that number = order).  Each member
  * of a group is a cell number (or index) representing a cell that is in the
  * group.  A group may represent a row, a column, a block of some shape (not
  * necessarily square) or a plane within a 3-D grid.  The fact that each
  * row, column, block or plane must contain each symbol exactly once is the
  * cardinal rule of Sudoku puzzles in general.
  *
  * For example, the XSudoku puzzle type has order 9 and 29 groups (or cliques)
  * of 9 cells each: 9 rows, 9 columns and 9 blocks 3x3 square, plus 2 diagonals,
  * which must also contain the numbers 1 to 9 in that type of Sudoku.  A Roxdoku
  * puzzle of order 16 has a cubic grid containing 12 planes, each 4x4 cells
  * square and each having 16 cells to be filled with the letters A to P.  There
  * are three sets of 4 planes, which are perpendicular to the X, Y and Z
  * directions respectively.
  *
  * For brevity and the convenience of classes using SKGraph, the groups or
  * cliques are organised into high-level structures such as a square grid (with
  * rows and columns, but with or without square blocks), a large NxNxN cube or a
  * special block, such as a diagonal in XSudoku or an irregularly shaped block
  * in jigsaw-type puzzles.  These structures also make it easier to write XML
  * files for new 2-D puzzle shapes and open the way for 3-D puzzles containing
  * more than one NxNxN cube overlapping in various ways.
  *
  * Cages, introduced in May-June 2015, are a new data-structure to support
  * Killer Sudoku and Mathdoku (aka KenKen TM) types of puzzle. A cage is an
  * irregular group of cells with size 1 to puzzle-order. Cages are imposed over
  * a Latin Square of digits, as used in 2-D Sudokus. A cage of size 1 is
  * equivalent to a clue or given value in a Sudoku. Cages of size 2 or more
  * provide the rest of the clues. In Mathdoku, each such cage has an arithmetic
  * operator (+-x/) and a value that is calculated, using that operator and
  * the hidden solution-values of the cells in the cage. The user has to work
  * out what the solutions are from the clues in the cages and the regular
  * Sudoku rules for rows and columns (but not blocks). In Killer Sudoku, there
  * are the usual 3x3 or 2x2 Sudoku blocks and the only operator is addition.
  * Note that a Mathdoku puzzle can have any size from 3x3 up to 9x9, but a
  * Killer Sudoku can have sizes 4x4 or 9x9 only.
  */
 
 class SKGraph
 {
 public:
     explicit SKGraph(int order = 9, ksudoku::GameType type = ksudoku::TypeSudoku);
     virtual ~SKGraph();
 
     inline int order() const { return m_order; }
     inline int base()  const { return m_base;  }
 
     inline int sizeX() const { return m_sizeX; }
     inline int sizeY() const { return m_sizeY; }
     inline int sizeZ() const { return m_sizeZ; }
 
     inline int size()  const { return m_sizeX * m_sizeY * m_sizeZ; }
 
     inline int cellIndex(uint x, uint y, uint z = 0) const
     {
         return (x * m_sizeY + y) * m_sizeZ + z;
     }
     inline int cellPosX(int i) const {
         if(! (m_sizeX && m_sizeY && m_sizeZ)) return 0;
         return i / m_sizeZ / m_sizeY;
     }
     inline int cellPosY(int i) const {
         if(! (m_sizeX && m_sizeY && m_sizeZ)) return 0;
         return i / m_sizeZ % m_sizeY;
     }
     inline int cellPosZ(int i) const {
         if(! (m_sizeX && m_sizeY && m_sizeZ)) return 0;
         return i % m_sizeZ;
     }
 
     // Get the total number of groups (cliques) -- rows, columns and blocks.
     inline int cliqueCount()   const { return m_cliques.count(); }
 
     // Get a list of the cells in a group (clique).
     QList<int> clique(int i) const { return m_cliques[i]; }
 
     // Get a list of the groups (cliques) to which a cell belongs.
     const QList<int> cliqueList(int cell) const;
 
     // High-level structure types are a square grid, a large cube or a
     // special or irregularly-shaped group, as in XSudoku or jigsaw types.
     enum StructureType { SudokuGroups, RoxdokuGroups, Clique };
 
     // Get the total number of high-level structures.
     inline int structureCount() const
                 { return m_structures.count()/3; }
 
     // Get the type of a structure (square, cube, etc.).
     inline StructureType structureType(int n) const
                 { return (StructureType) m_structures.at(n*3); }
 
     // Get the position of a structure within the puzzle-vector.
     inline int           structurePosition(int n) const
                 { return m_structures.at(n*3 + 1); }
 
     // Find out whether a 2-D structure has square blocks or not.
     inline bool          structureHasBlocks(int n) const
                 { return m_structures.at(n*3 + 2); }
 
     // Add a special or irregularly-shaped group to the list of structures.
     void addCliqueStructure(const QList<int> &data);
 
     // Add a cage (applicable to Mathdoku or Killer Sudoku puzzles only).
     void addCage(const QList<int> &cage, CageOperator cageOperator,
                      int cageValue);
 
     // Remove a cage (when keying in a Mathdoku or Killer Sudoku puzzle).
     void dropCage(int cageNum);
 
     // Get the total number of cages (0 if not Mathdoku or Killer Sudoku)..
     inline int cageCount() const { return m_cages.count(); }
 
     // Get a list of the cells in a cage.
     QList<int> cage(int i) const { return m_cages.at(i)->cage; }
 
     // Get the mathematical operator of a cage (+ - * or /).
     CageOperator cageOperator(int i) const
                                          { return m_cages.at(i)->cageOperator; }
 
     // Get the calculated value of the cells in a cage.
     int cageValue(int i) const { return m_cages.at(i)->cageValue; }
 
     // Get the top left cell in a cage.
     int cageTopLeft(int i) const { return m_cages.at(i)->cageTopLeft; }
 
     // Clear cages used in a previous puzzle, if any.
     void clearCages();
 
     inline const QString & name()     const { return m_name; }
     inline ksudoku::GameType type()   const { return m_type; }
     virtual SudokuType specificType() const { return m_specificType; }
 
     void initSudoku();
     void initSudokuGroups(int pos = 0, bool withBlocks = true);
 
     void initRoxdoku();
     void initRoxdokuGroups(int pos = 0);
 
     void initCustom(const QString & name, SudokuType specificType,
           int order, int sizeX, int sizeY, int sizeZ);
     void endCustom();
 
     inline const BoardContents & emptyBoard() const { return m_emptyBoard; }
 
 protected:
     int m_order;
     int m_base;
     int m_sizeX, m_sizeY, m_sizeZ;
 
     // High-level structures, 3 values/structure: structure type (see enum),
     // structure position and whether the structure includes square blocks.
     QList<int>          m_structures;
 
     // Low-level structures (rows, columns and blocks) also known as groups.
     QList<QList<int> >  m_cliques;
 
     QList<int>          m_cellIndex;    // Index of cells to cliques.
     QList<int>          m_cellCliques;  // Second level of the index.
 
     // Cages are for Mathdoku and Killer Sudoku puzzles only, else empty.
     struct Cage {
         QList<int>      cage;       // The cells in the cage.
         CageOperator    cageOperator;   // The mathematical operator.
         int             cageValue;      // The value to be calculated.
         int             cageTopLeft;    // The top-left (display) cell.
     };
     QList<Cage *>       m_cages;
 
     QString             m_name;
     ksudoku::GameType   m_type;
     SudokuType          m_specificType;
 
     BoardContents       m_emptyBoard;
 
 private:
     void addClique(const QList<int> &data);
 
     // For efficiency, make an index from cells to the groups (cliques)
     // where they belong.
     void indexCellsToCliques();
 };
 
 #endif