深度优先搜索解决数独问题

深度优先搜索是一种常见的解决数独问题的算法。其基本思路是从数独棋盘的左上角开始，依次填入数字，每个数字填入之前都进行判断，如果填入的数字与当前行、列、宫中已经填入的数字不冲突，则继续填下一个数字，直到填满整个数独棋盘。如果填入的数字与已经填入的数字冲突，则回溯到之前的位置重新选择数字进行填充，直到找到解或者所有的情况都尝试完毕。

具体实现时，可以使用递归函数来实现深度优先搜索。在递归函数中，首先判断当前位置是否已经填满，如果是，则返回 true，表示已经找到解；否则，依次尝试 1 到 9 这 9 个数字，对于每个数字，判断是否合法，如果合法，则将其填入当前位置并递归到下一个位置，如果递归返回 true，则表示已经找到解，否则撤销填入的数字，继续尝试下一个数字。如果所有的数字都尝试完毕，都没有找到解，则返回 false。

下面是一个使用深度优先搜索解决数独问题的示例代码：

def solveSudoku(board):
    """
    :type board: List[List[str]]
    :rtype: void Do not return anything, modify board in-place instead.
    """
    def isValid(x, y, val):
        for i in range(9):
            if board[x][i] == val or board[i][y] == val or board[(x//3)*3+i//3][(y//3)*3+i%3] == val:
                return False
        return True
    
    def dfs(x, y):
        if y == 9:
            x, y = x+1, 0
        if x == 9:
            return True
        if board[x][y] != '.':
            return dfs(x, y+1)
        for val in range(1, 10):
            if isValid(x, y, str(val)):
                board[x][y] = str(val)
                if dfs(x, y+1):
                    return True
                board[x][y] = '.'
        return False
    
    dfs(0, 0)

在上面的代码中，isValid 函数用于判断填入的数字是否合法，其中 x 表示行坐标，y 表示列坐标，val 表示填入的数字。对于每个数字，分别判断其所在行、所在列、所在宫是否已经填入过该数字，如果已经填入过，则返回 False，否则返回 True。

dfs 函数用于进行深度优先搜索，其中 x 表示当前搜索的行号，y 表示当前搜索的列号。如果当前位置已经填满，则继续搜索下一个位置，如果已经搜索到了最后一行，则表示已经找到解，返回 True。如果当前位置没有填入数字，则依次尝试 1 到 9 这 9 个数字，对于每个数字，判断是否合法，如果合法，则将其填入当前位置并递归到下一个位置，如果递归返回 True，则表示已经找到解，否则撤销填入的数字，继续尝试下一个数字。如果所有的数字都尝试完毕，都没有找到解，则返回 False。

最后，调用 dfs(0, 0) 函数即可解决数独问题。