37. 解数独（难）

• 题目
• 题解：回溯

题目

• 编写一个程序，通过填充空格来解决数独问题。

  数独的解法需 遵循如下规则：

  数字 1-9 在每一行只能出现一次。
  数字 1-9 在每一列只能出现一次。
  数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
  数独部分空格内已填入了数字，空白格用 '.' 表示。

题解：回溯

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def backtrack(board: List[List[str]], i: int, j: int) -> bool:
            m, n = 9, 9
            if j == n:
                return backtrack(board, i + 1, 0)  # 穷举到最后一列的话就换到下一行重新开始
            if i == m:#base case
                return True  # 所有行都填满，数独解决完成
            if board[i][j] != '.':
                return backtrack(board, i, j + 1)  # 当前位置已有数字，填充下一个位置
                
            for ch in range(1, 10):
                if isValid(board, i, j, str(ch)):#检查当前数字是否合法
                    board[i][j] = str(ch)  # 合法则填入数字
                    if backtrack(board, i, j + 1):  # 如果找到一个可行解，立即结束
                        return True
                    board[i][j] = '.'  # 回溯，撤销当前位置的填充
            return False#穷举完1-9，依然没有找到可行解，此路不通
        
        def isValid(board: List[List[str]], r: int, c: int, n: str) -> bool:
            for i in range(9):
                if board[r][i] == n:
                    return False  # 检查当前行是否有相同数字
                if board[i][c] == n:
                    return False  # 检查当前列是否有相同数字
                if board[(r // 3) * 3 + i // 3][(c // 3) * 3 + i % 3] == n:
                    return False  # 检查当前 3x3 方框内是否有相同数字
            return True

        # 调用回溯函数进行数独求解
        backtrack(board, 0, 0)
        # 已解决的数独
        for row in board:
            ' '.join(row)
        return board