题目
-
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 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