Implementation of a backtracking algorithm to generate Sudoku puzzles. More...
#include <generator.h>
Public Member Functions | |
Generator (Puzzle &puzzle, unsigned int givens_count, bool symmetric=true, unsigned int max_iter=0) | |
Constructor. | |
virtual void | set_first_at (unsigned int level) |
Set the element to the first sibling. | |
virtual void | set_next_at (unsigned int level) |
Set the element to the next sibling. | |
virtual void | reset_at (unsigned int level) |
Reset the element. | |
virtual bool | is_last_at (unsigned int level) const |
Check if the element is set to the last sibling. | |
virtual bool | is_valid_at (int level) const |
Check if the element is valid (following elements ignored). | |
virtual bool | is_last_level (int level) const |
Check if the level is the last possible level. | |
Private Attributes | |
Puzzle & | puzzle |
Puzzle | sudoku |
unsigned int | free_list [SDIM] |
unsigned int | free_count |
Pos | pos_list [SDIM] |
unsigned int | pos_count |
bool | symmetric |
bool | free_center |
Implementation of a backtracking algorithm to generate Sudoku puzzles.
To generate Sudoku puzzles two nested backtracking algorithms are used. First a random Sudoku solution is searched. Then the algorithm tries to remove some numbers so that only the requested number of givens remains. Each puzzle is checked with the nested solver algorithm if there is only one solution.
Example:
Puzzle puzzle; Generator generator(puzzle, 36); generator.find_next_solution(); bool found = generator.solution_is_valid();
Definition at line 51 of file generator.h.
Generator::Generator | ( | Puzzle & | puzzle, | |
unsigned int | givens_count, | |||
bool | symmetric = true , |
|||
unsigned int | max_iter = 0 | |||
) |
Constructor.
Definition at line 35 of file generator.cpp.
References BackTrack::Algorithm::find_next_solution(), free_center, free_count, pos_count, pos_list, Sudoku::Puzzle::reset(), Sudoku::SDIM, BackTrack::Algorithm::solution_is_valid(), and sudoku.
bool Generator::is_last_at | ( | unsigned int | level | ) | const [virtual] |
Check if the element is set to the last sibling.
Implements BackTrack::Solution.
Definition at line 95 of file generator.cpp.
References free_count, free_list, and pos_count.
bool Generator::is_last_level | ( | int | level | ) | const [virtual] |
Check if the level is the last possible level.
Implements BackTrack::Solution.
Definition at line 137 of file generator.cpp.
References free_count.
bool Generator::is_valid_at | ( | int | level | ) | const [virtual] |
Check if the element is valid (following elements ignored).
Implements BackTrack::Solution.
Definition at line 102 of file generator.cpp.
References Sudoku::Pos::center(), BackTrack::Algorithm::find_next_solution(), free_center, free_count, free_list, pos_count, pos_list, puzzle, Sudoku::SDIM, Sudoku::Puzzle::set_givens(), BackTrack::Algorithm::solution_is_valid(), sudoku, Sudoku::Pos::symmetric(), and symmetric.
void Generator::reset_at | ( | unsigned int | level | ) | [virtual] |
void Generator::set_first_at | ( | unsigned int | level | ) | [virtual] |
Set the element to the first sibling.
Implements BackTrack::Solution.
Definition at line 76 of file generator.cpp.
References free_count, and free_list.
void Generator::set_next_at | ( | unsigned int | level | ) | [virtual] |
Set the element to the next sibling.
Implements BackTrack::Solution.
Definition at line 83 of file generator.cpp.
References free_count, and free_list.
bool Sudoku::Generator::free_center [private] |
Definition at line 60 of file generator.h.
Referenced by Generator(), and is_valid_at().
unsigned int Sudoku::Generator::free_count [private] |
Definition at line 56 of file generator.h.
Referenced by Generator(), is_last_at(), is_last_level(), is_valid_at(), set_first_at(), and set_next_at().
unsigned int Sudoku::Generator::free_list[SDIM] [private] |
Definition at line 55 of file generator.h.
Referenced by is_last_at(), is_valid_at(), set_first_at(), and set_next_at().
unsigned int Sudoku::Generator::pos_count [private] |
Definition at line 58 of file generator.h.
Referenced by Generator(), is_last_at(), and is_valid_at().
Pos Sudoku::Generator::pos_list[SDIM] [private] |
Definition at line 57 of file generator.h.
Referenced by Generator(), and is_valid_at().
Puzzle& Sudoku::Generator::puzzle [private] |
Definition at line 53 of file generator.h.
Referenced by is_valid_at().
Puzzle Sudoku::Generator::sudoku [private] |
Definition at line 54 of file generator.h.
Referenced by Generator(), and is_valid_at().
bool Sudoku::Generator::symmetric [private] |
Definition at line 59 of file generator.h.
Referenced by is_valid_at().