递归回溯如何工作?电脑爱好者数独解算器 [英] How does Recursive Backtracking work? Computerphile sodoku solver

问题描述

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

I'm so confused by backtracking because when the recursive call returns, won't you replace the solution found by replacing the grid back to zero. So even if you find the solution would it not be erased because after calling the solve function you are canceling what you did by replacing the value back to zero. I get the fact that you are backtracking but on the final recursive call that contains all the correct values are you not just replacing everything to 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 教授在 Computerphile 视频上的代码阿尔滕基希.

This was the code on Computerphile video by Prof. Thorsten Altenkirch.

推荐答案

这是奇怪的代码，但应该可以进行一些调整:

This is weird code, but should work with some adaptations:

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

这篇关于递归回溯如何工作?电脑爱好者数独解算器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！