Sudoku Solver
Constraint-driven backtracking: fill the first empty cell with any consistent value and recurse. A contradiction anywhere erases back to the last choice point.
- Category
- Backtracking
- Time complexity
- O(4^cells)
- Space complexity
- O(cells)
Pseudocode
find an empty cell try 1..4, keep consistent ones conflict → next value stuck → erase and backtrack no empties left → solved
Reference implementation
for v in range(1, 5):
if ok(r, c, v):
grid[r][c] = v
if solve(): return True
grid[r][c] = 0 # undo