Backtracking

Backtracking is a general algorithmic technique used to find solutions to some computational problems, notably constraint satisfaction problems, by incrementally building candidates to the solutions. It "backtracks" (i.e., abandons a candidate) whenever it determines that the candidate cannot possibly be completed to a valid solution.

Core Concept

Backtracking systematically searches for solutions by trying to extend a partial solution one step at a time. It works as follows:

1. Build a Solution Incrementally: The algorithm starts with an empty or initial partial solution and tries to add one component (a "choice") at each step.
2. Check Validity: After adding a component, it checks if the current partial solution is still valid according to the problem's constraints.
3. Explore Deeper: If the partial solution is valid and not yet complete, the algorithm recursively explores further by making the next choice. This is akin to a Depth-First Search (DFS) in a state-space tree.
4. Backtrack (Undo Choice): If the partial solution becomes invalid at any point, or if it reaches a state where no further valid choices can be made (a "dead end"), the algorithm "backtracks." This means it undoes the last choice made and tries an alternative choice at the previous decision point. This process continues until a complete valid solution is found, or all possible choices have been exhausted without finding a solution.

The efficiency of backtracking comes from its ability to "prune" the search space by eliminating branches that are guaranteed not to lead to a valid solution, rather than exploring them fully.

Algorithm Structure

A generic backtracking algorithm is typically implemented recursively:

function backtrack(current_state, decisions_made):
    if current_state is a solution:
        add current_state to list_of_solutions
        return

    for each choice in possible_choices_from(current_state):
        // Make a choice
        apply_choice(choice, current_state)

        if is_valid(current_state): // Pruning step: check if current path is still promising
            backtrack(current_state, decisions_made + 1)

        // Undo the choice (backtrack)
        unapply_choice(choice, current_state)

Applications

Backtracking is a fundamental technique for solving a wide range of problems, including:

• Constraint Satisfaction Problems:
  • N-Queens Problem: Placing N chess queens on an N×N board so no two queens attack each other.
  • Sudoku Solver: Filling a 9×9 grid with digits.
  • Cryptarithmetic Puzzles: Assigning digits to letters to satisfy an arithmetic equation.
• Combinatorial Problems:
  • Subset Sum Problem: Finding a subset of a given set of numbers that sums to a specific target.
  • Generating Permutations and Combinations: Listing all possible arrangements or selections of elements.
  • Partition Problem: Dividing a set into two subsets with equal sums.
• Graph Problems:
  • Maze Solving: Finding a path through a maze.
  • Hamiltonian Cycle: Finding a cycle in a graph that visits each vertex exactly once.
  • Graph Coloring: Assigning colors to vertices such that no two adjacent vertices have the same color.

Characteristics

• Exhaustive Search: In its purest form, backtracking explores all potential solution paths.
• Pruning: The key to its efficiency is the ability to cut off branches of the search tree that cannot lead to a solution.
• Time Complexity: The worst-case time complexity is often exponential, as it may need to explore a significant portion of the search space. For example, O(b^d) where 'b' is the branching factor and 'd' is the maximum depth of the search tree.
• Space Complexity: Typically O(d) for the recursion stack depth.

Relationship to Other Algorithms

• Depth-First Search (DFS): Backtracking algorithms are inherently linked to DFS on a state-space tree. Each node in the tree represents a partial solution, and moving deeper in the tree corresponds to making another choice. Backtracking occurs when the DFS encounters a dead end and returns to an earlier node to explore an alternative path.
• Brute-Force Search: Backtracking is a refined form of brute-force search. While brute-force might check every single possibility, backtracking intelligently prunes the search space by avoiding paths that are guaranteed to be unproductive.
• Branch and Bound: A related technique often used for optimization problems. It extends backtracking by not only pruning invalid paths but also paths that are guaranteed to yield worse solutions than the best one found so far, typically by maintaining an upper or lower bound on the optimal solution.