What is Backtracking? And why is it used?

Backtracking is an algorithm that searches for possible combinations in order to solve computational problems. It is used for solving problems recursively by building increments and removing solutions that do not satisfy given constraints. This technique finds a solution among all possible solutions.

Comparison with Brute-Force Approach:
Backtracking is an improvement technique of the Bruteforce technique. These are problem solving approaches. Backtracking is efficient because it backtracks whenever it fails to meet given constraints at any given point in time, but brute force techniques find all possible solutions. It means brute force covers everything, while backtracking techniques focus on finding only one solution according to given constraints. So backtracking stops when a valid solution is found, while Bruteforce checks all solutions. Hence, backtracking is more efficient than the brute force technique in terms of memory usage.

Importance of Backtracking Algorithm:
Backtracking is an important technique because it can solve more complex problems like Sudoku and scheduling. It can solve optimisation problems while satisfying many constraints. Backtracking is an important technique to solve complex problems with efficiency and completeness.

How Backtracking Algorithm Works

Backtracking algorithms are a technique for solving problems sequentially. It finds solutions step by step. If the constraints of some steps do not satisfy some constraints, then it goes back to the previous step or a partial solution.

This continues with other possible combinations satisfying the given constraints. Since there are many possible combinations, it chooses one of the satisfactory combinations. Then it solves the problem sequentially. This is useful when you need to resolve one or more possible options. Withdrawal means cancelling your choice whenever a situation arises that does not yield a valid solution.

General Algorithm
Backtracking algorithms have the following steps in general to solve a problem:

Initialization: Start with initial empty/partial solution.
Selection: Choose one available option to extend the current solution. This choice should be made based on certain criteria. Consider the constraints that must be met.
Exploration: Recursively solve by considering the chosen candidate and moving forward in the problem-solving process.
Constraint Check: At each step, check if the current partial solution violates any constraints. If it does, backtrack to the previous step and try a different candidate.
Termination: The algorithm terminates if a valid solution is found or done with all combinations.
Backtracking: If the current option does not solve the given problem, it goes back to the previous state and considers the new option to solve the given problem.
Repeat: Continue with these above steps till the problem is solved or done with all possible choices.

Recursive Nature of Backtracking Algorithm
Backtracking algorithms are recursive in nature. If the solution is invalid, it backtracks and goes deeper. It follows the recursive algorithm of the backtracking technique in general:

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 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 tree represent partial solutions.
Solution States: States forming valid solution tuples in S.
Answer States: Satisfy implicit constraints, yield desired solutions.
Promising Node: Leads to desired solutions, 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 or all children generated.
Depth-First Node Generation: Uses the latest live node as the next E-node.
Bounding Function: Maximizes or minimises B(x1, x2, …, Xa) for optimisation.
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 Backtracking technique to solve a complex problem when:

Many choices exist: Backtracking is suitable if there exist many options at each step of the problem solving process. These options may relate to the selection of items and moves.
No clear best choice initially: There may not be enough information to determine the best choice among the available options at a given moment. Then you can choose a Backtracking algorithm.
Decision Lead to more choices: You can of course choose Backtracking technique to manage the branch structure and find all the possibilities.
Need to explore all possible solutions.

Types of problems in backtracking algorithms:

There are three types of problems in Backtracking algorithms: Decision problem, Optimization problem, and Enumeration problem as discussed below in brief.

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 possibility of placing n queens on an n × n chessboard without attacking each other.
Optimization Problem: In optimization problems. We look for the best possible solution among many. This may involve finding the maximum and minimum values of a certain function or variable. For example, the backpack problem. We maximize the total value of the items in the bag without exceeding its weight limit.
Enumeration Problem: Its objective is to find all possible solutions to a given problem. We list every valid option without any omissions. An example would be generating all possible permutations of a set of objects.

Applications of Backtracking & Examples:

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

1. Sudoku Solver: This problem contains a 3×3 subgrid that contains duplicate numbers. Backtracking technique is used to solve Sudoku solvers and its algorithm is given below.

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

2. N-Queen Problem: The backtracking technique determines how to place n queens on an N × N chessboard so that no two queens 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

3. Subset Sum Problem: It is used to find the subset of numbers from a given set that add up to a specific 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)

4. Hamiltonian Cycle Problem: Backtracking can be applied to find a closed tour in a graph that visits each vertex exactly once.

5. Rat in Maze Problem: 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

A. Advantages of Backtracking Algorithm
Backtracking techniques are used to solve complex problems. It has many advantages like:

Backtracking technique is efficient in constraint.
Backtracking technique is good for optimization problems.
This technique works for various types of problems.
This technique can find all possible solutions.
Since it backtracks so it also saves memory than Bruteforce technique.

B. Disadvantages of Backtracking Algorithm
However, backtracking techniques also have some limitations, like in terms of time complexity. This technique has these drawbacks:

There is no guaranteed solution.
It is slower because of many combinations.
It has exponential time complexity because of many combinations.
It is complex to implement with recursive functions this technique to solve a complex problem.
Efficiency depends on the level of complexity of the problem.

Difference between the Backtracking and Recursion

In recursion, a function calls itself until it reaches the base case. Whereas, in backtracking we use recursion to explore all the possibilities until we find the best and feasible result for any problem. Recursion is like a bottom-up process and backtracking is like a top-down process. In recursion, no value is discarded. Whereas, in backtracking, some solution candidates are rejected.

Conclusion

Backtracking is a technique for solving complex problems. It solves complex problems step by step. At each step, it checks the given constraints to obtain a valid solution to the problem. Whenever any condition fails it goes back to the previous step. The backtrack algorithm found all possible candidates but removed poor solutions. Backtrack technique is better than Bruteforce technique in terms of memory usage. The Backtrack algorithm is similar to the recursive algorithm but has some differences. Backtracking technique is generally used to solve complex problems.