Follow Us:

# Let’s understand the Backtracking Algorithm in an easy way

A backtracking algorithm is a systematic method for finding all (or some) solutions to a problem, each incrementally building on the previous ones. It is an example of a brute-force algorithm. The name “backtracking” comes from the fact that the algorithm explores all possible options (states) until it finds a goal (a solution or a path to a solution).

Backtracking algorithms are often used in combinatorial optimization problems, such as the travelling salesman problem or the knapsack problem.

The general idea of backtracking is to construct a partial solution incrementally until all of the constraints of the problem are satisfied. If at any point it becomes apparent that the partial solution cannot be completed to a full solution, then the partial solution is abandoned and the algorithm backtracks to the previous step.

## Applications of Backtracking Algorithm:

The backtracking algorithm can be used to solve problems such as the eight queens problem, the sudoku puzzle, and the crossword puzzle.

### N-Queens Problem:

The N-queens problem is a classic example of a backtracking problem. The goal is to place N-queens on a chessboard in such a way that no queen is in danger of being captured by another queen.

The constraints of the problem are that no two queens can be in the same row, column, or diagonal.

The backtracking algorithm works by starting with an empty board and placing a queen in the first row. It then proceeds to the next row and attempts to place a queen in every column. If a queen can be placed safely in a column, the algorithm moves on to the next row. If a queen cannot be placed safely in a column, the algorithm backtracks to the previous row and tries a different column.

Once the algorithm has placed N-queens on the board, the solution is complete.

### Sudoku Puzzle:

The sudoku puzzle is a 9×9 grid that must be filled in with the numbers 1-9 in such a way that each row, column, and 3×3 sub-grid contains all of the numbers 1-9.

The backtracking algorithm can be used to solve the sudoku puzzle by starting with an empty grid. It then Proceeds to fill in the first row, one column at a time. If a number can be placed safely in a column, the algorithm moves on to the next column. If a number cannot be placed safely in a column, the algorithm backtracks to the previous column and tries a different number.

Once the algorithm has placed all of the numbers 1-9 in the grid, the solution is complete.

### Crossword Puzzle:

The crossword puzzle is a grid of white and black squares that must be filled in with words. The words must intersect at the black squares, and all of the white squares must be filled in.

The backtracking algorithm is a systematic way of trying to solve a crossword puzzle by exhaustively searching through all possible solutions until a correct solution is found. The algorithm works by starting with a partial solution and then incrementally adding letters to the solution until all the letters in the puzzle are used or it is determined that there is no correct solution. If the algorithm reaches a point where it is impossible to find a correct solution, it will backtrack to the last point where a correct solution was possible and try a different letter. This process is repeated until a correct solution is found or it is determined that there is no correct solution.

### Travelling salesman problem(nearest neighbor algorithm):

The travelling salesman problem (TSP) is the most popular problem in computer science. It is the problem of finding the shortest route that visits all of a given set of locations. The TSP has been studied for over a hundred years and is one of the most famous problems in mathematics and computer science.

The problem can be formulated as follows: given a set of locations, find the shortest route that visits all of the locations exactly once and returns to the starting point. The locations can be represented as points in a plane, and the length of the route can be measured using the Euclidean distance between the points.

The traveling salesman problem is a difficult problem to solve, and there is no known algorithm that always finds the optimal solution. However, there are a number of heuristic algorithms that can find good solutions to the problem. One of the most popular heuristic algorithms for the TSP is the **“nearest neighbor” algorithm**.

The nearest neighbor algorithm is a simple algorithm that finds a reasonable solution to the TSP. The algorithm works by starting at the first location and then selecting the nearest location that has not yet been visited. This location is then added to the route, and the process is repeated until all locations have been visited. The route found by this algorithm is usually not the shortest possible route, but it is usually quite close to the shortest route.

The nearest neighbor algorithm can be implemented in a recursive way, as follows:

```
function nearest neighbour(currentLocation, remaining locations)
if (remaining locations is empty)
return currentLocation
else
select the nearest location from remainingLocations
add the selected location to the route
return nearestNeighbour(selectedLocation, remainingLocations - selectedLocation)
end if
end function
```

The time complexity of the nearest neighbour algorithm is O(n^{2}), where n is the number of locations. This is because the algorithm needs to compute the distance between the current location and all of the remaining locations in order to select the nearest location.

The nearest neighbor algorithm can be improved by using a more sophisticated data structure to store the locations. For example, if the locations are stored in a sorted array, then the algorithm can be modified to run in **O(n)** time.

The following pseudocode shows the modified algorithm:

```
function nearestNeighbour(currentLocation, remainingLocations)
if (remainingLocations is empty)
return currentLocation
else
select the nearest location from remainingLocations
add the selected location to the route
return nearestNeighbour(selectedLocation, remainingLocations - selectedLocation)
end if
end function
```

The time complexity of the nearest neighbour algorithm can also be improved by using a more sophisticated selection method to choose the next location. For example, instead of always selecting the nearest location, the algorithm could select the location that minimizes the length of the remaining route.

The following pseudocode shows the modified algorithm:

```
function nearestNeighbour(currentLocation, remainingLocations)
if (remainingLocations is empty)
return currentLocation
else
select the location from remainingLocations that minimizes the length of the remaining route
add the selected location to the route
return nearestNeighbour(selectedLocation, remainingLocations - selectedLocation)
end if
end function
```

The time complexity of this modified algorithm is O(n^{2}) because the algorithm still needs to compute the distance between the current location and all of the remaining locations in order to select the next location.

The nearest neighbor algorithm can be further improved by using a more sophisticated data structure to store the locations and a more sophisticated selection method to choose the next location. However, the time complexity of the algorithm will always be O(n^{2}), because the algorithm needs to compute the distance between the current location and all of the remaining locations in order to select the next location.

### Backtracking Algorithm vs nearest neighbor algorithm:

Backtracking algorithms are a type of algorithm that helps find solutions to problems by trying to build solutions incrementally. Nearest neighbour algorithms are a type of algorithm that helps find solutions to problems by finding the closest solution to the problem. Both algorithms have their pros and cons, but which one is better?

Backtracking algorithms are a type of algorithm that helps find solutions to problems by trying to build solutions incrementally. This means that the algorithm will start with a partial solution and then try to improve upon it until it finds a complete solution. Backtracking algorithms can be used for problems such as finding the shortest path between two points or solving a Sudoku puzzle.

One advantage of backtracking algorithms is that they are relatively simple to understand and implement. Additionally, backtracking algorithms can often find solutions to problems very quickly. However, one downside of backtracking algorithms is that they can sometimes get stuck in what is known as a “local optimum”, where the algorithm has found a partial solution that is good, but not the best possible solution.

Nearest neighbor algorithms are a type of algorithm that helps find solutions to problems by finding the closest solution to the problem. This means that the algorithm will start with a given point and then find the closest point to it. Nearest neighbor algorithms can be used for problems such as clustering data points or finding the shortest path between two points.

One advantage of nearest neighbor algorithms is that they can often find very accurate solutions to problems. Additionally, nearest neighbor algorithms can be used for problems that are too large to be solved by backtracking algorithms. However, one downside of nearest neighbor algorithms is that they can be computationally expensive, meaning that they can take a long time to find a solution.

## Dynamic Programming vs Backtracking:

Dynamic Programming | Backtracking |

“Dynamic programming is a method for solving complex problems by breaking them down into smaller subproblems. It is an efficient way to use recursion to solve problems that can be broken down into smaller, independent parts. | Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution. “ |

Now I’ve got some questions about Backtracking, so let’s answer them too.

#### What Happens when the backtracking algorithm reaches a complete solution?

When the backtracking algorithm reaches a complete solution, it means that all the constraints have been satisfied and there is nothing left to be done. This is the point at which the algorithm terminates.

#### Backtracking Algorithm is better than the brute force technique or not?

Backtracking algorithms are typically more efficient than brute force techniques because they only explore a small subset of the possible solution space. Additionally, backtracking algorithms can often utilize problem-specific knowledge to prune the search space, further reducing the time and space complexity.

So, that’s all for this blog. I hope this blog was not bored you.

If you found this blog useful, then share this with your friends too.

See you in the next blog.