00001 /* 00002 * Sudoku: A plug-in for the Video Disk Recorder 00003 * 00004 * Copyright (C) 2005-2007, Thomas Günther <tom@toms-cafe.de> 00005 * 00006 * This program is free software; you can redistribute it and/or modify 00007 * it under the terms of the GNU General Public License as published by 00008 * the Free Software Foundation; either version 2 of the License, or 00009 * (at your option) any later version. 00010 * 00011 * This program is distributed in the hope that it will be useful, 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 * GNU General Public License for more details. 00015 * 00016 * You should have received a copy of the GNU General Public License along 00017 * with this program; if not, write to the Free Software Foundation, Inc., 00018 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 00019 */ 00020 00021 #ifndef VDR_SUDOKU_GENERATOR_H 00022 #define VDR_SUDOKU_GENERATOR_H 00023 00024 #include "sudoku.h" 00025 #include "backtrack.h" 00026 #include "puzzle.h" 00027 00028 00029 namespace Sudoku 00030 { 00031 00032 //--- class Sudoku::Generator ------------------------------------------------ 00033 00034 /** Implementation of a backtracking algorithm to generate Sudoku puzzles 00035 * 00036 * To generate Sudoku puzzles two nested backtracking algorithms are used. 00037 * First a random Sudoku solution is searched. Then the algorithm tries to 00038 * remove some numbers so that only the requested number of givens remains. 00039 * Each puzzle is checked with the nested solver algorithm if there is only 00040 * one solution. 00041 * 00042 * Example: 00043 * 00044 * \code 00045 * Puzzle puzzle; 00046 * Generator generator(puzzle, 36); 00047 * generator.find_next_solution(); 00048 * bool found = generator.solution_is_valid(); 00049 * \endcode 00050 */ 00051 class Generator : public BackTrack::Algorithm, public BackTrack::Solution 00052 { 00053 Puzzle& puzzle; 00054 Puzzle sudoku; 00055 unsigned int free_list[SDIM]; 00056 unsigned int free_count; 00057 Pos pos_list[SDIM]; 00058 unsigned int pos_count; 00059 bool symmetric; 00060 bool free_center; 00061 00062 public: 00063 00064 /** Constructor */ 00065 Generator(Puzzle& puzzle, unsigned int givens_count, 00066 bool symmetric = true, unsigned int max_iter = 0); 00067 00068 /** Set the element to the first sibling. */ 00069 virtual void set_first_at(unsigned int level); 00070 00071 /** Set the element to the next sibling. */ 00072 virtual void set_next_at(unsigned int level); 00073 00074 /** Reset the element. */ 00075 virtual void reset_at(unsigned int level); 00076 00077 /** Check if the element is set to the last sibling. */ 00078 virtual bool is_last_at(unsigned int level) const; 00079 00080 /** Check if the element is valid (following elements ignored). */ 00081 virtual bool is_valid_at(int level) const; 00082 00083 /** Check if the level is the last possible level. */ 00084 virtual bool is_last_level(int level) const; 00085 }; 00086 00087 } // namespace Sudoku 00088 00089 #endif // VDR_SUDOKU_GENERATOR_H