Introduction of 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."

​

Amity School of Engineering & Technology

• 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.

Amity School of Engineering & Technology

Types of backtracking algorithms�

There are two types of backtracking algorithms:

• Recursive backtracking algorithm
• Non - recursive backtracking algorithm

​

Amity School of Engineering & Technology

Recursive backtracking algorithm�

Algorithm backtrack (k)

// this scheme describes the backtracking process using

// recursion. On entering, the first k-1 values.

// x [1], x [2]… x [k-1] of the solution vector.

// x [1:n] have been assigned. X [] and n are global.

{

For (each x [k] £ T (x[1],……,x[k-1])do

{

If ( Bk (x [1], x[2],……….,x [k] != 0) then

{

If (x[1], x[2], …… , x[k] is a path to an answer node )

Then write (x[1:k]);

If(k<n) then backtrack (k+1);

} } }

Amity School of Engineering & Technology

• The solution vector (x1, x2... xk) is treated as a global array x [1: n]. All the possible elements for k^th position of the tuple that satisfy Bk are generated, one by one and then they are adjoined to the current vector (x1... xk-1). Each time xk is attached, a check is made to find whether a solution has been found. When the for loop completed, no more values for xk exist and the current copy of backtrack ends.

Amity School of Engineering & Technology

Non - Recursive backtracking algorithm�

Algorithm backtrack (k)

// this scheme describes the backtracking process.

// all solution are generated in x [1: n] and printed

// as soon as they are determined.

{

K = 1;

While (k != 0) do

{ If ( there remains are untried x[1] £ T ( x [1], x[2], ….., x [k-1]) and Bk (x[1], ….., x[k]) is true) then

{

If ( x[1], …., x[k] is a path to an answer node)

Then write ( x[1 : k]);

K = k+1; // consider the next set

}

Else k = k-1 ; // backtrack to the previous set } }

Amity School of Engineering & Technology

• T() here yields the set of all possible values that can be placed as the first component x1 of the solution vector. The component x1 will take values for which the bounding function B1 (x1) is true.
• Elements are generated here in a depth first manner.

​

Amity School of Engineering & Technology