Backtracking

The Backtracking is an algorithmic-method to solve a problem with an additional way. It uses a recursive approach to explain the problems. We can say that the backtracking is needed to find all possible combination to solve an optimization problem.

Backtracking is a systematic way of trying out different sequences of decisions until we find one that "works."

In the following Figure:

• Each non-leaf node in a tree is a parent of one or more other nodes (its children)
• Each node in the tree, other than the root, has exactly one parent

Generally, however, we draw our trees downward, with the root at the top.

A tree is composed of nodes.

Backtracking can understand of as searching a tree for a particular "goal" leaf node.

Backtracking is undoubtedly quite simple - we "explore" each node, as follows:

To "explore" node N:
 1. If N is a goal node, return "success"
 2. If N is a leaf node, return "failure"
 3. For each child C of N,
     Explore C
     If C was successful, return "success"
 4. Return "failure"

Backtracking algorithm determines the solution by systematically searching the solution space for the given problem. Backtracking is a depth-first search with any bounding function. All solution using backtracking is needed to satisfy a complex set of constraints. The constraints may be explicit or implicit.

Explicit Constraint is ruled, which restrict each vector element to be chosen from the given set.

Implicit Constraint is ruled, which determine which each of the tuples in the solution space, actually satisfy the criterion function.