Python 中的逐步数独求解器

Question

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

然后我将其转入列表以进行索引。我想检查单元格，如果有一个单元格有一个可能的数字来输入数字而不是零，则输入该数字并打印所有数独表，然后重复此步骤。打印步骤，再次求解，打印步骤，再次求解。但在我的output.txt 文件中它只打印第一步。怎么了？

------------------

步骤 1 - 8 @ R1C1

------------------

8 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

------------------

这是我想要的输出，但所有步骤都是这样的。我的意思是这里有 48 个零，它必须打印 48 个步骤。

Answer 1

有几个问题：

• 您的输出文件将只有一个网格，因为在每次调用

  solve

  时，您都会调用

  f = open(sys.argv[2],'w')

  。您应该只打开文件进行一次写入。

• 您没有关闭输出文件。由于这两点，您需要将递归调用包装到打开和关闭文件的顶级调用中。

• 列表

  poss

  按照您的使用方式并没有多大用处。它一开始是空的，显然在第一个

  append

  之后它有一个元素，因此您放置该值并进行递归调用。但这并没有真正检查细胞是否没有其他解决方案。或者，如果打算以“回溯方式”进行操作，如果递归无法解决网格问题，那么您的代码将不会尝试替代方案。请参阅下一点。

• 你写了“如果有一个单元格有一个可能的数字来放置数字而不是零”，但这没有考虑所有空单元格（0）可能有多种可能性的情况。因此，这意味着您必须尝试一个值，如果它不能找到解决方案，请尝试替代方案，等等。如果您真的只想填充仅具有可能值的单元格，则首先需要让

  k

  循环完成到最后，因为只有这样你才能确定只有一个解决方案。如果情况并非如此，您应该尝试使用另一个单元格，而不是返回

  False

  。

• 与此相关，通过适当的回溯，当没有值可以进入已解决的网格时，您需要回溯。在这种情况下，您应该在返回

  False

  之前清除之前设置的值。这也意味着您的输出文件可能有更多的输出，而不仅仅是零的数量，因为它也将具有后来证明不会导致解决方案的输出。

这是带有回溯解决方案的更正代码：

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)  # call with one argument

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):
    f = open(sys.argv[2],'w')  # Should only execute once. So not part of recursive function
    counter = 0   # Should only execute once. So not part of recursion.
    
    def recur(r, c):
        nonlocal counter
        if r == 9:
            return True
        elif c == 9:
            return recur(r+1, 0)
        elif grid[r][c] != 0:
            return recur(r, c+1)
        else:
            # Don't use poss. It will prevent you from trying all available options
            for k in range(1, 10):
                if check(grid, r, c, k):
                    grid[r][c] = k
                    counter += 1
                    print("-" * 18, 
                          "Step " + str(counter) + " - " + str(k) 
                                  + " @ " + "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 recur(r, c+1):
                        return True
            grid[r][c] = 0  # backtrack!
            return False
            
    result = recur(0, 0)
    f.close()
    return result

if __name__ == "__main__":
    main()

如果您应该只解决只有一个可能值的单元格，那么您最好不要使用递归，因为这样就没有回溯。使用迭代：

• 找到下一个空闲单元并计算它具有的解决方案的数量。如果有的话，就使用那个。如果没有，则继续搜索这样的单元格。如果没有找到这样的单元格，则输入谜题对于该算法来说太复杂（并且您应该使用上面的回溯算法）。

这是“简单”数独的代码：

def solve(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 resolve_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

    with open(sys.argv[2], 'w') as f:
        for counter in range(count_empty_cells()):
            result = resolve_cell_with_one_solution()
            if not result:  # could not find an empty cell with one solution
                f.close()
                raise ValueError("This is not a simple Sudoku puzzle!")
            r, c, k = result
            grid[r][c] = k
            print("-" * 18, 
                  "Step " + str(counter+1) + " - " + str(k) 
                          + " @ " + "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)