Backtracking

Backtracking

Backtracking is a computational algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree). It is a type of Depth First Search but with added constraints. Backtracking is used in a variety of problems, including puzzle solving and constraint satisfaction problems.

Overview

Backtracking can be thought of as a selective tree/graph traversal method. It is used for solving problems that can be broken down into smaller problems of the same type. A classic example is the Eight Queens Puzzle, where the goal is to place eight queens on a chessboard such that no two queens threaten each other. Backtracking works by attempting to place a queen on a board, and if placing the next queen leads to a conflict, it backtracks by removing the previously placed queen and trying another position.

Algorithm

The backtracking algorithm consists of a recursive function that attempts to solve the problem. The function typically follows this structure:

1. Base Case: If the current solution is a valid and complete solution, return this solution. 2. For each candidate:

  a. Check if the candidate can potentially lead to a solution.
  b. If the candidate is valid, add it to the current solution.
  c. Recursively attempt to build on this candidate.
  d. If the candidate does not lead to a solution, remove it from the current solution (backtrack).

Applications

Backtracking is used in various applications such as:

• Sudoku solving
• Crossword puzzle solving
• Graph coloring
• Finding all Hamiltonian cycles in a graph
• Knapsack problems
• Permutations and combinations

Advantages and Disadvantages

Advantages

• Backtracking provides a systematic way to iterate through all possible configurations of a problem.
• It is flexible and can be applied to many types of problems.

Disadvantages

• It can be inefficient, as it explores some paths that may lead to a dead end and thus, might involve a lot of unnecessary calculations.
• The time complexity can be exponential in the worst case, making it impractical for large datasets.

See Also

• Brute-force search
• Dynamic programming
• Greedy algorithm

Backtracking Resources
Latest articles Most recent articles Ongoing trials	Wikipedia