What is Backtracking?
Tags: algorithms, backtracking, graphs, computerscience
Published: 2021-07-31 23:33:07

![Backtracking image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4vucf2rm1x54mmn76zkk.png)
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.

&nbsp;

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

&nbsp;

## 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**.

![Backtracking representation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hy8v3et3f9ygt23b0l9p.png)

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

&nbsp;

## 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.
![N Queen backtracking](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eitqdp7s0d83butoorrv.png)

&nbsp;

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

&nbsp;

## Pros and cons
### Pros
<ul>
<li>Backtracking can almost solve any problems, due to its brute-force nature.</li>
<li>Can be used to find all the existing solutions if there exists for any problem.</li>
<li>It is a step-by-step representation of a solution to a given problem, which is very easy to understand.</li>
<li>Very easy to write the code, and also to debug.</li>
</ul>
### Cons
<ul>
<li>It is very slow compared to other solutions.</li>
<li>Depending on the data that you have, there is the possibility to perform a very large search with <b>Backtracking</b> and at the end don't find any match to your search params.</li>
<li>Very-high computational cost, <b>Backtracking</b> is a recursive algorithm that consumes a lot from the memory and from the processor.</li>
<li>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 <b>branch-and-bound</b> algorithm.</li>
</ul>

&nbsp;

## Brute force examples

* Selection sort
* Bubble sort
* Sequential search
* Verify string matches

&nbsp;

## Sources

https://www.youtube.com/watch?v=eIyagipwO8w

https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/#:~:text=The%20N%20Queen%20is%20the,two%20queens%20attack%20each%20other.&text=The%20expected%20output%20is%20a,for%20above%204%20queen%20solution.

https://pt.wikipedia.org/wiki/Backtracking

https://towardsdatascience.com/genetic-algorithm-vs-backtracking-n-queen-problem-cdf38e15d73f

https://intellipaat.com/community/52752/what-is-backtracking-in-artificial-intelligence

https://www.baeldung.com/cs/backtracking-algorithms

https://www.quora.com/What-are-the-advantages-and-disadvantages-of-a-backtracking-algorithm