path: root/puzzle.h

/*
 * Sudoku: A plug-in for the Video Disk Recorder
 *
 * Copyright (C) 2005-2010, Thomas Günther <tom@toms-cafe.de>
 *
 * 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 VDR_SUDOKU_PUZZLE_H
#define VDR_SUDOKU_PUZZLE_H

#include "sudoku.h"


/** Sudoku puzzle
 *
 * A Sudoku puzzle consists of 9 x 9 cells subdivided into 9 regions with 3 x 3
 * cells. The rules are simple. There have to be the numbers from 1 to 9 in
 * every row, column and region.
 */
namespace Sudoku
{
  class History;


  /** Regions, rows/columns and square dimension of the puzzle */
  enum
  {
    /** Regions dimension. Width and height of a region */
    RDIM = 3,

    /** Dimension. Number of cells in a row, column or region */
    DIM = RDIM * RDIM,

    /** Square dimension. Number of cells in the whole puzzle */
    SDIM = DIM * DIM
  };


  //--- class Sudoku::Pos ------------------------------------------------------

  /** Position in a Sudoku */
  class Pos
  {
    unsigned int pos;
  public:
    Pos(unsigned int col, unsigned int row) : pos(col + row * DIM) {}
    Pos(unsigned int pos = 0) : pos(pos) {}
    operator unsigned int() const { return pos; }
    static Pos first() { return 0; }
    static Pos last() { return SDIM-1; }
    Pos next() const { return pos + 1; }
    unsigned int col() const { return pos % DIM; }
    unsigned int row() const { return pos / DIM; }
    unsigned int reg() const { return (col() / RDIM) + RDIM * (row() / RDIM); }
    static Pos center() { return SDIM / 2; }
    Pos symmetric() const { return SDIM - 1 - pos; }
    Pos prev_col() const { return col() > 0     ? pos - 1   : pos; }
    Pos next_col() const { return col() < DIM-1 ? pos + 1   : pos; }
    Pos prev_row() const { return row() > 0     ? pos - DIM : pos; }
    Pos next_row() const { return row() < DIM-1 ? pos + DIM : pos; }
    bool interacts_with(Pos other) const { return pos != other &&
      (col() == other.col() || row() == other.row() || reg() == other.reg()); }
  };


  //--- class Sudoku::Numbers --------------------------------------------------

  /** Numbers of a Sudoku */
  class Numbers
  {
    unsigned int content[SDIM];
    mutable char* numbers_dump;

    // prevent use of copy constructor and copy operator
    Numbers(const Numbers& other);
    Numbers& operator=(const Numbers& other);

  public:

    /** Constructor */
    Numbers(const char* dump = 0);

    /** Destructor */
    virtual ~Numbers();

    /** Get the numbers as dump */
    virtual const char* get_dump() const;

    /** Remove all numbers. */
    virtual void reset();

    /** Set numbers from contents of sudoku if marked in marks. */
    virtual void set_contents(const Numbers& sudoku, const bool marks[SDIM]);

    /** Set the number into this cell. */
    virtual void set(Pos pos, unsigned int number);

    /** Get the number from this cell. */
    virtual unsigned int get(Pos pos) const;

    /** Load numbers from a dump. */
    virtual void load_from_dump(const char* dump);
  };


  //--- class Sudoku::Puzzle ---------------------------------------------------

  /** Sudoku puzzle */
  class Puzzle : public Numbers
  {
    Numbers givens;
    Numbers marks;
    bool numbers[SDIM][DIM+1];
    unsigned int count[SDIM];
    mutable char* puzzle_dump;

    // prevent use of copy constructor and copy operator
    Puzzle(const Puzzle& other);
    Puzzle& operator=(const Puzzle& other);

  public:

    /** Constructor */
    Puzzle(const char* dump = 0);

    /** Constructor with generation of a random puzzle */
    Puzzle(unsigned int givens_count, bool symmetric = true);

    /** Destructor */
    virtual ~Puzzle();

    /** Get the puzzle as dump */
    virtual const char* get_dump() const;

    /** Reset the puzzle (including marks). */
    virtual void reset();

    /** Reset the puzzle (either with or without marks). */
    virtual void reset(bool clear_marks);

    /** Set the number into this cell. */
    virtual void set(Pos pos, unsigned int number);

    /** Load a puzzle from a dump. */
    virtual void load_from_dump(const char* dump);

    /** Generate a new puzzle. */
    void generate(unsigned int givens_count, bool symmetric = true);

    /** Set givens from contents of sudoku if marked in given_marks. */
    void set_givens(const Numbers& sudoku, const bool given_marks[SDIM]);

    /** Remove all givens. */
    void clear_givens();

    /** No cells set? */
    bool untouched() const;

    /** Is the number in this cell given? */
    bool given(Pos pos) const;

    /** Is there an error on this position? */
    bool error(Pos pos) const;

    /** Is the number in this cell ambiguous? */
    bool ambiguous(Pos pos) const;

    /** All cells set and no errors? */
    bool solved() const;

    /** Is this cell marked? */
    bool marked(Pos pos) const;

    /** Toggle the mark for this cell. */
    void toggle_mark(Pos pos);

    /** Get the next free cell with minimal possible numbers. */
    Pos next_cell(Pos pos = Pos::last()) const;

    /** Get the next possible number for this cell. */
    unsigned int next_number(Pos pos) const;

    /** Get the count of possible numbers for this cell. */
    unsigned int numbers_count(Pos pos) const;

    /** Is this number in this cell a possible number? */
    bool possible_number(Pos pos, unsigned int number) const;

private:

    /** Compute all possible numbers for this cell. */
    void compute_numbers(Pos pos);

    /** Is the number in this cell a possible number? */
    bool correct(Pos pos) const;
  };


  //--- class Sudoku::PuzzleGame -----------------------------------------------

  /** Sudoku puzzle game */
  class PuzzleGame : public Puzzle
  {
    Pos pos;
    History* history;

    // prevent use of copy constructor and copy operator
    PuzzleGame(const PuzzleGame& other);
    PuzzleGame& operator=(const PuzzleGame& other);

  public:

    /** Constructor */
    PuzzleGame(const char* dump = 0);

    /** Constructor with generation of a random puzzle */
    PuzzleGame(unsigned int givens_count, bool symmetric = true);

    /** Destructor */
    virtual ~PuzzleGame();

    /** Reset the puzzle (including marks). */
    virtual void reset();

    /** Reset the puzzle (either with or without marks). */
    virtual void reset(bool clear_marks);

    /** Set the number into the current cell, write action into history. */
    virtual void set_with_history(unsigned int number);

    /** Get the position of the current cell. */
    Pos get_pos() const;

    /** Set the position of the current cell. */
    void set_pos(Pos new_pos);

    /** Go one step backward in the history. */
    void backward();

    /** Go one step forward in the history. */
    void forward();
  };

} // namespace Sudoku

#endif // VDR_SUDOKU_PUZZLE_H