解数独

这个题解使用回溯法来解决数独问题。回溯法是一种通用的算法思路,适合由多个步骤组成的问题,并且每个步骤都有多个选项。通过尝试每一个选项,可以一步步构建问题的解,当某个步骤无法满足要求时,就回溯到上一个步骤,尝试其他选项。对于数独问题,从第一行第一列开始,尝试填入数字1-9。对于每个空格,先判断当前数字是否合法,如果合法就填入,然后递归地去填下一个空格,直到填完整个数独。如果中途发现无解,就回溯到上一个空格,尝试其他数字。

时间复杂度: O(9^(n^2))

空间复杂度: O(n^2)

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def valid(i, j, val):
            # 检查行
            for n in range(9):
                if board[n][j] == val:
                    return False
            # 检查列  
            for n in range(9):
                if board[i][n] == val:
                    return False
            # 检查3*3宫
            for n in range(9):
                if board[i//3*3 + n//3][j//3*3+n%3] == val:
                    return False
            return True

        def backtrack(i, j):
            # 如果列已经填完,就换到下一行
            if j == 9:
                return backtrack(i+1, 0)
            # 如果所有的行和列都填完,说明找到了一个解    
            if i == 9:
                return True
            # 如果当前位置已有数字,就跳过 
            if board[i][j] != '.':
                return backtrack(i, j+1)

            # 尝试填入数字1-9
            for val in range(1, 10):
                val = str(val)
                # 如果不合法,就跳过
                if not valid(i, j, val):
                    continue
                # 填入数字  
                board[i][j] = val
                # 递归地填写下一个位置
                if backtrack(i, j+1):
                    return True
                # 无解的话,恢复当前位置为空格
                board[i][j] = '.'
        
        backtrack(0, 0)