What is Backtracking?

#algorithms #backtracking #graphs #computerscience

If you have studied graph theory, cybersecurity, compilers, advanced algorithms or artificial intelligence, don't matter what of these subjects you have learned, it is very likely that you have already faced or listened the term "backtracking" at least once.
Backtracking is a very famous brute force algorithm, and as the most of the brute force algorithms, it is based on the construction of state trees. In this article we will learn more about Backtracking, how it works, what are your use cases, your pros and cons, alternatives and examples to illustrate this algorithm working on.

Formal definition

Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem, when the solution is found, the program is interrupted. This algorithm performs a deep search in a tree, doing a top-down route and from left to right.
When this search fails, or a terminal node of the tree is found, the backtracking mechanism comes into operation. This procedure makes the system return along the same path in order to find alternative solutions, for each error that is found, the algorithm goes back one node of the tree.

Backtracking representation with graphs

This is a graphic representation of the Backtracking algorithm. The representation is a tree, its first node represents the initial state of the algorithm. The first node has tree child nodes, each one of them with two nodes.
Keep in mind that the Backtracking algorithm always starts from the top, and goes from the left first. It is very important to know that, so then you can correctly interpret the image.

In this representation we can see the algorithm working, supposing that we want to find the string "123", the scanner will advance to the next node (C1 or Checkpoint 1) if the character found is equal to 1, and back off to try with another node if it is not. This process will be recursively repeated many times, until the algorithm match the string "123".

N Queen problem

The N Queen Problem is a well-known mathematical proposition. The challenge is: try to place N queens on a board with N×N dimensions without one queen killing the other.
To solve this problem, we can use Backtracking as it is a case of trial and error, that we need to test multiple solutions until find the correct one.

Use cases

As was already mentioned in the introduction, this algorithm can be applied in different niches in the computer science area. So let's talk about the use cases for the Backtracking algorithm:

Cybersecurity

If you are a cybersecurity engineer, a student, or even a hacker, Backtracking might be a useful tool to solve some problems. You can use it to perform searches in a file system, you can also design algorithms to find breaches, and the most common use case of this algorithm for cybersecurity is to brute force passwords.

Compilers

To build a compiler you need to study a lot, plan the steps and define which strategies you will use. One mandatory step of a compiler project is the planning of the parser (syntactical analyser). At this stage of planning, you must define which parser implementation you will use, one of them is top down parser with backtracking, this implementation is not very popular because it has a very-high computational cost, but depending of your needs, you can choose it.

Artificial intelligence

In artificial intelligence, the Backtracking algorithm is used in decision, optimization and enumeration situations. Backtracking is a common solution, but AI researchers around the world are trying to build models and artificial intelligences without using the Backtracking. They are looking for a more lightweight solution, with a lower computational cost.

Pros and cons

Pros

Backtracking can almost solve any problems, due to its brute-force nature.
Can be used to find all the existing solutions if there exists for any problem.
It is a step-by-step representation of a solution to a given problem, which is very easy to understand.
Very easy to write the code, and also to debug.

Cons

It is very slow compared to other solutions.
Depending on the data that you have, there is the possibility to perform a very large search with Backtracking and at the end don't find any match to your search params.
Very-high computational cost, Backtracking is a recursive algorithm that consumes a lot from the memory and from the processor.
If you need an optimized algorithm, that is able to handle a large volume of data and find all the possible solutions consuming less computational resources and in a shorter interval of time, you may consider using the branch-and-bound algorithm.