1 
def answer_solve_sudoku(__grid):

    res = check_sudoku(__grid)
    if res is None or res is False:
        return res

    grid = copy.deepcopy(__grid)

    # find the first 0 element and change it to each of 1..9,
    # recursively calling this function on the result
    for row in xrange(9):
        for col in xrange(9):
            if grid[row][col] == 0:
                for n in xrange(1, 10):
                    grid[row][col] = n
                    new = answer_solve_sudoku(grid)
                    if new is not False:
                        return new
                # backtrack
                return False

    # if we get here, we found no zeros and so we're finished
    return grid

这是代码，check_sudoku(grid)如果网格是有效的数独，则可以返回。

我就是看不懂递归部分，我试着在纸上写下过程，但每次都失败，回溯是如何工作的？什么是new？如果answer_solve_sudoku(grid)有效？

我知道它每 0 到 1..9 设置一次，并检查它是否是有效的网格，但我无法在纸上绘制整个过程。并且无法真正理解回溯是如何工作的。

顺便说一句，对理解递归代码有什么建议吗？

最好的祝福，

盛云

编辑

我一遍又一遍地阅读代码，现在我有了一些理解，但我对此不太确定，如果有人给我一些意见，那就太好了。

1，return new只有在求解器找到解决方案时才会调用，并且会在之后立即调用return grid

2、什么时候

# backtrack
return False

叫做？如果下一个解决方案不正确，check_sudoku(__grid)将返回False，如果下一个解决方案正确，它将调用另一个answer_solve_sudoku(grid)解决方案，直到它得到正确的解决方案，当它得到正确的解决方案时，它会return grid然后return new。那么什么时候是：

# backtrack
return False

叫？

4

2 回答 2

1

我有一个更好的建议，而不是写在纸上。格式化代码以向您展示逻辑在做什么的可视化表示。这是一种方法：

def print_counter(val, msg):
    print "%s[%d] %s" % (" "*val, val, msg)

def answer_solve_sudoku(__grid, counter=0):

    res = check_sudoku(__grid)
    if res is None or res is False:
        return res

    grid = copy.deepcopy(__grid)

    for row in xrange(9):
        for col in xrange(9):
            if grid[row][col] == 0:
                for n in xrange(1, 10):
                    grid[row][col] = n
                    print_counter(counter,"test: (row %d, col %d) = %d" % (row,col,n))
                    new = answer_solve_sudoku(grid, counter+1)
                    if new is not False:
                        print_counter(counter, "answer_solve_sudoku() solved: returning")
                        return new
                # backtrack
                print_counter(counter, "backtrack")
                return False

    print_counter(counter, "**SOLVED! Returning back up to top**")
    return grid

from pprint import pprint 
solution = answer_solve_sudoku(easy_grid)
pprint(solution)

我所做的是创建一个小打印机功能，它将打印一个数字并将消息缩进那么多空格。然后在你的 中answer_solve_sudoku，我给它一个默认的计数器值 0，并且总是将 counter+1 传递给每个递归调用。这样，随着深度的增加，数量也会增加。我将打印机功能放在一起以直观地说明正在发生的事情。

你会看到是这样的：

[0] test: (row 0, col 2) = 1
[0] test: (row 0, col 2) = 2
[0] test: (row 0, col 2) = 3
[0] test: (row 0, col 2) = 4
 [1] test: (row 0, col 3) = 1
  [2] test: (row 0, col 4) = 1
  [2] test: (row 0, col 4) = 2
  [2] test: (row 0, col 4) = 3
    ... 
         [45] test: (row 7, col 7) = 8
         [45] test: (row 7, col 7) = 9
         [45] backtrack
        [44] test: (row 7, col 5) = 6
        [44] test: (row 7, col 5) = 7
    ... 
               [51] test: (row 8, col 6) = 6
               [51] test: (row 8, col 6) = 7
                [52] **SOLVED! Returning back up to top**
               [51] answer_solve_sudoku() solved: returning
              [50] answer_solve_sudoku() solved: returning
             [49] answer_solve_sudoku() solved: returning
    ... 
  [2] answer_solve_sudoku() solved: returning
 [1] answer_solve_sudoku() solved: returning
[0] answer_solve_sudoku() solved: returning

return new 只会在求解器找到解决方案时调用，这将在返回网格之后立即调用

是的，当调用answer_solve_sudoku通过整个循环而没有失败并到达底部时，它已经成功并返回网格。然后，调用者将获得该网格作为结果new = answer_solve_sudoku(grid)并将其返回。网格将备份堆栈上的每个返回调用。

什么时候会发生回溯？

因为您在每次递归中创建网格的副本，除非该步骤找到解决方案，否则它对该网格所做的更改将被丢弃，因为一旦我们返回一个步骤，我们将回到我们之前的网格状态。它会尽可能地使用该解决方案，直到它超过 9 的值。

于 2012-07-17T18:00:41.967 回答
1

你应该看看这个答案。它具有用于递归回溯的伪代码和实际代码。代码是用 Java 编写的，但 Python 的思维过程是相同的。

于 2012-07-17T18:01:43.933 回答