Python数独求解器：从基础到回溯算法的实现与优化

import sys

def check(grid, r, c, k):
    """
    检查在给定位置 (r, c) 放置数字 k 是否合法。
    合法性规则：
    1. 同一行不能有重复数字 k
    2. 同一列不能有重复数字 k
    3. 同一 3x3 宫格内不能有重复数字 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 宫格的左上角坐标
    start_row = (r // 3) * 3
    start_col = (c // 3) * 3

    for i in range(3):
        for j in range(3):
            if grid[start_row + i][start_col + j] == k:
                return False
    return True

def main():
    # 从命令行参数获取输入文件路径
    # 假设 sys.argv[1] 是输入文件路径
    # sys.argv[2] 是输出文件路径
    if len(sys.argv) < 3:
        print("Usage: python solver.py <input_file> <output_file>")
        sys.exit(1)

    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, sys.argv[2])

def solve_simple_sudoku(grid, output_filepath):
    """
    迭代求解数独，每次只填充有唯一可能解的单元格。
    不涉及回溯，适用于“简单”数独。
    """
    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():
        """
        查找网格中第一个有且仅有一个合法填充数字的空白单元格。
        返回 (行, 列, 唯一解) 或 None。
        """
        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:  # 如果是空白单元格
                    possible_values = []
                    for k in range(1, 10):
                        if check(grid, r, c, k):
                            possible_values.append(k)
                    if len(possible_values) == 1:
                        return r, c, possible_values[0]
        return None  # 没有找到有唯一解的空白单元格

    with open(output_filepath, 'w') as f:
        # 循环直到所有单元格填满或无法找到唯一解
        for step_counter in range(count_empty_cells()): # 最多填充空白单元格的数量次
            result = find_cell_with_one_solution()
            if not result:
                # 如果找不到有唯一解的单元格，说明此数独对该算法而言过于复杂
                f.write("------------------\n")
                f.write("Error: This is not a simple Sudoku puzzle, cannot solve with single-solution fill.\n")
                f.write("------------------\n")
                return False # 表示未能完全解决

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

            # 打印当前步骤和数独状态
            f.write("-" * 18 + "\n")
            f.write(f"Step {step_counter + 1} - {k} @ R{r + 1}C{c + 1}\n")
            f.write("-" * 18 + "\n")
            for row in grid:
                f.write(" ".join(map(str, row)) + "\n")
            f.write("-" * 18 + "\n")
        return True # 表示成功解决

def solve_backtracking_sudoku(grid, output_filepath):
    """
    使用回溯算法求解数独，并记录每一步的填充过程。
    """
    # 文件句柄和步骤计数器应在顶层函数中初始化，
    # 避免在递归调用中重复打开文件或重置计数器。
    f = open(output_filepath, 'w')
    step_counter = 0

    def recur(r, c):
        nonlocal step_counter # 声明使用外部作用域的 step_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):
                    grid[r][c] = k  # 尝试填充数字
                    step_counter += 1

                    # 打印当前步骤和数独状态
                    f.write("-" * 18 + "\n")
                    f.write(f"Step {step_counter} - {k} @ R{r + 1}C{c + 1}\n")
                    f.write("-" * 18 + "\n")
                    for row in grid:
                        f.write(" ".join(map(str, row)) + "\n")
                    f.write("-" * 18 + "\n")

                    # 递归调用，尝试解决下一个单元格
                    if recur(r, c + 1):
                        return True  # 如果成功解决，则返回 True

            # 回溯：如果当前数字 k 无法导致解，则撤销填充，并返回 False
            # 尝试下一个 k，或者如果所有 k 都试过，则通知上一层递归回溯
            grid[r][c] = 0  
            return False

    # 启动递归求解过程
    result = recur(0, 0)
    f.close() # 确保文件在求解完成后关闭
    return result