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

Question

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

def 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 True

def 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]]

>