本教程详细讲解如何使用 python 实现一个功能完善的 Sudoku 求解器。文章首先分析了原始代码中存在的文件操作、递归逻辑和回溯机制的常见问题，随后提供了两种优化方案：一种是基于回溯算法的通用求解器，适用于任意难度数独；另一种是迭代式求解器，专门处理只存在唯一解的单元格。通过代码示例和详细解释，读者将掌握 Sudoku 求解的核心原理与实践技巧。
1. Sudoku 求解器的基础与问题分析
sudoku（数独）是一种经典的逻辑推理游戏，目标是在一个 9×9 的网格中填入数字 1-9，使得每一行、每一列以及每一个 3×3 的小九宫格内数字均不重复。实现一个 sudoku 求解器是学习回溯算法和约束满足问题（csp）的良好实践。
原始代码尝试使用递归方法解决 Sudoku，并记录每一步的填充过程。然而，它存在以下几个核心问题：
-
文件重复打开与未关闭： 在 solve 函数的每次递归调用中，都执行了 f = open(sys.argv[2],’w’)。这会导致每次递归都重新打开目标文件并以写入模式（’w’）清空其内容。因此，最终输出文件 output.txt 中只会保留最后一步的记录，而无法看到完整的求解过程。此外，文件句柄 f 未被显式关闭，可能导致资源泄露或数据未及时写入磁盘。
-
回溯机制的缺失与 poss 列表的误用： 原始代码尝试使用 poss 列表来判断一个单元格是否只有唯一解。它在找到第一个可能的数字时就立即填充并进行递归。然而，这种逻辑是错误的，因为它没有等待 for k in range(1, 10) 循环完全结束后再判断 len(poss) == 1。更重要的是，即使当前填充的数字导致后续无法找到解决方案，代码也没有将该单元格重置（即回溯），而是直接返回 False，导致算法无法探索其他可能的路径。
-
计数器位置不当：counter 变量在 solve 函数内部被初始化为 0。这意味着在每次递归调用时，counter 都会被重置，无法正确地累积并显示总的填充步数。
2. 核心概念：Sudoku 求解原理
在深入探讨解决方案之前，我们首先需要理解 Sudoku 求解的两个关键概念：有效性检查和回溯算法。
2.1 有效性检查 (check 函数)
check 函数是 Sudoku 求解的基础，它用于判断在给定网格的 (r, c) 位置上放置数字 k 是否合法。合法性判断需要满足以下三个条件：
立即学习“Python免费学习笔记（深入）”；
- 行不重复： 数字 k 不能在当前行 r 中已存在。
- 列不重复： 数字 k 不能在当前列 c 中已存在。
- 3×3 宫格不重复： 数字 k 不能在当前单元格所属的 3×3 小九宫格中已存在。
以下是 check 函数的实现：
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
2.2 回溯算法 (Backtracking Algorithm)
回溯算法是一种通过递归实现的问题求解范式，特别适用于解决约束满足问题，如 Sudoku。其核心思想是：
- 选择： 在当前状态下，选择一个未填充的单元格。
- 尝试： 尝试为该单元格填充一个可能的数字（1-9）。
- 检查： 使用 check 函数判断该数字是否合法。
- 递归： 如果合法，则递归调用求解函数，尝试填充下一个单元格。
- 回溯： 如果递归调用返回 False（表示当前选择无法导出完整解），则撤销当前单元格的填充（将其重置为 0），并尝试下一个可能的数字。
- 终止： 如果所有单元格都被成功填充，则找到一个解并返回 True；如果所有可能的数字都尝试完毕仍无法找到解，则返回 False。
3. 通用 Sudoku 求解器：回溯算法实现
为了解决原始代码的问题并实现一个通用的 Sudoku 求解器，我们将采用标准的回溯算法。主要修改包括：
- 文件处理集中化： 将文件的打开和关闭操作放在顶层的 solve 函数中，确保文件只打开一次并正确关闭。使用 with open(…) 语句可以自动管理文件句柄。
- 计数器与递归： counter 变量需要能够在递归调用中保持其状态并递增。这可以通过将 solve 函数设计为包装器，并在其内部定义一个嵌套的递归函数来实现，使用 nonlocal 关键字来修改外部作用域的 counter。
- 完整的回溯逻辑： 当一个尝试的数字无法导致最终解时，必须将该单元格重置为 0，以便算法可以尝试其他可能性。
import sys def main(): # 从命令行参数读取输入数独文件 with open(sys.argv[1], 'r') as f: s1 = f.read() s2 = s1.split() # 将字符串列表转换为整数列表 for i in range(len(s2)): s2[i] = int(s2[i]) # 将一维列表转换为 9x9 的数独网格 grid = [s2[i:i+9] for i in range(0, len(s2), 9)] solve(grid) # 调用主求解函数 def check(grid, r, c, k): # 检查行、列和 3x3 宫格的合法性，与前文相同 for i in range(9): if grid[r][i] == k: return False if grid[i][c] == k: return False 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): # 文件只打开一次，并使用 with 语句确保自动关闭 with open(sys.argv[2], 'w') as f: counter = 0 # 计数器在外部作用域初始化，确保不被重置 # 定义嵌套的递归函数，处理实际的求解逻辑 def recur(r, c): nonlocal counter # 声明 counter 为非局部变量，以便修改外部作用域的 counter # 基本情况：所有行都已处理完毕，表示数独已解 if r == 9: return True # 当前行处理完毕，进入下一行 elif c == 9: return recur(r + 1, 0) # 当前单元格已填充（非0），跳过并处理下一个单元格 elif grid[r][c] != 0: return recur(r, c + 1) # 当前单元格为空（为0），尝试填充数字 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 # 如果成功解决，返回 True # 如果所有数字尝试完毕，都无法解决，则回溯 grid[r][c] = 0 # 将当前单元格重置为 0 return False # 返回 False，表示当前路径失败 # 从 (0, 0) 开始递归求解 result = recur(0, 0) return result if __name__ == "__main__": main()
使用方法： 将上述代码保存为 sudoku_solver.py。 准备一个输入文件，例如 input.txt，内容为 81 个数字（0代表空），用空格分隔，例如： 0 4 0 0 0 0 1 7 9 0 0 2 0 0 8 0 5 4 … (示例输入在问题描述中) 然后在命令行运行： python sudoku_solver.py input.txt output.txtoutput.txt 文件将包含每一步的详细求解过程。
4. 简化 Sudoku 求解器：迭代式单解填充
原始问题中提到“如果有一个单元格只有一个可能的数字可以填入，就填入这个数字并打印表格，然后重复这个步骤”。这描述的是一种更简单的策略，适用于那些可以通过逻辑推理逐步填充的 Sudoku 谜题，即每一步都能找到一个“显而易见”的唯一解单元格。这种方法不需要回溯。
其核心思想是：
- 查找唯一解单元格： 遍历所有空单元格（值为 0），对于每个空单元格，尝试填充 1-9，并统计有多少个合法的数字。
- 填充： 如果某个空单元格只有一个合法的数字，则填充该数字。
- 重复： 重复上述过程，直到所有单元格都被填充或无法找到新的唯一解单元格。
- 限制： 如果在某一步无法找到任何具有唯一解的空单元格，则表示当前 Sudoku 无法通过这种简化方法解决。
import sys # check 函数与前文相同 def check(grid, r, c, k): for i in range(9): if grid[r][i] == k: return False if grid[i][c] == k: return False 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_simple(grid): # 辅助函数：计算当前网格中空单元格的数量 def count_empty_cells(): count = 0 for r_idx in range(9): for c_idx in range(9): if grid[r_idx][c_idx] == 0: count += 1 return count # 辅助函数：查找一个具有唯一可能解的空单元格 def find_cell_with_one_solution(): for r_idx in range(9): for c_idx in range(9): if grid[r_idx][c_idx] == 0: # 如果单元格为空 poss = [] # 存储可能的数字 for k in range(1, 10): if check(grid, r_idx, c_idx, k): poss.append(k) if len(poss) == 1: # 如果只有一个可能的数字 return r_idx, c_idx, poss[0] # 返回其坐标和唯一解 return None # 如果没有找到具有唯一解的空单元格 # 文件只打开一次，并使用 with 语句确保自动关闭 with open(sys.argv[2], 'w') as f: # 循环次数最多为所有空单元格的数量 for counter in range(count_empty_cells()): result = find_cell_with_one_solution() if not result: # 如果无法找到具有唯一解的空单元格 raise ValueError("This is not a simple Sudoku puzzle, cannot solve with this method!") 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) # main 函数需要修改以调用 solve_simple def main_simple(): with open(sys.argv[1], 'r') as f: s1 = f.read() s2 = s1.split() for i in range(len(s2)): s2[i] = int(s2[i]) grid = [s2[i:i+9] for i in range(0, len(s2), 9)] solve_simple(grid) if __name__ == "__main__": # 根据需求选择调用 main() 或 main_simple() main() # 默认调用回
