数独的解法
数独的规则
在 9×9 的方格里面填写数字 1-9，满足
- 每行不重复
- 每列不重复
- 9 个 3×3 的小方格不重复
回溯法
通过 DFS 遍历尝试每一个数字 根据三条规则，可以用三个二维数组记录每行，每列和每个小方格可填数字状态
row = [[True]*9 for _ in range(9)]
col = [[True]*9 for _ in range(9)]
block = [[True]*9 for _ in range(9)]
row[i][j]表示第i行是否可以填数字j
col[i][j]表示第i列是否可以填数字j
block[i][j]表示第i个方格是否可以填数字j
用二维数组g表示数独方格的原始状态，0表示空白
def dfs():
# 遍历所有位置
for i in range(9):
for j in range(9):
# 空白位置
if g[i][j]==0:
# 尝试每一个数字
for k in range(9):
# 数字满足行，列，块
if row[i][k] and col[j][k] and block[3*(i//3)+j//3][k]:
# 填入数字
row[i][k] = col[j][k] = block[3*(i//3)+j//3][k]= False
g[i][j] = k+1
if(dfs()):
return True
# 有填错的，删除数字
row[i][k] = col[j][k] = block[3*(i//3)+j//3][k]= True
g[i][j] = 0
# 九个数字都不能填
return False
# 所有位置都填了数字
return True
回溯法要注意如何进行记录状态，要方便更新，回溯