为什么这个数独解算器返回相同的棋盘而不解任何问题？

Question

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

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

你能做什么

让solve返回一个布尔值：当它发现矩阵已满时，它应该返回True。如果递归调用返回True，那么不要清除任何单元格！而是立即返回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中那样验证放置的值时得到更快的结果