Backtracking

Definition

Backtracking is a general algorithmic technique that involves exploring all possible solutions to a problem by building solution candidates incrementally and abandoning a candidate (“backtracking”) as soon as it is determined that the candidate cannot be extended to a valid solution. It’s essentially a trial and error approach, where potential solutions are built piece by piece and abandoned when they fail to meet the necessary criteria.

Backtracking is a fundamental concept in computer science, especially in the domain of algorithms and problem-solving. It’s particularly useful for solving constraint satisfaction problems, optimization problems, and combinatorial problems. Some classic examples include the N-Queens puzzle, the traveling salesman problem, and various game-solving algorithms like Sudoku. Its importance lies in its ability to find solutions to problems where the solution space is vast and cannot be traversed in a straightforward manner. By systematically trying out different solutions and backtracking when necessary, efficient solutions can be found for many complex problems.

Core Concepts

• Backtracking operation:

  The backtracking operation is the core of the backtracking algorithm. The backtrack operation is used to undo a decision and try another decision at a decision point.

• Decision Space:

  The decision space refers to all the possible options or choices available at any given point in the problem-solving process. In backtracking, not all decisions in this space lead to a valid solution. The algorithm explores these decisions systematically, often visualized as a tree or graph, where each node represents a decision.

• Feasibility Checks:

  Before or after making a decision, it’s essential to check if the current path being taken is feasible. This involves ensuring that the current solution candidate adheres to the problem’s constraints. If a decision fails the feasibility check, the algorithm will backtrack to a previous decision point.

• Solution Space:

  The solution space encompasses all potential solutions to the problem. It’s the set of all paths or decision sequences that lead to a valid solution. Backtracking navigates this space by exploring and discarding paths, aiming to find one or more paths that lead to a valid solution.

Implementation

Implementation may vary depending on the problem, but the general approach is either recursive or iterative. The recursive approach is more intuitive. The iterative approach requires the use of a stack data structure to keep track of the current state and the current path being explored.

• Recursive approach

function BACKTRACKING-SOLUTION(problem):
    if problem is a base case:
        return solution to the base case
    for each option in problem:
        if option is valid:
            make the option
            result = BACKTRACKING-SOLUTION(sub-problem created by the option)
            if result is a valid solution:
                return result
            undo the option (backtrack)
    return no solution found

• Iterative approach

  • Stack data structure

function ITERATIVE-BACKTRACKING-SOLUTION(initialProblem):
    create an empty stack S
    push initialProblem onto S

    while S is not empty:
        currentProblem = top of S

        if currentProblem is a solution:
            return currentProblem

        if currentProblem has unexplored options:
            nextOption = get next unexplored option for currentProblem

            if nextOption is valid:
                push nextOption onto S
            else:
                mark nextOption as explored for currentProblem

        else:
            // All options for currentProblem have been explored, backtrack
            pop S

    return no solution found

• Variations according to the goal

  • find one solution

  • find all solutions

Application Domain

Backtracking algorithms are often used for optimization problems and combinatorial problems, where you need to search through a large solution space. They can be very efficient when implemented correctly, as they prune the search space by discarding branches that are guaranteed not to lead to a solution.

• Enumeration (find all)

• Decision (find one)

• Optimization (find the best)

  • Find all and then select the best

  • Not as efficient as branch and bound

Example problems

• Sudoku

• Eight queens

• Cross-word

Related Algorithms and Paradigms

• Brute-Force

  Brute-force is a general algorithmic paradigm that involves exploring all possible solutions to a problem by generating all possible candidates and validating them. It’s similar to backtracking in that it involves exploring a decision space, but it’s less efficient as it doesn’t prune the search space and it doesn’t use backtracking to discard invalid candidates. Brute-force algorithms can cover a wide spectrum of problems as all possible solutions are explored. It can be used to find all solutions, any valid solution, or the best solution. Backtracking is a more specific algorithmic paradigm that focus on to find any valid solution to a constraint satisfaction problem. When backtracking is employed to find all solutions, it is still more efficient than brute-force as it prunes the search space by discarding invalid candidates as early as possible.

• Depth-First Search

  Both backtracking and depth-first search involve exploring a decision space or tree/graph space in a systematic manner. They both try to explore as deep as possible. The difference is that backtracking is used to find solutions to constraint satisfaction problems, while depth-first search is used to find paths/nodes in a graph or tree. Backtracking is a general algorithmic paradigm, while depth-first search is a specific algorithm that uses backtracking, which backtracks when it reaches a dead end.

• Branch and bound

  Branch and bound is a general algorithmic paradigm that involves exploring the solution space by branching out and bounding the search space. It’s similar to backtracking in that it involves exploring a decision space, but it’s more efficient as it prunes the search space by bounding the solution space. The purposes of branch and bound are to find the optimal solution while backtracking is to find any valid solution. Branch and bound is often used for optimization problems, while backtracking is used for constraint satisfaction problems.

Comparison

Backtracking vs Brute-force

	Backtracking	Brute-force
Search space	Generate part of the intermediate and final states	Generate all intermediate and final states
Constraint application	Reject partial solutions	Validate final states
Run-time	fast	slow
Implementation	Stack/Recursion	Nested Loops/Recursion
Problem type	find one/find all	usually find all