37. 解数独

https://leetcode-cn.com/problems/sudoku-solver/

解法一：

经典回溯法，对每个空白处（设有m个）尝试填入数字1-9，每次验证填入的数是否符合，然后递归进入下一个空白。若不符合，还原现场（将该位置继续设为空白）递归栈深度为m，复杂度为m^9。

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.solve(board)  #调用solve
        
    def solve(self, board):
        digits = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':  #对每个空白，尝试填入1-9
                    for c in digits:
                        if self.isValid(board, i, j, c):   #若验证合法，填入                           
                            board[i][j] = c
                            if self.solve(board):  #递归进入下一个
                                return True
                            else:  #若solve不成立，还原现场
                                board[i][j] = '.'
                    return False  #若1-9都试过，仍不符合，说明solve不成立，返回上一个位置
        return True  #所有空白都合法填完，solve成立（很重要，不能漏掉）


    def isValid(self, board, row, col, c):
        for i in range(9):
            if board[i][col] != '.' and board[i][col] == c:  #验证同一列是否有重复
                return False
            if board[row][i] != '.' and board[row][i] == c:  #验证同一行
                return False
            #验证同一块
            #以该块的最左上角为基准[3*(row//3), 3*(col//3)]
            #从左到右(i//3)，从上到下（i%3）遍历
            if board[3*(row//3) + i//3][3*(col//3)+i%3] != '.' and board[3*(row//3) + i//3][3*(col//3)+i%3] == c:
                return False
        return True