The Algorithm Behind Solving Any Sudoku Puzzle in Milliseconds

Sudoku is a constraint satisfaction problem disguised as a number puzzle. Every cell must satisfy three constraints simultaneously: its row contains each digit 1-9 exactly once, its column contains each digit 1-9 exactly once, and its 3x3 box contains each digit 1-9 exactly once. A standard 9x9 Sudoku has 81 cells. A typical puzzle provides 25-35 clues. That leaves 46-56 cells to fill. The brute force search space is enormous -- up to 9^56 possibilities. Yet a well-implemented solver handles any valid puzzle in under 10 milliseconds. The secret is constraint propagation combined with backtracking. Constraint propagation: the first pass Before doing any searching, you can eliminate candidates from each empty cell based on what is already placed. For each empty cell, start with candidates {1,2,3,4,5,6,7,8,9}. Remove any digit that already appears in the same row, column, or box. After this single pass, many cells are reduced to a handful of candidates, and some cells are reduced to a sin