Backtracking Algorithms

The Backtracking Algorithm is a modified approach to the brute force algorithm. It is an algorithmic technique for finding all possible solutions recursively to some computational problems. These are notably constraint satisfaction problems. They build solutions incrementally and abandon the solutions that fail to satisfy the constraints of the problem at any time.

Backtracking can be defined as a general algorithmic technique that searches for every possible solution in order to solve a computational problem.

It is easy to get Backtracking and recursion confused. Their main difference is that, in recursion, the function calls itself until it satisfies a base case, whereas, in backtracking, recursion is used to explore all possibilities until the best solution for the problem is found.

There are three types of problems in backtracking, and they are:

1. Decision problem - Searching for a feasible solution

2. Optimization problem - Searching for the best solution

3. Enumeration problem - Searching for ALL feasible solutions

How do we know if a problem can be solved using Backtracking Algorithms?

Usually, a constraint satisfaction problem that has distinct and well-defined constraints on an objective solution, and incrementally builds solutions and abandons unsatisfactory solutions as soon as it has been determined that it cannot be used to solve the problem, can be solved by Backtracking. However, it is important to note that many of the problems that can be solved using Backtracking, can also be solved using other algorithms like Greedy Algorithms or Dynamic Programming. Effectively, the time complexity of the aforementioned algorithms outperforms the backtracking algorithm. This is because backtracking algorithms are generally exponential in both time and space. But, there are a few problems that could only be solved using backtracking algorithms so far.

Advantages of Backtracking Algorithms

1. In comparison with Dynamic programming, the backtracking approach is more effective in some cases only.

2. Backtracking algorithms are the best option for solving tactical problems

3. Backtracking is effective for constraint satisfaction problems

4. In greedy algorithms, finding the global optimal solution is a long procedure and depends on the user’s statements, however, in backtracking, it is easily solvable

5. Backtracking algorithms are simple to implement and easy to code

6. Different states are store in stacks so that data and information of solutions can be accessed and used at any time

7. The accuracy is guaranteed if backtracking algorithms are used

Disadvantages of Backtracking Algorithms

1. The backtracking approach is not efficient for solving strategic problems

2. The overall runtime of backtracking algorithms is generally high

3. To solve large problems, sometimes it requires other techniques such as branch and bound

4. A large amount of storage space is required to store different solutions and state functions in stacks

5. Thrashing is one of the problems of backtracking (thrashing is when a computer’s virtual memory resources are overused, leading to a state of page faults, which can cause applications to stop processing)

6. The basic approach detects conflicts much later than required

Applications of Backtracking

1. Artificial intelligence

2. Optimisation and tactical problems

3. Constraint satisfaction problem

4. Network communication

5. Materials engineering

6. Solving puzzles such as Sudoku, Crossword, the 8-queens puzzle, etc.

Article was written for CyberClubNPSi