blob: 263e1dc06b2a2d079780f60aaf2c2a366cb5fb7d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
/*
* Sudoku: A plugin for the Video Disk Recorder
*
* See the README file for copyright information and how to reach the author.
*
* $Id: backtrack.h 11 2005-10-28 01:00:01Z tom $
*/
#ifndef VDR_SUDOKU_BACKTRACK_H
#define VDR_SUDOKU_BACKTRACK_H
#include "sudoku.h"
/** Generic backtracking algorithm
*
* Inspired by an article by Roger Labbe "Solving Combinatorial Problems with
* STL and Backtracking" in C/C++-Users Journal, February 2000, pp. 56-64.
*
* The solution to a combinatorial problem can be described as a sequence of
* decisions. The backtracking algorithm traverses the decision tree
* depth-first. Each solution of the problem is a path through the tree from the
* root to one leaf. The algorithm traverses the tree by changing the elements
* of the solution. An element passes through all siblings on a certain level,
* i.e. through all possible decisions. Each step is checked if it makes the
* solution invalid, in which case the traversal of the whole branch is
* cancelled. Otherwise the algorithm either goes one level deeper or if this is
* the last level it has found one valid solution. After the last sibling on a
* level has been processed the algorithm goes back one level. Finally all valid
* solutions have been found if it comes back to the root node.
*
* This implementation of the backtracking algorithm consists of two classes.
* The Algorithm class contains the generic backtracking algorithm itself. The
* Solution class is the virtual base class for all specific solution classes.
* To solve a certain problem the specific solution class has to inherit from
* Solution implementing all virtual methods.
*
* Example:
*
* \code
* class ColorStatesList : public Solution
* {
* int clist[NUMBER_STATES];
* void set_first_at(unsigned int level) { clist[level] = 0; }
* void set_next_at(unsigned int level) { ++clist[level]; }
* void reset_at(unsigned int level) {}
* bool is_last_at(unsigned int level) { return clist[level] >= LAST_COLOR; }
* bool is_valid_at(int level) { return check_all_neighbors_until(level); }
* bool is_last_level(int level) [ return level >= NUMBER_STATES-1; }
* ...
* };
*
* void find_all_solutions()
* {
* ColorStatesList color_states_list(...);
* Algorithm algorithm(color_states_list);
* algorithm.find_next_solution();
* while (algorithm.solution_is_valid())
* {
* // Do something with the solution.
* ...
* algorithm.find_next_solution();
* }
* }
* \endcode
*/
namespace BackTrack
{
//--- virtual base class BackTrack::Solution ---------------------------------
/** Virtual base class of solutions for the backtracking algorithm */
class Solution
{
public:
/** Destructor */
virtual ~Solution() {};
/** Set the element to the first sibling. */
virtual void set_first_at(unsigned int level) = 0;
/** Set the element to the next sibling. */
virtual void set_next_at(unsigned int level) = 0;
/** Reset the element. */
virtual void reset_at(unsigned int level) = 0;
/** Check if the element is set to the last sibling. */
virtual bool is_last_at(unsigned int level) const = 0;
/** Check if the element is valid (following elements ignored). */
virtual bool is_valid_at(int level) const = 0;
/** Check if the level is the last possible level. */
virtual bool is_last_level(int level) const = 0;
};
//--- class BackTrack::Algorithm ---------------------------------------------
/** Implementation of a generic backtracking algorithm */
class Algorithm
{
Solution& solution;
bool first;
bool valid;
int level;
unsigned int max_iter, iter;
public:
/** Constructor
*
* Constructs an backtracking algorithm to solve a problem. The problem is
* implemented in 'solution' which represents a path through the decision
* tree from the root to one leaf.
*/
Algorithm(Solution& solution, unsigned int max_iter = 0);
/** Find the next valid solution to the problem.
*
* Repeated calls will find all solutions to a problem if multiple solutions
* exist. Return true if a solution was found.
*/
void find_next_solution();
/** Is the current solution a valid solution? */
bool solution_is_valid();
/** Reset the decision tree, i.e. the next call to 'find_solution' finds
* the first valid solution.
*/
virtual void reset();
private:
/** Create the next leaf on the end of the solution. */
void create_left_leaf();
/** Backtrack through the decision tree until a node was found that hasn't
* been visited, return true if an unvisited node was found.
*/
bool visit_new_node();
/** Find the next valid sibling of the last leaf, return true if a valid
* sibling was found.
*/
bool find_valid_sibling();
/** Find the next valid solution to the problem, return true if a solution
* was found.
*/
bool find_solution();
};
} // namespace BackTrack
#endif // VDR_SUDOKU_BACKTRACK_H
|
