Sudoku Solver Python Solution with Tests

lcpy gen -n 37   # by problem number
lcpy gen -s sudoku_solver   # by problem name

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

![Solution](https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png)

class Solution:
    # Time: O(9^(n)) where n = number of empty cells, pruned heavily by validity checks
    # Space: O(n) recursion stack + O(1) bookkeeping sets
    def solve_sudoku(self, board: list[list[str]]) -> None:
        rows = [set[str]() for _ in range(9)]
        cols = [set[str]() for _ in range(9)]
        boxes = [set[str]() for _ in range(9)]
        empties: list[tuple[int, int]] = []

        for r in range(9):
            for c in range(9):
                ch = board[r][c]
                if ch == ".":
                    empties.append((r, c))
                else:
                    rows[r].add(ch)
                    cols[c].add(ch)
                    boxes[(r // 3) * 3 + c // 3].add(ch)

        def backtrack(idx: int) -> bool:
            if idx == len(empties):
                return True
            r, c = empties[idx]
            b = (r // 3) * 3 + c // 3
            for d in map(str, range(1, 10)):
                if d in rows[r] or d in cols[c] or d in boxes[b]:
                    continue
                board[r][c] = d
                rows[r].add(d)
                cols[c].add(d)
                boxes[b].add(d)
                if backtrack(idx + 1):
                    return True
                board[r][c] = "."
                rows[r].discard(d)
                cols[c].discard(d)
                boxes[b].discard(d)
            return False

        backtrack(0)