public class BacktrackingStrategy extends SolutionStrategy
function BACKTRACKING-SEARCH(csp) returns a solution, or failure
return BACKTRACK({ }, csp)
function BACKTRACK(assignment, csp) returns a solution, or failure
if assignment is complete then return assignment
var = SELECT-UNASSIGNED-VARIABLE(csp)
for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
if value is consistent with assignment then
add {var = value} to assignment
inferences = INFERENCE(csp, var, value)
if inferences != failure then
add inferences to assignment
result = BACKTRACK(assignment, csp)
if result != failure then
return result
remove {var = value} and inferences from assignment
return failure
Figure 6.5 A simple backtracking algorithm for constraint satisfaction
problems. The algorithm is modeled on the recursive depth-first search of
Chapter 3. By varying the functions SELECT-UNASSIGNED-VARIABLE and
ORDER-DOMAIN-VALUES, we can implement the general-purpose heuristic discussed
in the text. The function INFERENCE can optionally be used to impose arc-,
path-, or k-consistency, as desired. If a value choice leads to failure
(noticed wither by INFERENCE or by BACKTRACK), then value assignments
(including those made by INFERENCE) are removed from the current assignment
and a new value is tried.| Constructor and Description |
|---|
BacktrackingStrategy() |
| Modifier and Type | Method and Description |
|---|---|
protected DomainRestoreInfo |
inference(Variable var,
Assignment assignment,
CSP csp)
Primitive operation, which tries to prune out values from the CSP which
are not possible anymore when extending the given assignment to a
solution.
|
protected java.lang.Iterable<?> |
orderDomainValues(Variable var,
Assignment assignment,
CSP csp)
Primitive operation, ordering the domain values of the specified
variable.
|
protected Variable |
selectUnassignedVariable(Assignment assignment,
CSP csp)
Primitive operation, selecting a not yet assigned variable.
|
Assignment |
solve(CSP csp)
Returns a solution to the specified CSP, which specifies values for all
the variables such that the constraints are satisfied.
|
addCSPStateListener, fireStateChanged, fireStateChanged, removeCSPStateListenerpublic Assignment solve(CSP csp)
SolutionStrategysolve in class SolutionStrategycsp - a CSP to solveprotected Variable selectUnassignedVariable(Assignment assignment, CSP csp)
protected java.lang.Iterable<?> orderDomainValues(Variable var, Assignment assignment, CSP csp)
protected DomainRestoreInfo inference(Variable var, Assignment assignment, CSP csp)