Backtracking Algorithm

What is Backtracking Algorithm?

Backtracking is an algorithm that searches for possible combinations to solve computational problems. It incrementally builds candidates and removes those that do not satisfy given constraints. This technique is very useful in situations where you have to choose a feasible solution among multiple possible results.

This algorithm is considered better and more efficient than the Brute Force approach. Unlike Bruteforce, which tries all possible solutions, Backtracking focuses on finding only one final solution according to given constraints. It also saves time and memory by undoing the last step (backtrack) and trying another option after reaching a dead-end. Additionally, it stops as soon as a valid solution is found.

Backtracking is a widely used technique because it can solve complex problems without exhaustive resource consumption. It is particularly useful for problems where numerous constraints must be satisfied, such as Sudoku, n queen problem, and scheduling. By intelligently navigating through potential solutions, backtracking can find an answer that satisfies all conditions. This makes it invaluable for tasks that require both precision and efficiency.

How Backtracking Algorithm Works?

Backtracking algorithms are a problem-solving technique that involves finding valid solutions step by step. If the constraints of a step do not satisfy certain conditions, the algorithm returns to the previous step.

It then continues with other possible combinations that satisfy the given constraints. Since numerous possible combinations exist, it selects one of the most satisfactory options and solves the problem sequentially. This algorithmic technique is useful when you need to resolve one or more possible options. Withdrawal means canceling your choice whenever a situation arises that does not yield a valid solution.

The backtracking algorithm has the following steps in general to solve a problem:

Step 1) Initialization: Start with an initial empty/partial solution.

Step 2) Selection: Based on specific criteria and constraints, select one option to extend the current solution.

Step 3) Exploration: Recursively solve by considering the chosen candidate and moving forward in the problem-solving process.

Step 4) Constraint Check: Check if the current partial solution violates any constraints at every step. If it does, backtrack to the previous step and try a different candidate.

Step 5) Termination: The backtracking process stops when either a valid solution is found, or all combinations have been exhausted.

Step 6) Backtracking: If the current option does not solve the given problem, it returns to the previous state. It then considers the new option to solve the given problem.

Step 7) Repeat: Continue with these steps until the problem is resolved or all options are explored.

Recursive Nature of Backtracking Algorithm

Backtracking algorithms are recursive in nature. This means the algorithm calls itself with different parameters until it finds a solution or has tested all possibilities:

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Common Terms Related To Backtracking Problems

These are some basic terms related to the Backtracking technique:

Solution Vector: Represents solutions as n-tuples, like (X1, X2, …, Xn).
Constraints: Rules limiting X values, implicit and explicit.
Solution Space: All valid X values satisfying explicit constraints.
State Space Tree: Represents the solution space as a tree.
State Space: Describes paths in a state space tree.
Problem State: Nodes in the search tree representing partial solutions.
Solution States: States forming valid solution tuples in S.
Answer States: Satisfy implicit constraints and yield desired solutions.
Promising Node: Leads to desired solutions and remains feasible.
Non-Promising Node: Leads to infeasible states, not explored further.
Live Node: Generated with unexplored children.
E-Node: Live node with ongoing child generation.
Dead Node: No further expansion of all children generated.
Depth-First Node Generation: Uses the latest live node as the next E-node.
Bounding Function: Maximizes or minimizes B(x1, x2, …, Xa) for optimization.
Static Trees: Tree formulation independent of the problem instance.
Dynamic Trees: Tree formulation varies with the problem instance.

When To Use A Backtracking Algorithm?

We can choose the Backtracking technique to solve a complex problem when:

Many choices exist: Backtracking is suitable if many options exist at each step of the problem-solving process. These options may relate to the selection of items and moves.
No clear best choice: When there is insufficient information to determine the best choice among available options, a Backtracking algorithm can be utilized.
The decision leads to more choices: You can choose the backtracking technique to review choices systematically.
Need to explore all the possible solutions: Backtracking systematically explores all the solutions by making a series of decisions built upon each other.

Types of Backtracking Problems

There are three types of problems in backtracking algorithms: decision problems, optimization problems, and enumeration problems. Let’s learn about them below.

Decision Problem: In this type of problem, the goal is to determine whether a feasible solution exists. We check “yes” and “no” answers. For example, the n-queens problem. It is a decision problem that examines the likelihood of placing n queens on an n × n chessboard without attacking each other.
Optimization Problem: In optimization problems, the goal is to find the best possible solution among many options. This may involve determining the maximum and minimum values of a certain function or variable. For example, consider the backpack problem, where the objective is to maximize the total value of the items in the bag while adhering to its weight limit.
Enumeration Problem: Its objective is to find all the possible solutions to a given problem. We list every valid option without any omissions. An example would be generating all possible letter combinations from a given set of characters.

Applications of Backtracking & Examples

There are various applications of Backtracking. Some of them are explained below with their pseudo code.

Sudoku Solver: This problem contains a 3×3 subgrid with duplicate numbers. The backtracking technique will show the solution returns false, indicating the need for a different number placement.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

N-Queen Problem: The backtracking approach determines how to present queens on an N × N chessboard so that none of them threaten each other.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

Subset Sum Problem: It is used to find the subset of numbers from a given set that adds up to a particular target sum.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

Hamiltonian Cycle Problem: Backtracking can be applied to find a closed tour in a graph that visits each vertex exactly once.
Rat in Maze Problem: The backtracking technique is used to find the path of a rat from the starting point of the maze to the exit.

Advantages and Disadvantages of Backtracking Algorithm

Advantages of Backtracking Algorithm

Backtracking techniques are used to solve complex problems. It has many advantages like:

The backtracking technique is efficient for handling constraints.
This method is good for solving optimization problems.
The technique works for various types of problems.
This procedure can help review all possible solutions.
Since it backtracks, it saves more memory than the Bruteforce technique.

Disadvantages of Backtracking Algorithm

Backtracking techniques also have some limitations, such as time complexity. This technique has the following drawbacks:

There is no guaranteed solution.
It is slower because of many combinations.
It has high time complexity because of many possibilities.
It is unsuitable for real-time constraints as finding the best solution may take a long time.
Efficiency depends on the level of complexity of the problem.

Difference Between Backtracking And Recursion

Recursion	Backtracking
Calls itself until the base case is reached.	Uses recursion to review all possibilities until the best feasible result is found.
Bottom-up approach.	Top-down approach.
No value is discarded.	Non-viable solutions are rejected.

Conclusion

Backtracking is a useful algorithmic strategy for solving complex problems by systematically exploring feasible solutions and backtracking when necessary. We can expect backtracking techniques to enhance with improvements in computational power and algorithmic efficiency. These advancements will allow them to tackle larger and more complex problems efficiently.

In addition, machine learning models can guide backtracking decisions based on previously learned patterns.

All these technological innovations will revolutionize backtracking algorithms, making them a powerful and versatile tool for addressing complicated problems in various domains.