使用Python构建高效数独求解器：从基础到回溯算法实践

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

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

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()

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)