时间戳

首页 > 解决方案 > 为什么这个数独求解器返回相同的板而不解决任何问题？

python - 为什么这个数独求解器返回相同的板而不解决任何问题？

问题描述

我正在尝试编写一个简单的 python Sudoku 求解器，它实现了回溯，它似乎根本不起作用，也不能解决任何我不知道为什么的问题。The 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)

标签： pythonalgorithmbacktrackingsudoku

解决方案

你的代码总是回溯，即使它找到了解决方案。您的代码中没有任何内容说“嘿，我找到了解决方案，让我们停止进一步寻找”。因此，在扫描了所有可能性之后，您最终得到了一个完整的回溯矩阵。这段代码无能为力：它将回溯并将所有内容设置为零。没有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.

推荐阅读