用Python实现高效数独求解器教程

文章不知道大家是否熟悉？今天我将给大家介绍《用Python打造高效数独求解器：回溯算法实战教程》，这篇文章主要会讲到等等知识点，如果你在看完本篇文章后，有更好的建议或者发现哪里有问题，希望大家都能积极评论指出，谢谢！希望我们能一起加油进步！

1. 数独问题概述与数据表示

数独是一种基于逻辑的数字填充益智游戏。目标是填充一个9x9的网格，使每行、每列以及每个3x3的小方格内都包含1到9的数字，且每个数字只能出现一次。

在Python中，最直观的数独网格表示方式是使用一个二维列表（或嵌套列表），其中每个元素代表网格中的一个单元格。未填充的单元格通常用0表示。

# 示例数独网格（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]
]

2. 核心验证逻辑：check 函数

在尝试填充某个单元格时，我们需要验证一个数字是否可以合法地放置在该位置。这需要检查该数字是否已存在于当前行、当前列以及当前3x3的小方格中。

def check(grid, r, c, k):
    """
    检查数字 k 是否可以合法地放置在网格的 (r, c) 位置。
    参数:
        grid: 当前数独网格 (二维列表)
        r: 行索引
        c: 列索引
        k: 待检查的数字 (1-9)
    返回:
        如果合法返回 True，否则返回 False。
    """
    # 检查行
    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

3. 数独求解策略一：回溯算法 (Backtracking)

回溯算法是解决数独问题的通用且强大的方法。其核心思想是：

1. 找到一个空的单元格。
2. 尝试从1到9的每个数字。
3. 如果某个数字 k 可以合法地放置在该单元格，则将其放置，并递归地尝试解决下一个空单元格。
4. 如果递归调用返回 True (表示找到了一个解决方案)，则当前路径有效，返回 True。
5. 如果递归调用返回 False (表示当前数字 k 无法导致解决方案)，则撤销当前放置的数字（回溯），尝试下一个可能的数字。
6. 如果所有数字都尝试完毕，仍无法找到解决方案，则返回 False。

3.1 常见问题与优化

原始代码中存在几个常见问题，尤其是在递归和文件I/O处理方面：

• 文件重复打开： 在每次递归调用 solve 时都重新以写入模式 ('w') 打开文件，会导致每次只保留最后一次写入的内容。正确做法是在顶层函数中打开一次，并在所有操作完成后关闭。
• 缺少回溯机制： 当尝试一个数字失败时，原始代码没有将单元格重置为0，这导致一旦某个数字被错误地放置，后续尝试将无法纠正。
• poss 列表的误用： 原始代码试图在 poss 列表中只有一个元素时就立即填充并递归，这不符合回溯算法的“尝试所有可能”的原则，也无法处理多个可能性。

3.2 改进后的回溯求解器

为了解决上述问题，我们将 solve 函数设计为顶层函数，负责文件I/O和初始化，而实际的递归逻辑则封装在一个内部函数 recur 中。

import sys

def main():
    # 从命令行参数读取数独数据
    # sys.argv[1] 是输入文件路径，sys.argv[2] 是输出文件路径
    with open(sys.argv[1], 'r') as f:
        s1 = f.read()
        s2 = s1.split()
        grid_data = [int(x) for x in s2] # 将字符串转换为整数
        grid = [grid_data[i:i+9] for i in range(0, len(grid_data), 9)]
        solve_backtracking(grid) # 调用回溯求解器

def check(grid, r, c, k):
    # (check 函数与前面定义相同，此处省略重复代码)
    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_backtracking(grid):
    """
    使用回溯算法解决数独问题，并逐步打印求解过程到文件。
    """
    # 在顶层函数中打开文件一次，确保所有输出都写入同一个文件
    with open(sys.argv[2], 'w') as f:
        counter = 0 # 步骤计数器，记录填充了多少个单元格

        def recur(r, c):
            nonlocal 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,
                              f"Step {counter} - {k} @ R{r + 1}C{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

                # 回溯：如果所有数字都尝试失败，重置当前单元格为0
                grid[r][c] = 0
                return False # 返回 False，表示当前路径无法导致解决方案

        # 从 (0, 0) 位置开始递归求解
        return recur(0, 0)

if __name__ == "__main__":
    main()

4. 数独求解策略二：填充单一步骤确定解 (Iterative Single Possibility)

有时，我们可能只希望解决“简单”的数独谜题，即那些可以通过不断寻找只有一个可能解的空单元格来解决的谜题。这种方法不涉及回溯，而是迭代地填充确定的单元格。

4.1 适用场景与局限性

• 适用场景： 适用于那些每一步都能通过逻辑推导确定唯一解的数独。
• 局限性： 无法解决需要猜测和回溯的复杂数独。如果遇到所有空单元格都有多个可能解的情况，此算法将无法继续。

4.2 实现细节

该方法的核心是循环查找网格中所有空单元格，并计算每个空单元格的可能解。如果找到一个只有一个可能解的单元格，则填充它，并重复此过程，直到所有单元格都被填充或无法找到新的唯一解。

def solve_simple_sudoku(grid):
    """
    迭代地解决“简单”数独，只填充具有唯一可能解的单元格。
    如果遇到无法通过此方法解决的复杂数独，将抛出异常。
    """
    with open(sys.argv[2], 'w') as f:
        # 预先计算空单元格的数量，作为最大迭代次数的参考
        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():
            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 # 未找到具有唯一解的空单元格

        # 迭代填充，直到所有单元格填充完毕或无法继续
        for counter in range(count_empty_cells()): # 最多填充空单元格的数量次
            result = find_cell_with_one_solution()
            if not result: # 如果找不到具有唯一解的空单元格
                # 如果此时网格中仍有0，说明无法通过此方法解决
                if count_empty_cells() > 0:
                    raise ValueError("This is not a simple Sudoku puzzle! Requires backtracking.")
                break # 所有单元格都已填充

            r, c, k = result
            grid[r][c] = k # 填充唯一解

            # 打印当前步骤及数独状态
            print("-" * 18,
                  f"Step {counter + 1} - {k} @ R{r + 1}C{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_sudoku
# if __name__ == "__main__":
#     import sys
#     with open(sys.argv[1], 'r') as f:
#         s1 = f.read()
#         s2 = s1.split()
#         grid_data = [int(x) for x in s2]
#         grid = [grid_data[i:i+9] for i in range(0, len(grid_data), 9)]
#         solve_simple_sudoku(grid)

5. 总结与注意事项

本文详细介绍了两种主要的Python数独求解策略：

1. 回溯算法 (solve_backtracking)： 这是解决任何数独难题的通用方法。它通过递归地尝试所有可能的数字，并在遇到死胡同时进行回溯来找到解决方案。其关键在于正确的递归逻辑、回溯操作（重置单元格）以及高效的文件I/O管理（一次性打开和关闭文件）。
2. 迭代单一步骤填充法 (solve_simple_sudoku)： 这种方法适用于可以通过逻辑直接推导出唯一解的“简单”数独。它通过循环查找并填充具有唯一可能解的单元格。此方法不涉及回溯，因此在处理复杂数独时会失败。

在实际应用中，回溯算法是更常用和推荐的解决方案，因为它能够处理更广泛的数独难题。文件I/O的最佳实践是始终在程序的顶层或特定功能模块中一次性打开文件，并在操作完成后确保关闭文件（例如使用 with open(...) as f: 语句，它会自动处理文件的关闭）。理解并正确应用回溯机制是编写高效递归算法的关键。

到这里，我们也就讲完了《用Python实现高效数独求解器教程》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！