Discrete Mathsfor Engineers

3. Generic Backtracking Algorithm

Now that we understand the intuition behind backtracking, we can formalize the technique as a generic algorithm.

Many classical problems share the same structure, even though their constraints and search spaces differ.

For this reason, backtracking is best understood through a generic algorithmic template.

3.1 State Representation

At any point in the algorithm, we maintain a partial solution.

This sequence represents the decisions made so far.

The state of the algorithm therefore consists of:

• the current partial assignment
• the depth in the search tree
• the remaining possible choices

3.2 Generating Choices

From a partial solution (x₁, …, xᵢ), the algorithm generates possible extensions for the next decision variable.

These values typically come from a domain of feasible candidates.

Each candidate corresponds to a child node in the search tree.

3.3 Feasibility Test

Before exploring a branch further, the algorithm verifies whether the new partial solution still satisfies the constraints.

If the constraint check fails, the branch is pruned immediately.

3.4 Detecting a Complete Solution

A complete solution is obtained when all decision variables have been assigned.

In other words, when the depth of the search tree reaches the required level.

At that moment, the algorithm may:

• record the solution
• print the solution
• update an optimal value
• stop the search (if only one solution is needed)

3.5 Generic Backtracking Template

The general structure of a backtracking algorithm can be written as follows:

BACKTRACK(state):

    if state is a complete solution:
        report solution
        return

    for each candidate choice c:
        
        if c is feasible:
            apply choice c
            
            BACKTRACK(updated state)
            
            undo choice c

This template captures the entire mechanism: explore a choice, recurse, and undo the choice afterward.

3.6 Structure of the Search Tree

The algorithm implicitly explores a tree structure.

• Each node represents a partial solution
• Each edge represents a decision
• Leaves correspond to complete assignments

The power of backtracking comes from the ability to prune large portions of this tree before fully exploring them.

3.7 Why This Template Is Important

Many classical algorithms are direct instantiations of this template.

• N-Queens
• Sudoku solvers
• Permutation generation
• Subset generation
• Graph coloring
• Hamiltonian path search

In each case, the differences lie in the constraint checks and candidate generation, not in the underlying search strategy.