Backtracking Algorithm

What is Backtracking Algorithm?

Backtracking is an algorithmic technique that searches for valid combinations to solve computational problems. It incrementally builds candidate solutions and discards those that fail to satisfy the given constraints. The approach is particularly useful when you must choose a feasible result among many possible outcomes.

This algorithm is considered more efficient than the Brute Force approach. Unlike Brute Force, which examines every possible combination, Backtracking focuses on finding a single valid solution that meets the defined constraints. It saves time and memory by undoing the last step and trying another option after reaching a dead end. It also stops as soon as a valid solution is found.

Backtracking is widely used because it can solve complex problems without exhaustive resource consumption. The technique is especially valuable for problems with many constraints, such as Sudoku, the N-Queens problem, and scheduling. By intelligently navigating potential solutions, Backtracking finds an answer that satisfies all conditions, which makes it indispensable for tasks that demand both precision and efficiency.

How Backtracking Algorithm Works?

The Backtracking algorithm is a problem-solving technique that builds valid solutions one step at a time. If the constraints at a given step are not satisfied, the algorithm returns to the previous step and selects a different candidate.

It then continues with alternative combinations that meet the constraints. Because many possible combinations exist, the algorithm picks the most satisfactory option and resolves the problem sequentially. This technique is helpful whenever you must pick from several candidates. Withdrawal means canceling a choice whenever it cannot lead to a valid solution.

The Backtracking algorithm follows these general steps to solve a problem:

Step 1) Initialization: Begin with an empty or partial solution.

Step 2) Selection: Based on the constraints, choose one candidate to extend the current solution.

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

Step 4) Constraint Check: At each step, verify whether the partial solution violates any constraints. If it does, backtrack and try a different candidate.

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

Step 6) Backtracking: When the current option cannot solve the problem, revert to the previous state and attempt a new candidate.

Step 7) Repeat: Continue the cycle until the problem is solved or every option has been explored.

Recursive Nature of Backtracking Algorithm

Backtracking algorithms are inherently recursive. The function calls itself with different parameters until it discovers a valid solution or exhausts every possibility:

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 the foundational terms tied to the Backtracking technique:

• Solution Vector: Represents solutions as n-tuples, such as (X1, X2, …, Xn).
• Constraints: Rules that limit X values, both implicit and explicit.
• Solution Space: All valid X values that satisfy the explicit constraints.
• State Space Tree: Represents the solution space in tree form.
• State Space: Describes paths within a state space tree.
• Problem State: Nodes in the search tree that represent partial solutions.
• Solution States: States that form valid solution tuples in S.
• Answer States: Satisfy implicit constraints and yield the desired solutions.
• Promising Node: Leads toward valid solutions and remains feasible.
• Non-Promising Node: Leads to infeasible states and is not explored further.
• Live Node: Already generated with unexplored children remaining.
• E-Node: A live node currently generating its child nodes.
• Dead Node: No further expansion is possible because every child is generated.
• Depth-First Node Generation: Uses the most recent live node as the next E-node.
• Bounding Function: Maximizes or minimizes B(x1, x2, …, Xa) for optimization.
• Static Trees: Tree formulation is independent of the problem instance.
• Dynamic Trees: Tree formulation varies with the problem instance.

When To Use A Backtracking Algorithm?

With the working steps clear, the next question is when Backtracking is the appropriate choice. You can pick the Backtracking technique to solve a complex problem in the following cases:

• Many choices exist: Backtracking suits problems where many options are available at every step, such as item selection or moves.
• No clear best choice: When there is insufficient information to determine the best option upfront, Backtracking can be applied to explore systematically.
• The decision leads to more choices: Backtracking helps you review chained choices in a structured way.
• Need to explore all possible solutions: Backtracking systematically explores every solution by making a series of decisions that build upon each other.

Types of Backtracking Problems

Once you decide that Backtracking fits the problem, you must recognize which category the problem belongs to. There are three types of problems in Backtracking algorithms: decision, optimization, and enumeration problems.

1. Decision Problem: The goal is to determine whether a feasible solution exists. The answer is either yes or no. For example, the N-Queens problem is a decision problem that asks whether N queens can be placed on an N x N chessboard without attacking each other.
2. Optimization Problem: The goal is to find the best possible solution among many options. This may involve identifying the maximum or minimum of a function or variable. The knapsack problem, where the objective is to maximize the total value of items while respecting the weight limit, is a classic example.
3. Enumeration Problem: The objective is to list every valid solution to a given problem without omission. Generating all possible letter combinations from a given set of characters is one such example.

Applications of Backtracking & Examples

Backtracking is applied in many real-world and academic scenarios. Some popular applications are explained below with their pseudo code.

1. Sudoku Solver: The Backtracking technique fills empty cells with valid numbers and reverts whenever a placement violates Sudoku rules.

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 approach places queens on an N x N chessboard such 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

3. Subset Sum Problem: Backtracking finds the subset of numbers from a given set that adds 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 is applied to find a closed tour in a graph that visits every vertex exactly once.
5. Rat in a Maze Problem: Backtracking finds the path of a rat from the starting point of a maze to the exit, undoing moves that lead to walls.

Advantages and Disadvantages of Backtracking Algorithm

Like every algorithmic strategy, Backtracking has clear strengths and limitations that you should weigh before adopting it.

Advantages of Backtracking Algorithm

Backtracking techniques solve complex problems in several effective ways:

• The Backtracking technique handles constraints efficiently.
• The method works well for solving optimization problems.
• The technique adapts to many different problem types.
• The procedure helps review every possible solution.
• Because it backtracks, it saves more memory than the Brute Force technique.

Disadvantages of Backtracking Algorithm

Backtracking also has some limitations, especially around time complexity. The drawbacks are as follows:

• It does not guarantee a solution in every scenario.
• It can be slow because of the large number of combinations to try.
• It carries high time complexity due to many possibilities.
• It is unsuitable for real-time constraints because finding the best solution may take a long time.
• Efficiency depends on the level of complexity of the problem.

Difference Between Backtracking And Recursion

Backtracking is built on recursion, but the two are not the same. The table below highlights the key differences.

FAQs