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

Question

我开始研究使用回溯和递归的数独求解器。我无法打印已解决的数独。我已经测试了 possible(y,x,n) 方法并且它有效。该程序以 Process finished with exit code 0 结束，但没有打印出已解决的数独谜题。我正在使用 python 3.7 和 PyCharm 社区版 2020.1.3 作为我的 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

I have tested the possible(y,x,n) method and it works.

但是坏了:

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

应该是：

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

下一期是您要解决的难题，已破解！第六列有两个9：

[., ., ., ., ., 0, ., ., .]
[., ., ., ., ., 9, ., ., .]
[., ., ., ., ., 0, ., ., .]
[., ., ., ., ., 0, ., ., .]
[., ., ., ., ., 3, ., ., .]
[., ., ., ., ., 0, ., ., .]
[., ., ., ., ., 0, ., ., .]
[., ., ., ., ., 9, ., ., .]
[., ., ., ., ., 0, ., ., .]

您可能想在您的函数集中添加一个拼图验证器。在我下面的示例中，我使用了一个不同的可解决的难题，否则很难调试您的代码！

终于，你的solve()功能被承保了。它不应该打印拼图，而是 return 一个布尔值，指示它是否解决了拼图。然后将此结果用于您的回溯，并在最后确定难题是否可解决。

最后，请仔细阅读 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]]
>

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

Unable to get an output for sudoku solver using backtracking

python

recursion

sudoku

python-3.x

recursive-backtracking