Discrete Mathsfor Engineers

1. Problem Model & Search Space

Backtracking is often introduced informally as a method that tries possibilities and undoes decisions when they fail.

That intuition is useful, but to understand the technique rigorously, we must first define the problem model and the search space it explores.

1.1 Why Start With the Model?

Backtracking is not tied to a single concrete problem. It is a general strategy for exploring a structured set of possibilities under constraints.

Therefore, before discussing recursion or implementation details, we must answer:

• What is a candidate solution?
• How is a partial solution represented?
• When can we stop exploring a branch?

1.2 Candidate Solutions

A candidate solution is usually built incrementally as a sequence of decisions:

Each variable xᵢ represents a choice made at step i, typically selected from a domain of feasible values.

A complete assignment may represent a full solution, while a prefix (x₁, …, xᵢ) represents a partial solution.

1.3 The Search Space

The collection of all candidate solutions defines the search space.

This space is naturally modeled as a tree:

• The root is the empty solution
• Each level corresponds to one additional decision
• Each edge represents a choice
• Each node represents a partial assignment

In abstract terms, a node may be written as (x₁, …, xᵢ).

1.4 Constraints

Not every partial solution is worth exploring.

A backtracking problem is defined together with constraints that determine whether a partial assignment can still be extended into a valid full solution.

If the current partial assignment violates the problem structure, the algorithm stops exploring that branch.

1.5 Feasible vs. Complete Solutions

It is useful to distinguish two notions:

• Feasible partial solution: a partial assignment that does not violate constraints
• Complete solution: a full assignment that satisfies all problem requirements

Backtracking spends most of its time exploring feasible partial solutions and testing whether they can be extended.

Feasibility is a local condition, while completeness is a global one.

1.6 The Objective of Backtracking

Depending on the problem, the objective may be:

• Find one valid solution
• Find all valid solutions
• Count how many valid solutions exist
• Find an optimal solution under additional criteria

In every case, the method systematically explores the search tree while pruning branches that cannot succeed.

1.7 Why This Matters

This model appears in many classical problems:

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

In all of them, the central idea is the same: build solutions incrementally, test constraints early, and backtrack whenever a branch becomes impossible.