题目
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
思路
使用暴力破解是不现实的，其需要 9^81次运算。
因此与数独相同，都需要用到回溯的思想。
其算法可以简化为：
1.从头开始选择到一个空白格
2.选择数字 1-9中的一个，判断是否符合标准（不能重复出现在行，列，3*3方格中）
2.1 填入数字
2.2 检查其是否已经找出了数独的解
2.2.1 若抵达最后一格，获得数独的解
2.2.2 若没有抵达最后一格，放置下一个数字
2.2.3 若不存在解，删除当前数字
实现
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
flag = False
line = [[]for i in range(9)]
arr = [[]for i in range(9)]
chunk = [[]for i in range(9)] def valid_num(num, row, col):
num_flag = num not in line[row] and num not in arr[col] and num not in chunk[row//3*3+col//3]
return num_flag def remove(num, row, col):
i = line[row].index(num)
j = arr[col].index(num)
k = chunk[row//3*3+col//3].index(num)
del line[row][i]
del arr[col][j]
del chunk[row//3*3+col//3][k]
board[row][col] = '.' def add(num, row, col):
line[row].append(num)
arr[col].append(num)
chunk[row//3*3+col//3].append(num)
board[row][col] = num def check(row, col):
if row == 8 and col == 8:
nonlocal flag
flag = True
else:
if col == 8:
backtrace(row + 1, 0)
else:
backtrace(row, col + 1) def backtrace(row, col):
if board[row][col] == '.':
for m in range(1,10):
d= str(m)
if valid_num(d, row, col) is True:
add(d, row, col)
check(row, col)
if not flag:
remove(d, row, col)
else:
check(row, col) vex = len(board)
for i in range(vex):
for j in range(vex):
get = board[i][j]
k = i//3*3+j//3
if get is not '.':
line[i].append(get)
arr[j].append(get)
chunk[k].append(get)
# flag = False
backtrace(0, 0)
值得注意的是，在check函数中，需要申明nonlocal flag在函数或其他作用域中使用外层(非全局)变量，因为其对flag值进行了修改，否则无法使用。此处不能使用global。