Very simple and minimal 9x9 sudoku solver, designed to work with Web Sudoku puzzles and written mostly as an exercise.
The solver employs an ad hoc algorithm which iteratively:
- Fills in all trivially-deducible digits in every row, column, and "quadrant" (square).
- Ranks the remaining cells by ascending number of possible digits they could contain (topmost and leftmost taking priority when necessary).
- Recursively fills these cells with (ascending-digit) guesses until a valid solution is found.
This is basically what I found my internal thought-process/algorithm to be doing as I tried to solve sudokus by hand.
While this is considerably more efficient than a naive brute-force backtracking algorithm, it is not as elegant or efficient as a properly-implemented Dancing Links / Algorithm X approach would be.[1] [2]
python3 sudoku.py