• Backtracking search is a form of depth-first search, which is commonly used for solving CSPs. Inference can be interwoven with search. CSPs are all commutative. A problem is commutative if the order of application of any given set of actions has no effect on the outcome. A depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign.

• Backtracking algorithm repeatedly chooses an unassigned variable, and then tries all values in the domain of that variable in turn, trying to find a solution. If an inconsistency is detected, then BACKTRACK returns failure, causing the previous call to try another value.

• There is no need to supply BACKTRACKING-SEARCH with a domain-specific initial state, action function, transition model, or goal test.

• BACKTRACKING-SARCH keeps only a single representation of a state and alters that representation rather than creating a new ones.

Algorithm

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
            inference <-- 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

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc