Backtracking recursively explores alternative solution paths. When a recursive attempt reaches a dead end, it reverses the latest choice and tries another path, continuing upward when necessary. section 15.8 section 15.11
A typical backtracking search proceeds as follows:
- Choose an available option at the current step and record the choice. section 15.10 section 15.9
- Recursively solve the smaller remaining problem. section 15.8
- Return success when the base case confirms a solution; otherwise undo the choice and try the next option. section 15.10 section 15.9
- Backtrack to the previous step after exhausting every option at the current step. section 15.11
Sudoku and eight queens
A Sudoku solver visits cells in order, tries numbers allowed by the row, column, and block, and recursively tests the next cell. Failed numbers are replaced; if every number fails, the solver returns to the previous cell. An eight-queens solver similarly places a safe queen in each column, recursively searches the next column, and removes the queen before trying another row. section 15.10 section 15.9
Figure 2.1 A design decision tree and the application development path shown as the dotted line. Each tree node denotes a juncture during development when we must decide to choose a path (i.e., branch) on which to continue. While designing and coding, if we head down a branch that leads to a dead-end (the lumps of coal), we must backtrack to the previous decision node and try another branch. After trying all the branches at a node, we must backtrack to the next higher node and try the next branch from there. We hope to find the path to a successfully completed application (the pot of gold).
A decision-tree figure makes branching, dead ends, and returning to earlier decision points visible. section 2.1
