Python数独求解器：从基础回溯到单解填充策略

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函数现在负责文件操作，所以这里不再传入文件对象
        solve(grid) 

def check(grid, r, c, k):
    # 检查行：当前行是否有重复的 k
    for i in range(9):
        if grid[r][i] == k:
            return False

    # 检查列：当前列是否有重复的 k
    for i in range(9):
        if grid[i][c] == k:
            return False

    # 检查3x3九宫格：计算当前单元格所属九宫格的左上角坐标
    x_area = (c // 3) * 3
    y_area = (r // 3) * 3

    # 遍历九宫格，检查是否有重复的 k
    for i in range(3):
        for j in range(3):
            if grid[y_area + i][x_area + j] == k:
                return False

    # 如果行、列、九宫格都没有重复，则 k 是合法数字
    return True

def solve(grid):
    # 文件操作和计数器应在外部初始化，确保只执行一次
    # 使用 'w' 模式打开文件，每次运行都会清空旧内容
    # 使用 'a' 模式可以追加内容，但这里我们希望每次求解都从头记录
    with open(sys.argv[2], 'w') as f:  
        counter = 0 # 记录填充步骤的计数器，非局部变量

        # 内部递归函数，负责具体的求解逻辑
        def recur(r, c):
            nonlocal counter # 声明 counter 是外部作用域的变量

            # 基本情况1：所有行都已处理完毕，数独已解
            if r == 9:
                return True

            # 基本情况2：当前行已处理完，进入下一行
            if c == 9:
                return recur(r + 1, 0)

            # 如果当前单元格已填充 (非0)，则跳过，处理下一个单元格
            if grid[r][c] != 0:
                return recur(r, c + 1)

            # 如果当前单元格为空 (0)，尝试填充 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)

                    # 递归调用：如果当前数字 k 导致后续成功解出，则返回 True
                    if recur(r, c + 1):
                        return True

            # 回溯：如果尝试了所有数字 k 都无法解出，则撤销当前单元格的填充
            # 将当前单元格重置为 0，并返回 False，表示此路径失败
            grid[r][c] = 0 
            return False

        # 启动递归求解过程
        result = recur(0, 0)
    # with 语句确保文件在退出时自动关闭
    return result

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():
        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 # 如果没有找到唯一解的空单元格，返回 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:  # 如果找不到唯一解的空单元格，说明此数独不是“简单”数独
                f.close()
                raise ValueError("This is not a simple Sudoku puzzle! Use a backtracking solver.")

            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 还是 solve_simple_sudoku
# 例如：
# def main():
#     # ... (输入处理部分不变) ...
#     # solve(grid) # 调用回溯求解器
#     solve_simple_sudoku(grid) # 调用单解填充求解器