Discrete Mathsfor Engineers

6. Classic Problems

Backtracking is not a single problem-specific trick.

It is a general search strategy that appears in many classical problems from combinatorics, graph theory, and constraint satisfaction.

The purpose of this part is to connect the generic algorithm with concrete and well-known applications.

6.1 Permutation Generation

One of the simplest applications of backtracking is the generation of all permutations of a set.

At each level, the algorithm chooses one element that has not yet been used.

• Partial solution = current permutation prefix
• Choices = unused elements
• Goal = complete permutation

This is often the first problem used to introduce backtracking.

6.2 Subset Generation

Another classical example is generating all subsets of a set.

Each decision answers a binary question: include an element or exclude it.

• Each level corresponds to one element
• Each node branches into two possibilities
• The leaves represent complete subsets

This makes the search tree especially clear and easy to visualize.

6.3 N-Queens

The N-Queens problem is one of the most famous backtracking problems.

The task is to place n queens on an n × n chessboard so that no two queens attack each other.

• Partial solution = queens placed so far
• Choices = possible columns for the next row
• Constraints = no shared column or diagonal

6.4 Sudoku

Sudoku can also be solved with backtracking.

The algorithm fills empty cells one by one, testing whether each placement respects the puzzle rules.

• Choices = digits that can be placed in a cell
• Constraints = row, column, and subgrid consistency
• Goal = fill the entire board

This is a strong example of constraint-driven pruning.

6.5 Graph Coloring

In graph coloring, we assign colors to vertices so that adjacent vertices receive different colors.

A backtracking solution assigns colors one vertex at a time.

• Partial solution = colors assigned so far
• Choices = available colors
• Constraint = adjacent vertices cannot share a color

This example connects backtracking directly to graph theory.

6.6 Hamiltonian Path

The Hamiltonian Path problem asks whether a graph contains a path that visits every vertex exactly once.

Backtracking explores possible vertex sequences while rejecting branches that repeat vertices or break adjacency.

• Partial solution = current path
• Choices = admissible next vertices
• Goal = a path containing all vertices

6.7 The Common Structure

Although these problems look different, they all share the same abstract structure:

• build a partial solution incrementally
• generate possible next choices
• test feasibility
• recurse
• undo and try another branch

What changes from one problem to another is not the search strategy, but the definition of state, choices, and constraints.