Python分步数独求解器仅输出第一步的问题排查

问题描述 #

我编写了如下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])
        grid = [s2[i:i+9] for i in range(0, len(s2), 9)]
        solve(grid,0,0)

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(grid, r=0, c=0):
    f = open(sys.argv[2],'w')
    counter = 0
    if r == 9:
        return True
    elif c == 9:
        return solve(grid, r+1, 0)
    elif grid[r][c] != 0:
        return solve(grid, r, c+1)
    else:
        poss = []
        for k in range(1, 10):
            if check(grid, r, c, k):
                poss.append(k)
                if len(poss) == 1:
                    grid[r][c] = k
                    counter += 1
                    print("-" * 18, "Step " + str(counter) + " - " + str(poss[0]) + " @ " + "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 solve(grid, r, c+1):
                        return True
        return False


if __name__ == "__main__":
    main()

输入的数独网格：

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

需求是：遍历数独单元格，找到仅有一种可能值的空单元格（值为0），填入该值后打印当前完整数独状态，重复此过程直至所有空单元格填满。但目前输出文件仅显示第一步，无法输出后续47步。

代码问题分析 #

• 文件打开模式错误：每次调用solve函数时用'w'模式打开输出文件，该模式会清空原有内容并重新写入，导致之前的步骤被覆盖。
• 步骤计数器失效：counter是solve的局部变量，每次递归都会重置为0，永远只会输出Step 1。
• 递归逻辑中断流程：填入唯一候选值后直接递归并返回True，终止后续单元格遍历，无法处理其他存在唯一候选的单元格。
• 未循环扫描网格：按行优先顺序遍历，填完一个单元格后直接继续下一个，但填入值后可能让其他单元格出现新的唯一候选，需要重新从头扫描整个网格。

修复后的代码 #

import sys

def main():
    with open(sys.argv[1], 'r') as f:
        s1 = f.read()
        s2 = list(map(int, s1.split()))
        grid = [s2[i:i+9] for i in range(0, len(s2), 9)]
    
    # 初始化输出文件，清空原有内容
    with open(sys.argv[2], 'w') as f:
        pass
    
    solve(grid)

def check(grid, r, c, k):
    # 检查行
    if k in grid[r]:
        return False
    # 检查列
    if k in [grid[i][c] for i in range(9)]:
        return False
    # 检查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

def solve(grid):
    counter = 1
    while True:
        filled = False
        # 遍历整个网格寻找唯一候选的单元格
        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:
                        # 填入唯一值
                        val = poss[0]
                        grid[r][c] = val
                        # 追加写入步骤到文件
                        with open(sys.argv[2], 'a') as f:
                            print("-" * 18, file=f)
                            print(f"Step {counter} - {val} @ R{r+1}C{c+1}", file=f)
                            print("-" * 18, file=f)
                            for row in grid:
                                print(" ".join(map(str, row)), file=f)
                            print("-" * 18, file=f)
                        counter += 1
                        filled = True
                        # 填完一个后跳出循环，重新扫描整个网格
                        break
            if filled:
                break
        # 没有找到可填充的唯一候选单元格，检查是否完成
        if not filled:
            if all(all(cell != 0 for cell in row) for row in grid):
                break
            # 若仍有空单元格但无唯一候选，可在此添加回溯逻辑（可选）
            break

if __name__ == "__main__":
    main()

修复说明 #

• 文件处理优化：主函数先清空输出文件，后续用'a'追加模式写入，避免覆盖之前的步骤。
• 循环扫描网格：用while循环持续扫描整个网格，每次填入值后重新从头扫描，确保新产生的唯一候选被及时处理。
• 计数器全局化：将counter放在循环外，确保步骤数持续递增不重置。
• 逻辑调整：移除递归终止流程，改为循环遍历，确保所有符合条件的单元格都被处理。

内容的提问来源于stack exchange，提问作者leandro