Backtracking
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
Pick the cell with the fewest candidates
Starting from a cell with only two candidates leaves just one branch to try if the first guess fails. This choice largely determines how much searching is needed.
Place one of its candidates tentatively
The digit goes in as a provisional move rather than a confirmed one, recorded so that it can be undone later.
Fill in whatever constraint propagation can confirm
Cells whose candidates have been narrowed to one by that placement are filled in a chain reaction, which brings any contradiction to the surface early.
Has a contradiction appeared?
Yes
Roll the grid back to just before the tentative placement and try another candidate in the same cell. This is backtracking.
No
If empty cells remain, return to the first step and choose the next cell.
Once every cell is filled, the solution is complete
Steps 1 to 4 form a loop. A rollback undoes only the most recent tentative placement, so everything confirmed before it is preserved. The more often constraint propagation runs between guesses, the sooner contradictions surface and the fewer branches have to be tried.
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.