Python 数独求解教程：详解回溯与迭代策略-Python教程-PHP中文网

Python 数独求解教程：详解回溯与迭代策略

本教程详细讲解如何使用 Python 实现一个功能完善的 Sudoku 求解器。文章首先分析了原始代码中存在的文件操作、递归逻辑和回溯机制的常见问题，随后提供了两种优化方案：一种是基于回溯算法的通用求解器，适用于任意难度数独；另一种是迭代式求解器，专门处理只存在唯一解的单元格。通过代码示例和详细解释，读者将掌握 Sudoku 求解的核心原理与实践技巧。

1. Sudoku 求解器的基础与问题分析

sudoku（数独）是一种经典的逻辑推理游戏，目标是在一个 9x9 的网格中填入数字 1-9，使得每一行、每一列以及每一个 3x3 的小九宫格内数字均不重复。实现一个 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 中已存在。
3x3 宫格不重复： 数字 k 不能在当前单元格所属的 3x3 小九宫格中已存在。

以下是 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() # 默认调用回

登录后复制

以上就是Python 数独求解教程：详解回溯与迭代策略的详细内容，更多请关注php中文网其它相关文章！