Sudoku Solver
Fill empty cells with a digit that satisfies row, column and box. Backtrack on dead ends.
Backtracking: A 4 x 4 sudoku with a dead end to back out of
Cell (0, 1). 1 is already in row 0. 2 fits. 3 is already in column 1. 4 fits. Place 2, the smallest that fits, and move on.
Cost
- Best
- O(1)
- Average
- exponential
- Worst
- O(9^(empty cells))
- Space
- O(empty cells)
Before this
Taught by the same lesson
Backtracking covers these too, in the same run.