数独求解的核心在于两个方面：一是如何表示数独网格，二是如何判断一个数字在特定位置是否有效。
一个标准的9x9数独可以被表示为一个二维列表（或称列表的列表），其中0表示空单元格。
# 示例数独网格
grid = [
[0, 4, 0, 0, 0, 0, 1, 7, 9],
[0, 0, 2, 0, 0, 8, 0, 5, 4],
[0, 0, 6, 0, 0, 5, 0, 0, 8],
[0, 8, 0, 0, 7, 0, 9, 1, 0],
[0, 5, 0, 0, 9, 0, 0, 3, 0],
[0, 1, 9, 0, 6, 0, 0, 4, 0],
[3, 0, 0, 4, 0, 0, 7, 0, 0],
[5, 7, 0, 1, 0, 0, 2, 0, 0],
[9, 2, 8, 0, 0, 0, 0, 6, 0]
]main 函数负责从文件读取输入并将其转换为这种网格格式：
import sys
def main():
# 从命令行参数获取输入文件路径
with open(sys.argv[1], 'r') as f:
s1 = f.read()
s2 = s1.split()
# 将字符串转换为整数列表
s_int_list = [int(x) for x in s2]
# 将一维列表转换为9x9的二维网格
grid = [s_int_list[i:i+9] for i in range(0, len(s_int_list), 9)]
# 接下来调用求解函数
# solve(grid) # 具体调用取决于采用哪种求解策略check 函数是数独求解的基石，它判断在给定行 r、列 c 的位置放置数字 k 是否符合数独规则。规则包括：
def check(grid, r, c, k):
# 检查行
for i in range(9):
if grid[r][i] == k:
return False
# 检查列
for i in range(9):
if grid[i][c] == k:
return False
# 检查3x3宫格
# 计算当前单元格所属3x3宫格的左上角坐标
x_area = (c // 3) * 3
y_area = (r // 3) * 3
for i in range(3):
for j in range(3):
if grid[y_area + i][x_area + j] == k:
return False
return True原始代码尝试实现一个递归求解器，但存在几个关键问题，导致它只能输出第一步：
立即学习“Python免费学习笔记（深入）”；
回溯法是一种穷举搜索算法，适用于解决约束满足问题。其核心思想是：尝试一个可能的值，如果发现这条路径无法通向解，就“回溯”到上一步，撤销之前的尝试，然后尝试另一个可能的值。
为了解决文件重复打开和回溯问题，我们将文件操作和计数器变量提升到外部作用域，并使用一个嵌套函数 recur 来实现递归回溯逻辑。
import sys
def main():
with open(sys.argv[1], 'r') as f:
s1 = f.read()
s2 = s1.split()
s_int_list = [int(x) for x in s2]
grid = [s_int_list[i:i+9] for i in range(0, len(s_int_list), 9)]
solve(grid) # 调用新的 solve 函数
def check(grid, r, c, k):
# 检查行
for i in range(9):
if grid[r][i] == k:
return False
# 检查列
for i in range(9):
if grid[i][c] == k:
return False
# 检查3x3宫格
x_area = (c // 3) * 3
y_area = (r // 3) * 3
for i in range(3):
for j in range(3):
if grid[y_area + i][x_area + j] == k:
return False
return True
def solve(grid):
# 文件只打开一次，使用 'w' 模式会清空文件，但因为只打开一次，所以不会重复清空
# 更好的做法是使用 'a' 模式（追加）或者在 solve 外部处理文件
# 这里为了与原始需求保持一致，假设每次运行都生成新的输出文件
with open(sys.argv[2], 'w') as f: # 使用 with 语句确保文件关闭
counter = 0 # 计数器只初始化一次
# 嵌套函数实现递归，可以访问外部 solve 函数的 counter 和 f
def recur(r, c):
nonlocal counter # 声明 counter 为非局部变量，以便修改外部函数的 counter
# 基础情况：如果行索引达到9，表示所有行都已处理完毕，数独已解决
if r == 9:
return True
# 如果列索引达到9，表示当前行已处理完毕，移动到下一行的开头
elif c == 9:
return recur(r + 1, 0)
# 如果当前单元格不为0（已被填充），则跳过，处理下一个单元格
elif grid[r][c] != 0:
return recur(r, c + 1)
else:
# 尝试填充1到9的数字
for k in range(1, 10):
if check(grid, r, c, k): # 检查当前数字 k 是否有效
grid[r][c] = k # 放置数字
counter += 1
# 打印当前步骤到文件
print("-" * 18,
"Step " + str(counter) + " - " + str(k)
+ " @ " + "R" + str(r + 1) + "C" + str(c + 1),
"-" * 18,
sep='\n', file=f)
for x in grid:
print(" ".join(map(str, x)), file=f)
print("-" * 18, file=f)
# 递归调用以填充下一个单元格
if recur(r, c + 1):
return True # 如果后续填充成功，则当前路径有效
# 回溯：如果所有数字都尝试过，但没有一个能导致解，
# 则将当前单元格重置为0，并返回 False
grid[r][c] = 0
return False
# 从 (0, 0) 开始递归求解
result = recur(0, 0)
return result # 返回最终求解结果（True/False）
if __name__ == "__main__":
main()关键改进点：
原始需求中提到“如果有一个单元格只有一个可能的数字，就填入这个数字并打印表格，然后重复这些步骤”。这是一种简化版的数独填充策略，不涉及回溯，只适用于那些可以通过逻辑推理逐步填充的“简单”数独。如果数独需要猜测并回溯，这种方法将无法解决。
import sys
# check 函数与 main 函数保持不变，此处省略重复代码
def solve_simple_sudoku(grid):
def count_empty_cells():
count = 0
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
count +=1
return count
def find_cell_with_one_solution():
"""
在网格中寻找一个空单元格，该单元格只有一个可能的有效填充数字。
如果找到，返回 (行, 列, 唯一数字)；否则返回 None。
"""
for r in range(9):
for c in range(9):
if grid[r][c] == 0: # 找到空单元格
poss = [] # 存储当前单元格的所有可能数字
for k in range(1, 10):
if check(grid, r, c, k):
poss.append(k)
if len(poss) == 1: # 如果只有一个可能数字
return r, c, poss[0]
return None # 没有找到具有唯一解的空单元格
with open(sys.argv[2], 'w') as f:
# 循环次数最多为所有空单元格的数量，因为每次成功填充一个
# 实际可能更少，因为如果无法找到唯一解，会提前退出
for counter in range(count_empty_cells()):
result = find_cell_with_one_solution()
if not result: # 如果找不到具有唯一解的空单元格
# 如果所有单元格都已填充，则数独已解决
if count_empty_cells() == 0:
print("Sudoku solved successfully!", file=f)
else: # 否则，这个数独对这种方法来说太复杂了
print("This is not a simple Sudoku puzzle! Requires backtracking.", file=f)
return False # 无法通过此方法解决
r, c, k = result # 获取找到的唯一解单元格信息
grid[r][c] = k # 填充数字
# 打印当前步骤和网格状态
print("-" * 18,
"Step " + str(counter+1) + " - " + str(k)
+ " @ " + "R" + str(r + 1) + "C" + str(c + 1),
"-" * 18,
sep='\n', file=f)
for x in grid:
print(" ".join(map(str, x)), file=f)
print("-" * 18, file=f)
# 如果循环结束且所有单元格都已填充
if count_empty_cells() == 0:
print("Sudoku solved successfully!", file=f)
return True
else:
print("Finished simple filling, but puzzle not fully solved.", file=f)
return False
# 在 main 函数中调用此 solve_simple_sudoku
# if __name__ == "__main__":
# # 假设 main 函数已经处理了文件读取和 grid 初始化
# # 然后可以这样调用：
# # main()
# # 并在 main 函数内部调用 solve_simple_sudoku(grid)注意事项：
本教程展示了两种不同策略的数独求解器：
在实际开发中，应根据数独的复杂度和预期行为选择合适的求解策略。对于通用的数独求解需求，回溯法是首选。同时，良好的文件I/O习惯（如使用 with open 语句）和清晰的变量作用域管理（如 nonlocal 关键字）是编写健壮Python代码的重要实践。
以上就是Python数独求解器：从基础到回溯算法详解的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
206
收藏
