递归回溯如何工作？电脑爱好者数独解算器

Question

我对回溯很困惑，因为当递归调用returns时，你不会通过将网格替换回零来替换找到的解决方案。因此，即使您找到了解决方案，它也不会被删除，因为在调用 solve 函数之后，您通过将值替换回零来取消所做的操作。我知道你正在回溯，但在包含所有正确值的最终递归调用中，你不是只是将所有内容替换为 0 吗？

# grid = .....    # defined as a global value,
                  # a list of 9 lists, 9-long each
def solve():
    global grid
    for y in range (0, 9):
        for x in range (0, 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

    # edit: missed this final line:
    print (np.matrix(grid))

这是 Thorsten Altenkirch 教授在 Computerphile video 上的代码。

Answer 1

这是一段奇怪的代码，但应该可以进行一些改编：

def solve():
    global grid
    for y in range(0, 9):
        for x in range(0, 9):
            if grid[y][x] == 0:
                for n in range(1,10):
                    if possible(y, x, n):
                        grid[y][x] = n
                        if solve():
                            return True  # return without reset
                        grid[y][x] = 0
                return False  # exhausted all options
            return True  # this is the deepest and last call with no more zeroes

Answer 2

这不是包含所有正确值的 final 递归调用，而是 (each of) deepest 。是的，此代码列举了所有给定棋盘 grid 的拼图解法，而不仅仅是第一个解法。

对于每个 (y,x) 位置，如果它是空的，我们尝试依次放置从 1 到 9 的每个数字。如果可以像 到目前为止 一样在板上放置，我们递归 已更改 grid 板.

在最深层次的递归中，棋盘上没有空的 (y,x) 位置。因此，我们滑到 print 语句。 _{（它也可以被替换为 yield True，例如，将其变成一个生成器。在我们从该生成器获得的每个 next 值上，我们都有一个完整的解决方案-- 在 changed grid 中。当发电机耗尽时，grid 将再次处于其原始状态。）}

当从 1 到 9 的所有数字都被尝试过后，当前调用已运行完成。但是递归链中它上面的那个正在等待继续 its 工作试图填补 its (y,x) 位置。我们必须让它在它调用 this 调用 solve() 之前的同一块板上工作。这个调用在棋盘上所做的唯一变化是将 its (y,x) 位置的值从 0 更改为 1 到 9。因此我们必须将其更改回 0.

这意味着代码也可以稍微重组，因为

def solve():
    global grid
    for y in range (0, 9):
        for x in range (0, 9):     # for the first
            if grid[y][x] == 0:    # empty slot found:
                for n in range(1,10):  # try 1..9
                    if possible(y, x, n):
                        grid[y][x] = n
                        solve()        # and recurse
                # (move it here)
                grid[y][x] = 0     # restore
                return             # and return
    # no empty slots were found:
    #   we're at the deepest level of recursion and
    #   there are no more slots to fill:
    yield True     # was: print (np.matrix(grid))

每次调用仅在一个 (y,x) 位置起作用，它通过从头开始重新搜索找到的第一个空位置 在改变的板上。此搜索由 y 和 x 上的前两个嵌套循环完成。这有点多余；我们知道这个 (y,x) 之前的所有职位都已经填满了。代码将更好地重组以将起始位置 (y,x) 作为参数传递给 solve.

递归回溯的范例很漂亮。 Prolog 充满神秘感，Haskell 会用神秘的 monads 谈话让你眼花缭乱（monads 实际上只是可解释的可嵌套数据），但这里只需要一些 nested loops，递归创建！

范式很漂亮，但是这段代码，没那么多。代码的视觉结构应该反映其真正的计算结构，但这段代码给你的印象是 y-x- 循环是嵌套循环，用于创建 backtracking 结构，它们是 not（他们只是按照自上而下从左到右的顺序对下一个空space进行一次性线性搜索）。

角色由 n in range(1,10) 循环完成。当发现空 space 时，y-x- 循环应该停止并显式退出，以在代码结构中真正反映计算上发生的事情，使其明显 n in range(1,10) 循环没有嵌套在 y-x- 循环中，而是在他们完成工作后发挥作用。

另一个问题是它只是假设在第一次调用 solve() 之前在 grid 中给我们的数字的有效性。从未实际检查过该有效性，仅检查我们放置在空单元格中的数字的有效性。

_{（注意：此答案的先前版本是基于对代码的错误阅读。其中也有一些有效部分。您可以在修订列表中找到它们here).}

Answer 3

这是我的部分代码：

vlist = PossibleValueAtPosition(row,col) # find possible value at location (row, col)

for v in vlist:             # try each possible value

    puzzle[row][col] = v

if SolvePuzzle(n+1)==True:  # n=81 means all filled then end loop

    return True             # if get a solution, you return True

    puzzle[row][col] = 0        # if above return true, this line will never run

    return False                # return False for each fail attemp

主程序应该是这样的

if SolvePuzzle(0)==True:

    print(puzzle)

else:

    print('No solution!')

递归回溯如何工作？电脑爱好者数独解算器

How does Recursive Backtracking work? Computerphile sodoku solver

python

recursion

backtracking

sudoku

recursive-backtracking