BackTrack::Algorithm Class Reference
Implementation of a generic backtracking algorithm. More...
#include <backtrack.h>
Public Member Functions | |
| Algorithm (Solution &solution, unsigned int max_iter=0) | |
| Constructor. | |
| void | find_next_solution () |
| Find the next valid solution to the problem. | |
| bool | solution_is_valid () |
| Is the current solution a valid solution? | |
| void | reset () |
| Reset the decision tree, i.e. | |
Private Member Functions | |
| void | create_left_leaf () |
| Create the next leaf on the end of the solution. | |
| bool | visit_new_node () |
| Backtrack through the decision tree until a node was found that hasn't been visited, return true if an unvisited node was found. | |
| bool | find_valid_sibling () |
| Find the next valid sibling of the last leaf, return true if a valid sibling was found. | |
| bool | find_solution () |
| Find the next valid solution to the problem, return true if a solution was found. | |
Private Attributes | |
| Solution & | solution |
| bool | first |
| bool | valid |
| int | level |
| unsigned int | max_iter |
| unsigned int | iter |
Detailed Description
Implementation of a generic backtracking algorithm.
Definition at line 115 of file backtrack.h.
Constructor & Destructor Documentation
| Algorithm::Algorithm | ( | Solution & | solution, | |
| unsigned int | max_iter = 0 | |||
| ) |
Member Function Documentation
| void Algorithm::create_left_leaf | ( | ) | [private] |
Create the next leaf on the end of the solution.
Definition at line 73 of file backtrack.cpp.
References level, BackTrack::Solution::set_first_at(), and solution.
Referenced by find_solution().
| void Algorithm::find_next_solution | ( | ) |
Find the next valid solution to the problem.
Repeated calls will find all solutions to a problem if multiple solutions exist.
Definition at line 48 of file backtrack.cpp.
References find_solution(), and valid.
Referenced by Sudoku::Puzzle::generate(), generate_puzzle(), Sudoku::Generator::Generator(), Sudoku::Generator::is_valid_at(), solve_puzzle(), Test_Generator::test_GenerateNonSymmetricSudoku(), Test_Generator::test_GenerateSymmetricSudoku(), Test_BackTrack::test_PermutationBackTrack(), Test_Solver::test_SearchFirstSudoku(), Test_Solver::test_SearchRandomSudoku(), and Test_Solver::test_SolveHardSudoku().
| bool Algorithm::find_solution | ( | ) | [private] |
Find the next valid solution to the problem, return true if a solution was found.
Definition at line 124 of file backtrack.cpp.
References create_left_leaf(), find_valid_sibling(), first, BackTrack::Solution::is_last_level(), BackTrack::Solution::is_valid_at(), iter, level, max_iter, solution, and visit_new_node().
Referenced by find_next_solution().
| bool Algorithm::find_valid_sibling | ( | ) | [private] |
Find the next valid sibling of the last leaf, return true if a valid sibling was found.
Definition at line 104 of file backtrack.cpp.
References BackTrack::Solution::is_last_at(), BackTrack::Solution::is_valid_at(), iter, level, max_iter, BackTrack::Solution::set_next_at(), and solution.
Referenced by find_solution().
| void Algorithm::reset | ( | ) |
Reset the decision tree, i.e.
the next call to 'find_solution' finds the first valid solution.
Definition at line 62 of file backtrack.cpp.
References first, level, BackTrack::Solution::reset_at(), and solution.
| bool Algorithm::solution_is_valid | ( | ) |
Is the current solution a valid solution?
Definition at line 54 of file backtrack.cpp.
References valid.
Referenced by Sudoku::Puzzle::generate(), generate_puzzle(), Sudoku::Generator::Generator(), Sudoku::Generator::is_valid_at(), solve_puzzle(), Test_Generator::test_GenerateNonSymmetricSudoku(), Test_Generator::test_GenerateSymmetricSudoku(), Test_BackTrack::test_PermutationBackTrack(), Test_Solver::test_SearchFirstSudoku(), Test_Solver::test_SearchRandomSudoku(), and Test_Solver::test_SolveHardSudoku().
| bool Algorithm::visit_new_node | ( | ) | [private] |
Backtrack through the decision tree until a node was found that hasn't been visited, return true if an unvisited node was found.
Definition at line 82 of file backtrack.cpp.
References BackTrack::Solution::is_last_at(), level, BackTrack::Solution::reset_at(), BackTrack::Solution::set_next_at(), and solution.
Referenced by find_solution().
Member Data Documentation
bool BackTrack::Algorithm::first [private] |
Definition at line 118 of file backtrack.h.
Referenced by Algorithm(), find_solution(), and reset().
unsigned int BackTrack::Algorithm::iter [private] |
Definition at line 121 of file backtrack.h.
Referenced by Algorithm(), find_solution(), and find_valid_sibling().
int BackTrack::Algorithm::level [private] |
Definition at line 120 of file backtrack.h.
Referenced by Algorithm(), create_left_leaf(), find_solution(), find_valid_sibling(), reset(), and visit_new_node().
unsigned int BackTrack::Algorithm::max_iter [private] |
Definition at line 121 of file backtrack.h.
Referenced by find_solution(), and find_valid_sibling().
Solution& BackTrack::Algorithm::solution [private] |
Definition at line 117 of file backtrack.h.
Referenced by create_left_leaf(), find_solution(), find_valid_sibling(), reset(), and visit_new_node().
bool BackTrack::Algorithm::valid [private] |
Definition at line 119 of file backtrack.h.
Referenced by Algorithm(), find_next_solution(), and solution_is_valid().
The documentation for this class was generated from the following files:
