Backtracking Algorithm in Data Structures

Introduction to Backtracking Algorithm

• In backtracking, we always start with one possible choice out of many available choices and try to find out the solution of the problem if we are able to find the solution with the selected move then we will print the solution else we will backtrack and select some other option and try to solve the problem.

• It allows us to deal with situations in which a brute-force approach would lead to an impossible number of choices to consider.

So in the backtracking algorithm at each node, we try to eliminate the choices that are not possible and proceed further to recursively check only those choices that can contribute towards the solution.

How Backtracking Algorithms Works?

Backtracking is the technique to solve programs recursively. In backtracking problems, you will have a number of options and you must choose one of these options.

After you make your choice you will explore a new set of options, if you reach the feasible solution through those choices you will print the solution otherwise you will backtrack and return to explore the other paths and choices that can possibly lead to the solution.

For Instance: Consider the following space state tree. With the help of the below space state tree let's understand how the backtracking algorithm actually works.

We start from S which is the starting point of our problem. We go to find a solution to Y1 from intermediate point X1 and then we find that Y1 is not a feasible solution to our problem therefore we backtrack and go back to X1 via Y1 then go back to S and then again try to find out the feasible solution by following another path S->X2->Y2 and again we will find that Y2 is not a feasible solution so we will again return to S by following path Y2->X2->S and then we will ultimately reach out to feasible solution Y3 by following the path S->X3->Y3.

So we can summarise the backtracking algorithm as follows:

1. We select one possible path and try to move forward towards finding a feasible solution.
2. If we will reach a point from where we can’t move towards the solution then we will backtrack.
3. Again we try to find out the feasible solution by following other possible paths.

When to Use a Backtracking Algorithm?

Backtracking algorithms are ideally used when solving problems that involve making a sequence of choices, with each choice leading towards a potential solution. They are best suited for problems where the solution space is large and a brute-force approach is computationally impractical. This includes puzzles like Sudoku or the N-Queens problem, and decision-making problems such as finding shortest paths, subsets, or combinations. However, backtracking may not be optimal for problems with smaller decision spaces or those that can be solved more efficiently with other algorithms.

Types of Backtracking Problems

Before start solving the problem we must be able to recognize if it can be solved using a backtracking algorithm. There are the following types of problems that can be solved using backtracking:

1. Decision Problem: In this type of problem we always search for a feasible solution.
2. Optimization Problem: In this type of problem we always search for the best possible solution.
3. Enumeration Problem: In this type of problem we try to find all feasible solutions.

Example of Backtracking Algorithm

We will discuss N Queen example which is a very popular problem that can be solved using Backtracking. In the N Queen problem, we have to place N queens on an N×N chessboard such that no two queens can attack each other. We cannot place two queens in the same row or same column or same diagnol in order to avoid the attack. For instance, given below is the configuration for placing N queens on N*N chessboard where N=4.

In the output, we will print the binary matrix containing 1s where the queen can be placed, and the rest all cells will contain 0s.

Solution: The bruteforce approach of solving this problem is generating all possible configurations of queens on board and then printing the configuration which will satisfy the constraint. But the time complexity of this approach will be exponential as we have to generate all possible configurations. But we can improve the time complexity by using a backtracking algorithm.

In the backtracking algorithm, we will start from the leftmost column and one by one try to place queens in different columns. When we place a queen in a column, we will check if the queen that we have placed currently is clashing with other already placed queens. In the current column, if we are able to find a row for which it is safe to place a queen then we will mark this row and column as part of the solution. If we do not find such a row due to clashes then we will backtrack and return false.

Approach to Code: We will have a chessboard in the form of a 2d matrix in which we will try to place the queens. We will create the following three functions:

• solveNQueen(): This will be the recursive function to solve n queen problem. It will take two arguments, a board matrix, and a column number.
• isSafe_to_place(): This function will check if it is safe to place the queen in the current cell. It will take arguments board matric, current row, and current column.
• printOutput(): This function will print the output matrix.

Below is the C++ implementation of the above approach:

Time Complexity: O(N!), where ‘N’ is the number of queens. For the first column, we check ‘N’ rows, for the second column, we check 'N - 1 rows and so on. hence time complexity will be N * (N-1) * (N-2) …. i.e N!

Space Complexity: O(N^2), where ‘N’ is the number of queens. As we are using a 2-D array of size N rows and N columns, and also we will be using a recursion stack which will take linear space.

Backtracking Algorithm Applications

There are various applications of backtracking algorithms. Some of them are following:

• Maize solve the problem
• N- Queens problem
• Finding all Hamiltonian Paths present in the graph
• Subset Sum problem
• The Knight's Tour problem
• Word break problem
• Longest possible roue in matrix with hurdles
• Word search problem