回溯

回溯 37.解数独

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        def isValid(row, col, num):
            # 先判断再填就不用排除自身情况
            # 行和列
            for i in range(9):
                if board[row][i] == num:
                    return False
                if board[i][col] == num:
                    return False
            # 九宫
            r, c = row // 3, col // 3
            for i in range(r*3, r*3 + 3):
                for j in range(c*3, c*3 + 3):
                    if board[i][j] == num:
                        return False
            return True
        
        def dfs(row, col):
            # 递归的基线条件
            if row > 8:
                # 记录当前board
                for i in range(9):
                    for j in range(9):
                        ans[i][j] = board[i][j]
                return
            if board[row][col] != ".":
                if col < 8:
                    dfs(row, col + 1)
                else:
                    dfs(row + 1, 0)
            else:
                for i in range(1, 10):
                    if isValid(row, col, str(i)):
                        board[row][col] = str(i)
                        if col < 8:
                            dfs(row, col + 1)
                        else:
                            dfs(row + 1, 0)
                        board[row][col] = "."

        ans = [[""] * 9 for i in range(9)]
        dfs(0, 0)
        for i in range(9):
            for j in range(9):
                board[i][j] = ans[i][j]

执行用时：516 ms, 在所有 Python 提交中击败了34.53%的用户
内存消耗：13.2 MB, 在所有 Python 提交中击败了32.74%的用户

---

思路很简单，上述代码还需优化，先放个简版的