leetcode: 37. Sudoku Solver

# Write a program to solve a Sudoku puzzle by filling the empty cells.
# 
# Empty cells are indicated by the character '.'.
# 
# You may assume that there will be only one unique solution.

class Solution():
    def solveSudoku(self, board):
        def solver(board):
            for i in range(9):
                for j in range(9):
                    if board[i][j] == ".":
                        for k in range(1, 10):
                            board[i][j] = str(k)
                            if isValid(board, i, j) and solver(board):
                                return True
                            board[i][j] = "."
                        return False
            return True

        def isValid(board, x, y):
            for i in range(9):
                if (i != x and board[i][y] == board[x][y]) or (i != y and board[x][i] == board[x][y]):
                    return False
            for i in range((x//3)*3, (x//3)*3+3):
                for j in range((y//3)*3, (y//3)*3+3):
                    if (i != x or j != y) and board[i][j] == board[x][y]:
                        return False
            return True

        solver(board)


if __name__ == '__main__':
    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",".","."]]
    Solution().solveSudoku(board)
    assert board == [["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"]]