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 an empty cell and backtracks when a contradiction arises. Which cell is chosen changes the number of branches: choosing a cell with fewer remaining candidates makes the branching at that step smaller. Narrowing the candidates first reduces the combinations that have to be tried.
Difference from Human Solving
When solving with pencil and paper, avoiding tentative search (guessing) and advancing only through logically confirmable steps is sometimes said to be the preferred approach. The reason given is the load of holding and managing several hypothetical states at once.