为什么这个数独解算器 return 同一个棋盘没有解决任何问题？

Question

我正在尝试编写一个简单的 python 数独解算器，它实现了回溯，它似乎根本不起作用，也没有解决任何我不知道为什么的问题。 Puzzle 应该有一个解决方案，我猜问题出在回溯机制上，但我完全不确定为什么会发生这种行为。

matric =[
    [7,8,0,4,0,0,1,2,0],
    [6,0,0,0,7,5,0,0,9],
    [0,0,0,6,0,1,0,7,8],
    [0,0,7,0,4,0,2,6,0],
    [0,0,1,0,5,0,9,3,0],
    [9,0,4,0,6,0,0,0,5],
    [0,7,0,3,0,0,0,1,2],
    [1,2,0,0,0,7,4,0,0],
    [0,4,9,2,0,6,0,0,7]
]

def is_possible(y: int, x: int, n: int) -> bool:

        # check row and column
    for i in range(9):
        if matric[y][i] == n:
            return False

    for i in range(9):
        if matric[i][x] == n:
            return False
    # check box
    new_x = x // 3 * 3
    new_y = y // 3 * 3
    for i in range(3):
        for j in range(3):
            if matric[new_y + i][new_x + j] == n:
                return False
    return True

def solve():
    global matric
    # Find a point
    for y in range(9):
        for x in range(9):
            if matric[y][x] == 0:   # found a point to solve
                for n in range(1, 10):   # Check numbers
                    if is_possible(y, x, n):
                        matric[y][x] = n
                        solve()         # Solve Next Point
                        matric[y][x] = 0    # Back track
                return
solve()
for x in matric:
    print(x)

Answer 1

您的代码总是回溯，即使找到了解决方案。您的代码中没有任何内容表明 “嘿，我找到了解决方案，让我们停止进一步寻找”。因此，在扫描了所有可能性之后，您最终会得到一个完整的回溯矩阵。此代码无能为力：它将回溯并将所有内容设置为零。没有if solved: announce the solution

你能做什么

设solvereturn一个boolean：当发现矩阵满了，应该returnTrue。如果递归调用returns True，那么不要清除任何单元格！相反，立即 return True。这样您将快速回溯出递归树，而无需更改矩阵中的任何内容。然后，原始调用者将找到仍然完好无损的解决方案的矩阵。

所以：

def solve():
    global matric
    for y in range(9):
        for x in range(9):
            if matric[y][x] == 0:
                for n in range(1, 10):
                    if is_possible(y, x, n):
                        matric[y][x] = n
                        if solve():  # Did we find a solution?
                            return True  # Yes! Tell the caller!
                        matric[y][x] = 0  # Back track
                return False  # No way to fill this cell with a valid value
    return True  # Found no free cell, so this is a solved puzzle!

请注意，虽然此算法可能会解决一些难题，但它会在较难的难题上花费太多时间。要解决更难的难题，您需要添加和维护更多的数据结构，以了解哪些值仍可在单元格中使用，以及哪些值仍需要在行、列或块中找到一个位置。与现在在 is_possible.

中必须验证放置的值相比，这将提供更快的结果

为什么这个数独解算器 return 同一个棋盘没有解决任何问题？

Why this sudoku solver return same board without solving anything?

python

algorithm

sudoku

backtracking

你能做什么