leetcode 37 数独

判断数字是否填写正确没那么困难，通过check函数。减少时间复杂度，通过传入i,j。
！！！注意然后只返回一个解即可，需要 return。

唯一不同的变化是，题解的回溯函数有一个返回值，它是布尔类型，一旦返回 True，在递归那边就会把 True 传递上去，终止回溯。这一点值得注意。

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def check(value,i,j,board1):
            for t in range(len(board1)):
                if value ==board1[t][j]:
                    return False
                if value == board1[i][t]:
                    return False
            for t in range((i//3)*3,((i//3)+1)*3):
                for k in range((j//3)*3,(j//3+1)*3):
                    if board1[t][k]==value:
                        if t!=i and k!=j:
                            return False
            return True


        def dfs(i,j,board):
            if j==9:
                return dfs(i+1,0,board)#成功后不往下执行了
            if i==9:
                return True   
            if board[i][j]=='.':
                for value in range(1,10):
                    if check(str(value),i,j,board):
                        board[i][j]=str(value)
                        if dfs(i,j+1,board):#只返回一个解
                            return True
                        board[i][j]='.'
            else:
                return dfs(i,j+1,board)#成功后不往下执行了
        dfs(0,0,board)

也可以先确定可用数字数组。
见https://leetcode-cn.com/problems/sudoku-solver/solution/jing-dian-hui-su-fa-jin-shuang-bai-jie-fa-jian-dan/