2

最近发了几个关于递归和回溯的问题，感觉现在有所收获，试着写了一个测试，确实解决了数独问题，但是当我写成另一种格式的代码时，代码卡住了while 并返回 False，表示此问题没有解决方案。

grid 是一个 9x9 的列表列表，如果 list[i][j] 为零，则表示需要填写。

这是解决问题的代码：

def correct_solve(grid):

    # if there is no more zeros
    if found_solution(grid):
        return True

    for row in xrange(9):
        for col in xrange(9):
            if grid[row][col] == 0:
                for num in xrange(1, 10):
                    grid[row][col] = num
                    if check_sudoku(grid) == True:
                        if correct_solve(grid) == True:
                            return True
                # there are no numbers which could make
                # a valid solution, so backtrack
                grid[row][col] = 0
                return False

这是另一个功能，我尝试以不同的方式解决问题，但失败了，我找不到问题出在哪里

def buggy_solve(grid, col):

    # if there is no more zeros
    if found_solution(grid):
        return True

    # if the col is over 8, make it to 0
    if col > 8:
        col = 0

    for row in xrange(9):
        if grid[row][col] == 0:
            for num in xrange(1, 10):
                grid[row][col] = num
                if check_sudoku(grid) == True:
                    # I tend to move to the next cell, and it seems that
                    # this is correct.
                    if buggy_solve(grid, col + 1) == True:
                        return True

            # if there are no valid solutions, backtrack.
            grid[row][col] = 0
            return False

我试图调试程序并没有发现任何有用的东西，顺便说一句，调试一段递归代码有什么好的做法吗？

编辑：

这是我用来测试的矩阵：

easy = [[2,9,0,0,0,0,0,7,0],
        [3,0,6,0,0,8,4,0,0],
        [8,0,0,0,4,0,0,0,2],
        [0,2,0,0,3,1,0,0,7],
        [0,0,0,0,8,0,0,0,0],
        [1,0,0,9,5,0,0,6,0],
        [7,0,0,0,9,0,0,0,1],
        [0,0,1,2,0,0,3,0,6],
        [0,3,0,0,0,0,0,5,9]]
4

2 回答 2

1

correct_solve查看整个网格，同时buggy_solve查看单个列。这意味着，如果问题还没有解决，buggy_solve只会在当前列中查找要填充的单元格——如果该列恰好没有空单元格，它将退出外部 for 循环并退出，而不使用显式return语句。因此，当发生这种情况时，您需要代码调用buggy_solve下一列（并使用适当的return语句）。

于 2012-07-18T09:59:01.360 回答
0

问题是您的递归解决方案永远不会开始回溯。相反，除非它意外地找到解决方案，否则它将以无休止的递归告终——这是非常不可能的，并且仅适用于大多数已解决的数独游戏。排除这些情况，这就是正在发生的事情：

if buggy_solve(grid, col + 1) == True:
    return True

这个buggy_solve调用永远不会返回 false。因为如果需要，该函数将继续尝试和迭代列。当它到达最后一列时，它将再次从第一列开始，覆盖之前发生的一切。

因此，回溯永远不会开始。check_sudoku鉴于我们仍处于处理的早期阶段，并且大多数未填充的数独可能会在给定单元格中允许多个值，因此很少会失败。

您想要做的是防止buggy_solve重新开始，即删除列重置并使其简单地为无效列返回 false。这种方式buggy_solve会在某个时候返回 false 并且回溯实际上可以开始。

于 2012-07-18T10:38:53.513 回答