递归回溯是如何工作的?电脑爱好者的数独求解器

Question

我对回溯很困惑，因为当递归调用返回时，你不会将通过将网格替换回零找到的解决方案吗。因此，即使你找到了解决方案，它也不会被删除，因为在调用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教授在电脑爱好者视频中的代码。

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

这是我的代码的一部分：

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!')

Answer 3

包含所有正确值的不是最终递归调用，而是(每个(最深的。是的，此代码列举了所有具有给定板grid的谜题解决方案，而不仅仅是第一个解决方案。

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

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

当已经尝试了从1到9的所有数字时，当前调用已经运行。但递归链中位于其上方的一个正在等待继续其工作，试图填充其(y,x)位置。我们必须让它在调用solve()之前的同一块板上工作。该调用在板上所做的唯一更改是将其(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上的前两个嵌套循环完成。这有点多余；我们知道在这个CCD_ 16之前的所有位置已经被填充。该代码将被更好地重构以将起始位置(y,x)作为参数传递给solve。

递归回溯的范例是美丽的。Prolog充满了神秘感，Haskell会用神秘的单体语言让你眼花缭乱(单体实际上只是可解释的嵌套数据(，但这里只需要递归创建一些嵌套循环！

这个范式很漂亮，但这个代码就不那么漂亮了。代码的视觉结构应该反映其真实的计算结构，但这段代码给你的印象是，y-x-循环是用来创建回溯结构的嵌套循环，它们是而不是(它们只是按照自上而下的从左到右的顺序对下一个空格进行一次性线性搜索(。

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

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

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