编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 ‘.’ 表示。
提示：
给定的数独序列只包含数字 1-9 和字符 ‘.’ 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的。
class Solution: def solveSudoku(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ # 9 * 9 记录第1行的1,2，3，4,,,是否出现在这一行了 0代表没有出现过 rows_ = [[0 for _ in range(9)] for _ in range(10)] # 9 * 9 记录第1列的1,2，,,4,,是否出现在某一列 cols_ = [[0 for _ in range(9)] for _ in range(10)] # 9 * 9 记录第一个方格中的数字是否出现过了 一行代表一个大的方格子 boxes = [[0 for _ in range(9)] for _ in range(10)] # 扫描整个给定的地图，从左到右 从上到下 # i 控制行， j 控制列 先来一个扫描，天冲一下初始化的记录矩阵 for i in range(9): for j in range(9): if board[i][j] != '.': index = ord(board[i][j]) - ord('0') - 1 rows_[i][index] = 1 cols_[j][index] = 1 boxes[i // 3 * 3 + j // 3][index] = 1 # 初始化扫描之后，开始填充 def fill(board: List[List[str]], x: int, y: int) -> bool: # 递归函数，先定义退出条件 # 当纵坐标是9的时候 这一行填充完毕 if y == 9: return True # 定义下一个寻找目标的坐标 x控制行，y控制列 next_y = (y + 1) % 9 next_x = x + 1 if next_y == 0 else x # 然后开始遍历从1-9 每一个数字都判断一下，是否满足约束条件,一个一个去尝试 for i in range(9): index = x // 3 * 3 + y // 3 # index = (x + 1) // 3 * 3 + (y + 1) // 3 if rows_[x][i] != 1 and cols_[y][i] != 1 and boxes[index][i] != 1: rows_[x][i] = 1 cols_[y][i] = 1 boxes[index][i] = 1 board[x][y] = chr(i + ord('0') + 1) # 填充数字转成字符进当前的矩阵里面 if fill(board, next_x, next_y): # 递归填充成功 return True # 下一个空格填充不成功， 重置上面的操作，并选择下一个数字继续 rows_[x][i] = 0 cols_[y][i] = 0 boxes[index][i] = 0 board[x][y] = '.' return False # 最终不成功的话，就返回false fill(board, 0, 0)