Backtracking

Backtracking is a general algorithmic technique for finding solutions to computational problems that can be solved by making a sequence of decisions. It works by building a solution incrementally through a series of choices, implemented most effectively using recursion to mirror the depth-first search of the solution space. At each stage, the algorithm makes a decision and attempts to proceed down that path; if the partial solution proves non-viable or leads to a dead end, the algorithm “backtracks” by systematically undoing the most recent choice and exploring an alternative option, thus efficiently pruning unpromising paths.

Examples of problems where backtracking is commonly used include:

Puzzles such as eight queens puzzle and Sodoku.
Combinatorial optimization problems such as parsing and the knapsack problem.
Goal-directed programming languages such as Prolog.

A backtracking algorithm that only searches for one solution typically has the following general structure:

FUNCTION solve(current_state):

# 1. Check if the current state forms a complete solution
IF is_solution(current_state):
RETURN true # Found a solution (maybe do something with it?)

# 2. Iterate through all possible choices (candidates) from the current state
FOR EACH candidate IN generate_candidates(current_state):

# Check if the choice is safe/valid
IF is_valid(current_state, candidate):

# A. Make the move (Choose)
make_move(current_state, candidate)

# B. Recurse to the next state (Explore)
IF solve(current_state):
RETURN true # The recursive call found a solution, stop iterating

# C. Undo the move (Unchoose/Backtrack)
# This is the essential “backtracking” step to explore other possibilities.
undo_move(current_state, candidate)

RETURN false # No solution found

References

GeeksforGeeks: Introduction to Backtracking
Wikipedia: Backtracking