打印有效，但使用回溯解决数独时 return 值为 None

Question

我写了下面的代码来用回溯法解决一个数独游戏。可以打印正确的结果，但我还没有找到一种方法来获得与 return 值相同的结果而不是打印它。我必须如何更改程序才能使其正常工作？

import numpy as np

def find_possible(sudoku,r,c):
    """returns the possible Values as numpy array for a given position"""
    position = sudoku[r, c]
    if position == 0:
        line = sudoku[r, :]
        column = sudoku[: ,c]
        r0 = (r//3)*3
        c0 = (c//3)*3
        square = sudoku[r0:r0+3,c0:c0+3]
        numbers = np.arange(1, 10)
        blocked_numbers = np.unique(np.append(np.append(line,column),square))
        return np.setdiff1d(numbers,blocked_numbers)
    else: return np.array([])

def backtrack(sudoku):
    """solve the game with the backtracking method"""
    for r in range(9):
        for c in range(9):
            list_of_possible = find_possible(sudoku,r, c)
            if sudoku[r,c] == 0:
                for i in range(len(list_of_possible)):
                    sudoku[r,c] = list_of_possible[i]
                    backtrack(sudoku)
                    sudoku[r,c] = 0
                return

    result = sudoku
    print(result)

table = np.array([[5, 3, 0, 0, 7, 0, 0, 0, 0],
                  [6, 0, 0, 1, 9, 5, 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]])

backtrack(table)

编辑

如果 print 被 return 替换，return 值仍然是 None，因为第一个 return。而如果我给第一个return数独矩阵的值，输出的不是最终结果

Answer 1

您需要使用 return 语句。使用 return result

而不是 print(result)

Answer 2

您没有将结果 "back along the track" 传递给 backtrack 函数的原始调用。（结果意味着数独已经解决了。）你的 print 有效，因为你恰好到达那条线一次：当你的 for 循环结束时没有零。但是，解决问题并不止于此，您的 "tree" 次调用 backtrack 次调用仍在继续。您可以通过查看 table 来验证这一点：在某些时候它已被完全解决（没有留下零），但是如果您在最后打印它，那里将再次有零。

通过以下更改，您的函数可以是 returns None（就像您之前所做的那样，我只是添加了 None 以明确显示）或 [=21 中已解决的数独=].在 for 循环中，result 存储调用 backtrack 的结果，我们可以测试结果是否为 None（我们必须继续求解）或者我们已经完成并且可以 return result（或者到之前的 backtrack 调用，或者到函数外的原始调用）。

def backtrack(sudoku):
    """solve the game with the backtracking method"""
    for r in range(9):
        for c in range(9):
            list_of_possible = find_possible(sudoku, r, c)
            if sudoku[r, c] == 0:
                for i in range(len(list_of_possible)):
                    sudoku[r, c] = list_of_possible[i]
                    result = backtrack(sudoku)
                    if result is not None:
                        return result
                    sudoku[r, c] = 0
                return None
    return sudoku

顺便说一句，result 名称只是对与 sudoku 相同对象的另一个引用。我认为这可能有助于理解正在发生的事情，但你并不真的需要它：

def backtrack(sudoku):
    """solve the game with the backtracking method"""
    for r in range(9):
        for c in range(9):
            list_of_possible = find_possible(sudoku, r, c)
            if sudoku[r, c] == 0:
                for i in range(len(list_of_possible)):
                    sudoku[r, c] = list_of_possible[i]
                    if backtrack(sudoku) is not None:
                        return sudoku
                    sudoku[r, c] = 0
                return None
    return sudoku

此外，尝试开始使用像 Pylint 或 flake8 这样的 linter，它们会稍微分析您的代码以进行一些改进。例如，在 Python 中，而不是

for i in range(len(list_of_possible)):

你可以写

for possible in list_of_possible:

打印有效，但使用回溯解决数独时 return 值为 None

Print works but return value is None when using backtracking to solve a sudoku

python

recursion

sudoku

backtracking