0

Sudoku Solver

Hard

Fill the first empty cell with each legal digit and recurse. Validating as you place, rather than at the end, is what makes it tractable.

constraint propagationbacktracking
TimeExponential in theory, instant in practice
SpaceO(1) extra
Input4x4 for a quick demo, 9x9 for the real thing
3
4

Given digits are fixed. Fill the rest so every row, column and 2 by 2 box holds 1 to 4 once.

placements0backtracks0
1 / 20
solve():
find first empty cell
for d in 1..9:
if d is legal in row, column and box:
place d; if solve(): return true; erase d
return false
Why it matters

Box index is row over three times three plus column over three.

Practise this
Sudoku SolverHValid SudokuMN-QueensH
Keyboard
space play← → stepr restartctrl K search

More in Recursion & Backtracking

N-Queens
Exponential, heavily pruned
Subsets (Take or Skip)
O(n * 2^n)
Permutations (Swap and Recurse)
O(n! * n)
Next visualiser
KMP Pattern Matching