A trial-and-error algorithm for finding solutions. When stuck, it reverts to a previous state and tries a different option.

Backtracking is a problem-solving algorithm based on depth-first search. In a Sudoku solver, it tentatively places a digit in an empty cell and, if a constraint violation occurs, reverts to the previous state and tries a different digit. By systematically exploring all combinations, it is guaranteed to find a solution (if one exists).

Role in Sudoku Solvers

When constraint propagation alone cannot solve a puzzle, backtracking serves as the last resort. It tentatively places a digit in the cell with the fewest candidates and backtracks when a contradiction arises. Combined with constraint propagation, the search space is dramatically reduced.

Difference from Human Solving

Humans prefer to avoid backtracking (guessing) and solve using only logically confirmable steps. This is due to working memory limitations - simultaneously tracking multiple hypothetical states is extremely difficult for humans. Sudoku difficulty design is based on whether a puzzle can be solved without guessing.