Backtracking Algorithm

Exploring Solutions by Trial and Error

Basic flow of a backtracking algorithm.

Many computer science problems require us to find a solution from a large number of possible choices. Trying every possible choice can be extremely slow. Backtracking is an algorithmic technique that solves such problems by building a solution step by step and abandoning a path as soon as it becomes clear that the path cannot lead to a valid solution.

In simple terms: try a choice, check whether it works, continue if it works, and undo the choice if it does not.

Backtracking is widely used in problems involving combinations, permutations, puzzles, constraint satisfaction, and searching through possible solutions. Common examples include the N-Queens problem, Sudoku, maze solving, graph coloring, permutations, and subset-sum problems.

What Is Backtracking?

Backtracking is a systematic trial-and-error technique. Suppose we are solving a problem where we have several choices at every step. We select one choice and continue building the solution.

If the current choice makes the solution invalid, we do not continue exploring that path. Instead, we remove the last choice, return to the previous step, and try another choice.

This process continues until a valid solution is found or all possibilities have been explored.

How Backtracking Works

A typical backtracking algorithm follows four main steps:

1. Choose — Select one possible option.
2. Check — Determine whether the selected option is valid.
3. Explore — If valid, recursively continue building the solution.
4. Undo — If the choice does not lead to a solution, remove it and try another possibility.

The undo step is what allows the algorithm to return to an earlier state and explore a different path.

General Backtracking Algorithm

Backtracking is commonly implemented using recursion.

BACKTRACK(solution):

if solution is complete:
record or return solution

for each possible choice:

if choice is valid:

make the choice

BACKTRACK(solution)

undo the choice

Example: N-Queens Problem

A classic example of backtracking is the N-Queens problem.

The problem is to place N queens on an N × N chessboard so that no two queens can attack each other. A queen can attack another queen if they are in the same row, the same column, or the same diagonal.

For a 4 × 4 board, one valid solution is shown below.

Solving N-Queens Using Backtracking

We can place queens one row at a time. For every row, we try each column, check whether the position is safe, place the queen if it is safe, and move to the next row. If no column works, we remove the queen from the previous row and try another position.

For example, after placing a queen, some positions in the next row become invalid because they are attacked by the existing queen. Those positions are immediately rejected instead of being explored further.

SOLVE(row):

if row == N:
return true

for column = 0 to N — 1:

if position(row, column) is safe:

place queen at (row, column)

if SOLVE(row + 1):
return true

Get Pratyushgupta’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

remove queen from (row, column)

return false

Backtracking Tree

The search process can be visualized as a tree. Each node represents a partial solution, while each branch represents a possible choice.

When a branch violates a constraint, the algorithm stops exploring that branch and returns to the previous node. This is called pruning.

Simplified search tree showing branching, invalid states, and backtracking.

Why Backtracking Is Better Than Brute Force

Without backtracking, an algorithm may generate every possible arrangement and check each one only after it is complete. Backtracking rejects invalid partial solutions immediately.

For example, if placing a queen creates a conflict, there is no reason to place more queens below it. The entire branch can be discarded. This early rejection is called pruning.

Pruning

Pruning is one of the most important ideas behind backtracking. If a partial solution cannot possibly become a valid complete solution, the algorithm stops exploring that branch.

Effective pruning can dramatically reduce the number of states that need to be examined, although the worst-case complexity can still be exponential or factorial.

Time Complexity

The time complexity of backtracking depends heavily on the specific problem. In the worst case, backtracking can still have exponential or factorial time complexity because it may need to explore a large number of possible solutions.

If a problem has b possible choices at each step and the solution has depth d, a general worst-case estimate is:

O(b^d)

For the N-Queens problem, a commonly used upper-bound description is approximately O(N!), because the algorithm can be viewed as choosing a different column for each row. The exact practical running time depends on how effectively invalid positions are pruned.

Space Complexity

Backtracking algorithms commonly use recursion, so the recursion depth contributes to auxiliary space.

For N-Queens, the recursion depth is O(N). If the complete N × N board is stored, the board itself requires O(N²) space. Therefore, when the board representation is included, total space can be described as O(N²).

Applications of Backtracking

Backtracking is useful whenever a problem has a set of possible choices, constraints that determine whether a choice is valid, and a need to find one or more valid configurations.

Common applications include:

Sudoku: Try numbers in empty cells and undo invalid choices.

Maze solving: Explore paths and return from dead ends.

Graph coloring: Assign colors while ensuring adjacent vertices have different colors.

Permutations: Generate different arrangements of a set of elements.

Subset Sum: Try including or excluding elements while searching for a target sum.

Advantages and Disadvantages

Advantages:
• Simple and natural for constraint-based problems.
• Can eliminate invalid solutions early.
• Often faster than checking every complete solution.
• Works well with recursive problem structures.
• Can find one solution or enumerate all solutions.

Disadvantages:
• Worst-case complexity can be exponential or factorial.
• Deep recursion can consume significant memory.
• Performance depends heavily on effective pruning.
• Very large search spaces can still be expensive.

Backtracking vs Brute Force

Brute force generally tries all possibilities, while backtracking explores possibilities and rejects invalid paths as early as possible.

Key difference: backtracking does not blindly explore every possibility. It stops exploring a branch as soon as that branch becomes invalid.

All in All

Backtracking is a powerful algorithmic technique for solving problems where a solution must be constructed through a sequence of decisions.

Its basic pattern is:

Choose → Check → Explore → Undo → Try another choice