Backtracking

In Turkish: Geri İzleme

Updated September 30, 20263 min read

In short

Backtracking is a search technique that builds a solution one choice at a time and undoes the latest choice when it hits a dead end, then tries another option.

What is backtracking?

Backtracking is a way of searching through possible solutions to a problem without blindly checking every combination. It builds a candidate solution step by step, one decision at a time, and after each step checks whether the partial solution can still lead to a valid answer. If it can't, the algorithm undoes the last decision, backs up, and tries the next option.

Backtracking is usually written as a recursive function that follows a choose, explore, unchoose pattern: make a choice, recurse to solve the rest of the problem, then reverse the choice before trying the next one. All the possible sequences of decisions form a tree, and backtracking walks that tree depth-first. Its power comes from pruning: by rejecting a partial solution early, it skips the entire subtree of choices that would have followed from it. The worst case is still exponential, but good pruning often makes real problems fast enough.

Solving a maze by always taking the first open turn, and walking back to the last junction whenever you hit a wall, is backtracking in its purest form. It is the standard technique for constraint puzzles such as sudoku, crosswords, and the N-queens problem, for generating permutations and combinations, and for scheduling problems in which every choice must respect a list of rules. Many regular expression engines also use backtracking to try alternative ways of matching, which is why a badly written pattern can take exponential time on certain inputs, a vulnerability known as ReDoS (regular expression denial of service).

Backtracking is closely related to depth-first search, and the two are often confused. DFS is a general way to traverse a graph that already exists, while backtracking explores a tree of choices that it generates on the fly and abandons any branch that breaks the rules. It also differs from dynamic programming, which avoids re-solving repeated subproblems by storing their results, and from a greedy algorithm, which never undoes a choice at all.

Key takeaways

Backtracking builds a solution incrementally and undoes choices that lead to dead ends.
It is usually recursive and follows a choose, explore, unchoose pattern.
Pruning invalid partial solutions early is what makes it practical.
The worst case is exponential, but real problems are often much faster.
Sudoku solvers, N-queens, permutation generators, and many regex engines use backtracking.

Example

Counting N-queens solutions with backtrackingpython

def solve_queens(n, placed):
    # placed[r] is the column of the queen already placed in row r
    row = len(placed)
    if row == n:
        return 1  # a queen in every row: one complete solution
    count = 0
    for col in range(n):
        # Prune: skip columns and diagonals attacked by an earlier queen
        if any(c == col or abs(c - col) == row - r for r, c in enumerate(placed)):
            continue
        placed.append(col)                # choose
        count += solve_queens(n, placed)  # explore
        placed.pop()                      # unchoose, then try the next column
    return count
print(solve_queens(8, []))  # 92 solutions on a standard chessboard

Readers ask

What is the difference between backtracking and depth-first search?

Depth-first search traverses the nodes of an existing graph or tree. Backtracking applies the same depth-first order to a tree of choices that it generates as it goes, and it abandons a branch as soon as the partial solution breaks a rule.

What is the time complexity of backtracking?

In the worst case it is exponential, or even factorial, because it may explore every combination of choices. Pruning cuts the work dramatically in practice, but the worst-case bound usually stays exponential.

What problems are solved with backtracking?

Typical examples are sudoku and other constraint puzzles, the N-queens problem, generating all permutations or combinations, finding paths through a maze, and scheduling problems with many rules.