blob: 963724a2dedd59154c307abef1263970f1669e57 (
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
|
/*
* Sudoku: A plugin for the Video Disk Recorder
*
* See the README file for copyright information and how to reach the author.
*
* $Id: backtrack.cpp 11 2005-10-28 01:00:01Z tom $
*/
#include "backtrack.h"
using namespace BackTrack;
//--- class BackTrack::Algorithm -----------------------------------------------
/** 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::Algorithm (Solution& solution, unsigned int max_iter) :
solution(solution), max_iter(max_iter)
{
first = true;
valid = false;
level = -1;
iter = 0;
}
/** Find the next valid solution to the problem.
*
* Repeated calls will find all solutions to a problem if multiple solutions
* exist.
*/
void Algorithm::find_next_solution()
{
valid = find_solution();
}
/** Is the current solution a valid solution? */
bool Algorithm::solution_is_valid()
{
return valid;
}
/** Reset the decision tree, i.e. the next call to 'find_solution' finds
* the first valid solution.
*/
void Algorithm::reset()
{
while (level >= 0)
{
solution.reset_at(level);
--level;
}
first = true;
}
/** Create the next leaf on the end of the solution. */
void Algorithm::create_left_leaf()
{
++level;
solution.set_first_at(level);
}
/** Backtrack through the decision tree until a node was found that hasn't
* been visited, return true if an unvisited node was found.
*/
bool Algorithm::visit_new_node()
{
// If the current node is the rightmost child we must backtrack
// one level because there are no more children at this level.
// So we back up until we find a non-rightmost child, then
// generate the child to the right. If we back up to the top
// without finding an unvisted child, then all nodes have been
// generated.
while (level >= 0 && solution.is_last_at(level))
{
solution.reset_at(level);
--level;
}
if (level < 0)
return false;
solution.set_next_at(level);
return true;
}
/** Find the next valid sibling of the last leaf, return true if a valid
* sibling was found.
*/
bool Algorithm::find_valid_sibling()
{
// If the current node is not valid pass through all siblings until either
// a valid sibling is found or the last sibling is reached.
for (;;)
{
++iter;
if (max_iter != 0 && iter > max_iter)
return false;
if (solution.is_valid_at(level))
return true;
if (solution.is_last_at(level))
return false;
solution.set_next_at(level);
}
}
/** Find the next valid solution to the problem, return true if a solution
* was found.
*/
bool Algorithm::find_solution()
{
// If first time, need to create a root.
if (first)
{
first = false;
level = -1;
if (solution.is_last_level(level))
return solution.is_valid_at(level);
create_left_leaf();
}
// Otherwise visit new node since solution contains the last solution.
else if (!visit_new_node())
return false;
for (;;)
{
if (find_valid_sibling())
{
if (solution.is_last_level(level))
return true;
create_left_leaf();
}
else if (max_iter != 0 && iter > max_iter)
return false;
else if (!visit_new_node())
return false; // The tree has been exhausted, so no solution exists.
}
}
|
