Introduction to Recursive Programming

CHAPTER 12

Multiple Recursion III: Backtracking

He who would search for pearls must dive below.

—John Dryden

BACKTRACKING is one of the most important algorithm design paradigms. It can be regarded as an “intelligent” brute-force strategy that performs exhaustive searches for solutions to constraint satisfaction and discrete optimization problems. The approach can be used to solve numerous puzzles and problems, including the eight-queens problem, finding paths through mazes, the sudoku puzzle, the 0-1 knapsack optimization problem, and many more.

Backtracking methods generally combine recursion and iteration, contain several parameters, and are not usually designed by strictly thinking about problem decomposition and induction. Thus, they ...