2

我的数独求解器完全按照它应该做的 - 除了返回正确的东西。它在返回之前打印它应该正确的内容（正确解决的网格），但随后它似乎继续运行一段时间并返回 None。我不知道发生了什么事。

网格是列表的列表。假设如果网格有效（解决与否），check_sudoku 返回 True，否则返回 False。

def solve_sudoku(grid, row=0, col=0):
    "Searches for valid numbers to put in blank cells until puzzle is solved."
    # Sanity check
    if not check_sudoku(grid): 
        return None
    # Sudoku is solved
    if row > 8: 
        return grid
    # not a blank, try next cell
    elif grid[row][col] != 0:
        next_cell(grid, row, col)
    else:
        # try every number from 1-9 for current cell until one is valid
        for n in range(1, 10):
            grid[row][col] = n
            if check_sudoku(grid):
                next_cell(grid, row, col)
        else:
            # Sudoku is unsolvable at this point, clear cell and backtrack
            grid[row][col] = 0
            return

def next_cell(grid, row, col):
    "Increments column if column is < 8 otherwise increments row"
    return solve_sudoku(grid, row, col+1) if col < 8 else solve_sudoku(grid, row+1, 0)
4

2 回答 2

3

您正在调用next_cell递归，但从不返回它的值。

于 2012-07-14T18:38:43.397 回答
2

在我看来，这似乎永远不会真正返回有用的东西。我们第一次输入您的solve_sudoku时，您检查网格是否已解决，如果已解决，则将其返回。在那之后，你开始了一堆递归，最终将在函数结束时返回并返回 None。无论如何，您总是返回 None 。您最终得到的唯一结果是grid您在开始时传入的修改过的参数。

def solve_sudoku(grid, row=0, col=0):
    # possible return at the first entry point
    if not check_sudoku(grid): 
        return None

    # only time you would ever NOT get None
    if row > 8: 
        return grid

    ...recurse...

    # come back out when the stack unwinds,
    # and there is no return value other than None

我推测正在发生的事情是，您正在打印沿途的值，并且您确实在它发生的那一刻正确地看到了一个已解决的网格，但是您的函数没有设置为在完成后正确地完全中断。它会继续循环，直到耗尽某个范围，并且您会看到一堆额外的工作。

重要的是检查递归调用的返回值。如果未解决，或者已解决，您将返回 None grid。就目前而言，您永远不会关心调用范围内的递归结果。

因为我没有关于您的特定代码的所有详细信息，所以这里有一个简单的等价物：

def solver(aList):
    if aList[0] == 10:
        print "SOLVED!"
        return None

    print "NOT SOLVED..."
    return next(aList)

def next(aList):
    # do some stuff
    # check some stuff
    aList[0] += 1
    return solver(aList)


if __name__ == "__main__":
    data = [0]
    solver(data)
    print data

请注意，间接递归调用checker() -> solver()的值一直沿链返回。在这种情况下，我们说的None是解决方法，否则它应该继续递归。您知道在递归堆栈深处的某个时刻，解决方案将得到解决。您需要立即将其传达回顶部。

通信如下所示：

aList == [0]
solver(aList)
  next(...)
    next(...)
      next(...)
        next(...) 
          #SOLVED
        <- next(...)
      <- next(...)
    <- next(...)
  <- next(...)
<-solver(aList)
aList == [10]

如果应用于我的简单示例，您的版本可能如下所示：

aList == [0]
solver(aList)
  next(...)
    next(...)
      # SOLVED
      next(...)
        next(...) 
          ...
        <- next(...)
      <- next(...)
    <- next(...)
  <- next(...)
<-solver(aList)
aList == [10]
于 2012-07-14T19:14:47.147 回答