solver.py

from typing import List


class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        cols = [set() for _ in range(9)]
        rows = [set() for _ in range(9)]
        cuadrant = []
        for _ in range(3):
            cuadrant.append([set() for _ in range(9)])

        # Stack or positions to be filled
        s = []
        # Useful to iterate numbers as strings
        numStr = [str(num) for num in range(1, 10)]

        # Fill
        for i in range(9):
            for j in range(9):
                if board[i][j] != ".":
                    cols[j].add(board[i][j])
                    rows[i].add(board[i][j])
                    cuadrant[i // 3][j // 3].add(board[i][j])
                else:
                    s.append((i, j))

        def backtrack():
            # No elements missing
            if len(s) == 0:
                return True

            i, j = s.pop()
            for num in numStr:
                if num not in cols[j] and num not in rows[i] and num not in cuadrant[i // 3][j // 3]:
                    board[i][j] = num
                    cols[j].add(num)
                    rows[i].add(num)
                    cuadrant[i // 3][j // 3].add(num)

                    if backtrack():
                        return True

                    cuadrant[i // 3][j // 3].remove(num)
                    rows[i].remove(num)
                    cols[j].remove(num)
                    board[i][j] = "."

            # Return the position to the stack to re-process later
            s.append((i, j))
            return False

        backtrack()


# Tests:
if __name__ == '__main__':
    
    assert Solution().solveSudoku(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"]]) == [["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"]]
    assert Solution().solveSudoku(board = [[".",".","9","7","4","8",".",".","."],["7",".",".",".",".",".",".",".","."],[".","2",".","1",".","9",".",".","."],[".",".","7",".",".",".","2","4","."],[".","6","4",".","1",".","5","9","."],[".","9","8",".",".",".","3",".","."],[".",".",".","8",".","3",".","2","."],[".",".",".",".",".",".",".",".","6"],[".",".",".","2","7","5","9",".","."]]) == [["5","1","9","7","4","8","6","3","2"],["7","8","3","6","5","2","4","1","9"],["4","2","6","1","3","9","8","7","5"],["3","5","7","9","8","6","2","4","1"],["2","6","4","3","1","7","5","9","8"],["1","9","8","5","2","4","3","6","7"],["9","7","5","8","6","3","1","2","4"],["8","3","2","4","9","1","7","5","6"],["6","4","1","2","7","5","9","8","3"]]
    assert Solution().solveSudoku(board = [[".",".",".",".",".","7",".",".","9"],[".","4",".",".","8","1","2",".",".","3"],[".",".",".","9",".",".",".","1",".","."],[".",".","5","3",".",".",".","7",".","."],[".",".",".",".",".",".",".",".",".","."],[".","1","9",".",".",".","4",".",".","."],["5",".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".",".","."]]) == [["8","5","6","1","4","7","3","2","9"],["7","4","3","6","8","2","1","9","5"],["2","9","1","9","3","5","7","8","6"],["1","8","5","3","6","4","9","7","2"],["3","6","4","7","9","8","5","1","2"],["9","1","7","2","5","6","4","3","8"],["5","2","8","4","1","9","6","5","7"],["4","7","9","5","2","3","8","6","1"],["6","3","2","8","7","1","9","5","4"]]
    
    print('All Passed!')