python中的奇怪遞歸行爲

Question

我的數獨解算器完全按照它應該做的 - 除了返回正確的東西。它打印什麼它應該在返回之前（一個正確解決的網格），但它似乎保持運行一點，並返回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) 

Answer 1

在我看來，這將永遠不會返回有用的東西。我們第一次輸入您的solve_sudoku時，您會檢查網格是否已解決，如果有，請將其退回。之後，你開始一堆遞歸，最終會回到函數結束並返回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] 

Answer 2

您在遞歸中調用next_cell，但從不返回它的值。