无法使用回溯获得数独解算器的输出

Question

我开始使用回溯和递归来研究数独求解器。我无法打印已解决的数独。我已经测试了该possible(y,x,n)方法并且它有效。该程序完成Process finished with exit code 0但没有打印出已解决的数独谜题。我使用带有 PyCharm Community Edition 2020.1.3 的 python 3.7 作为我的 IDE。

import numpy as np

grid = [[5, 3, 0, 0, 7, 0, 0, 0, 0],

        [6, 0, 0, 1, 5, 9, 0, 0, 0],

        [0, 9, 8, 0, 0, 0, 0, 6, 0],

        [8, 0, 0, 0, 6, 0, 0, 0, 3],

        [4, 0, 0, 8, 0, 3, 0, 0, 1],

        [7, 0, 0, 0, 2, 0, 0, 0, 6],

        [0, 6, 0, 0, 0, 0, 2, 8, 0],

        [0, 0, 0, 4, 1, 9, 0, 0, 5],

        [0, 0, 0, 0, 8, 0, 0, 7, 9]]

def possible(y, x, n):

    global grid

    for i in range(9):

        if grid[y][i] == n:

            return False

    for i in range(9):

        if grid[x][i] == n:

            return False

    x0 = (x // 3) * 3

    y0 = (y // 3) * 3

    for i in range(3):

        for j in range(3):

            if grid[y0 + i][x0 + j] == n:

                return False

    return True

def solve():

    global grid

    for y in range(9):

        for x in range(9):

            if grid[y][x] == 0:

                for n in range(1, 10):

                    if possible(y, x, n):

                        grid[y][x] = n

                        solve()

                        grid[y][x] = 0

                return

    print(np.matrix(grid))

if __name__ == "__main__":

    solve()

Answer 1

我已经测试了 possible(y,x,n) 方法并且它有效。但它坏了：if grid[x][i] == n:应该：if grid[i][x] == n:下一期是您要解决的难题，已解决！第六列有两个九：[., ., ., ., ., 0, ., ., .][., ., ., ., ., 9, ., ., .][., ., ., ., ., 0, ., ., .][., ., ., ., ., 0, ., ., .][., ., ., ., ., 3, ., ., .][., ., ., ., ., 0, ., ., .][., ., ., ., ., 0, ., ., .][., ., ., ., ., 9, ., ., .][., ., ., ., ., 0, ., ., .]您可能想在您的函数集中添加一个拼图验证器。在我下面的示例中，我使用了一个不同的可解决的难题，否则很难调试您的代码！最后，你的solve()功能被承保了。它不应该打印拼图，而是返回一个布尔值，指示它是否解决了拼图。然后将此结果用于您的回溯，并在最后确定难题是否可解决。最后，仔细阅读关键字global，您使用的不正确。import numpy as npdef possible(y, x, n):    for i in range(9):        if grid[y][i] == n:            return False    for i in range(9):        if grid[i][x] == n:            return False    x0 = (x // 3) * 3    y0 = (y // 3) * 3    for i in range(3):        for j in range(3):            if grid[y0 + i][x0 + j] == n:                return False    return Truedef solve():    for y in range(9):        for x in range(9):            if grid[y][x] == 0:                for n in range(1, 10):                    if possible(y, x, n):                        grid[y][x] = n  # tentatively try n                        solved = solve()                        if solved:                            return True  # solved recursively!                        grid[y][x] = 0  # undo attempt at n                                return False  # no solution for this square    return True  # no 0's to resolve, puzzle solved!if __name__ == "__main__":    grid = [        [6, 5, 8, 0, 0, 0, 0, 7, 0],        [0, 7, 0, 0, 5, 0, 8, 0, 0],        [0, 3, 9, 0, 0, 0, 5, 4, 0],        [0, 0, 2, 6, 0, 5, 0, 0, 7],        [0, 6, 0, 9, 7, 4, 0, 0, 0],        [7, 0, 0, 3, 0, 0, 6, 0, 0],        [0, 4, 6, 0, 0, 0, 2, 5, 0],        [0, 0, 7, 0, 6, 0, 0, 0, 0],        [0, 0, 0, 0, 0, 0, 7, 6, 8]    ]    if solve():        print(np.matrix(grid))    else:        print("No solution!")输出> python3 test.py[[6 5 8 1 4 3 9 7 2] [4 7 1 2 5 9 8 3 6] [2 3 9 7 8 6 5 4 1] [3 9 2 6 1 5 4 8 7] [8 6 5 9 7 4 1 2 3] [7 1 4 3 2 8 6 9 5] [1 4 6 8 3 7 2 5 9] [9 8 7 5 6 2 3 1 4] [5 2 3 4 9 1 7 6 8]]>