Sudoku Solver
Sudoku is a 9×9 grid divided into 3×3 boxes. Fill the grid so each row, column, and box contains digits 1–9 exactly once. The standard solution is backtracking: pick an empty cell, try digits 1–9; if a digit is valid (no conflict in row/col/box), place it and recurse; if we get stuck, backtrack.
Loading demo…
Algorithm explanation
Backtracking: find next empty cell. For each digit 1–9, check row, column, and 3×3 box for conflicts. If valid, place digit and recurse. If recursion returns true, we have a solution. If no digit works, reset cell and return false to backtrack. Optimizations include MRV (minimum remaining values) and forward checking.
Concepts used
- Backtracking
- Constraint propagation
- Recursion
Complexity
Time:
O(9^m) where m = empty cells (worst case)Space:
O(81) for boardReal-world usage
- Constraint satisfaction problems
- Scheduling and timetabling
- Puzzle games and generators