Backtracking reverses an earlier decision when the current path cannot produce an acceptable result. In software design, it also means revisiting a poor decision as requirements and testing expose its weaknesses. section 2.0 section 15.8
A recursive backtracking search typically proceeds by:
- Treating each partial decision as a stage with one or more possible next steps. section 15.8
- Taking one valid path recursively, reducing the remaining problem until reaching a solution or dead end. section 15.11
- Undoing the latest choice at a dead end, then trying the next available choice. section 15.8
- Stopping after one solution or continuing to earlier stages to find additional solutions. section 15.8
Solving Sudoku
A solver fills cells from left to right and top to bottom. For each empty cell, it tries numbers from 1 through 9 and accepts a number only when its row, column, and three-by-three block remain valid. It recursively solves the next cell; when no number works there, it resets the previous cell to zero and tries that cell’s next candidate. Reaching the final cell produces a solution. section 15.10
