标签：count return matrix python value 生成 col 数独 row
递归回溯实现
退出条件全部遍历结束
// 全部结束
if (count == 81): # 递归出口
return True
// 已经填充过了
# 行优先遍历
row = count // 9 # 行标
col = count % 9 # 列标
if matrix[row][col] != 0: # 已填充
return solveSudoku(matrix, count=count + 1)
递归
for i in range(1, 10):
if check(matrix, row, col, i): # 找到可能的填充数
matrix[row][col] = i
if solveSudoku(matrix, count=count + 1): # 是否可完成
return True # 可完成
# 不可完成
matrix[row][col] = 0 # 回溯
return False # 不可完成
每个数字检查
- 每一行包含1~9
- 每列包含1~9
- 3 *3 区域包含 1~9
def check(matrix, row, col, value):
"""
检测在(row,col)放value是否合适
1.每行含1-9,不含重复值value
2.每列含1-9,不含重复值value
3.3*3区块含1-9,不含重复值value
"""
# 检测每行
for j in range(9):
if matrix[row][j] == value:
return False
# 检测每列
for i in range(9):
if matrix[i][col] == value:
return False
# 检测元素所在3*3区域
area_row = (row // 3) * 3
area_col = (col // 3) * 3
for i in range(area_row, area_row + 3):
for j in range(area_col, area_col + 3):
if matrix[i][j] == value:
return False
return True
整体代码
点击查看代码
def check(matrix, row, col, value):
"""
检测在(row,col)放value是否合适
1.每行含1-9,不含重复值value
2.每列含1-9,不含重复值value
3.3*3区块含1-9,不含重复值value
"""
# 检测每行
for j in range(9):
if matrix[row][j] == value:
return False
# 检测每列
for i in range(9):
if matrix[i][col] == value:
return False
# 检测元素所在3*3区域
area_row = (row // 3) * 3
area_col = (col // 3) * 3
for i in range(area_row, area_row + 3):
for j in range(area_col, area_col + 3):
if matrix[i][j] == value:
return False
return True
def solveSudoku(matrix, count=0):
"""
遍历每一个未填元素，遍历1-9替换为合适的数字
"""
if (count == 81): # 递归出口
return True
# 行优先遍历
row = count // 9 # 行标
col = count % 9 # 列标
if matrix[row][col] != 0: # 已填充
return solveSudoku(matrix, count=count + 1)
for i in range(1, 10):
if check(matrix, row, col, i): # 找到可能的填充数
matrix[row][col] = i
if solveSudoku(matrix, count=count + 1): # 是否可完成
return True # 可完成
# 不可完成
matrix[row][col] = 0 # 回溯
return False # 不可完成
if __name__ == '__main__':
matrix = [[0 for x in range(81)][i:i + 9] for i in range(0, 81, 9)]
solveSudoku(matrix)
for i in range(9):
print(' '.join(map(str, matrix[i])))
标签：count,
return,
matrix,
python,
value,
生成,
col,
数独,
row
From： https://www.cnblogs.com/guanchaoguo/p/16852821.html