python回溯

Question

我最近發佈了幾個問題來理解遞歸和回溯，我覺得我現在得到了一些東西，並試圖編寫一個測試，我確實解決了數獨問題，但是當我以另一種格式編寫代碼時，該代碼會查找一段時間，並返回False，這表示沒有解決此問題的方法。

網格是列表的9x9的列表中，如果表[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]] 

Answer 1

correct_solve縱觀全部併網發電，同時buggy_solve俯瞰一列。這意味着，如果問題還沒有解決，buggy_solve只會在當前列中查找要填寫的單元格 - 如果該列沒有發生空單元格，它將從外部刪除循環和退出，而不使用明確的return語句。因此，如果發生這種情況（並使用適當的return聲明），則需要在下一列調用buggy_solve的代碼。

Answer 2

問題是您的遞歸解決方案從未開始回溯。相反，它會以無盡的遞歸結束，除非它意外地找到一個解決方案 - 這是不太可能的，並且只適用於大部分解決的sudokus。考慮這些情況了，這是發生了什麼事：

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

這buggy_solve的通話將永遠返回false。因爲該函數將繼續嘗試並在必要時遍歷列。當它到達最後一列時，它將從第一個開始，覆蓋之前發生的所有事情。

因此，回溯將永遠不會開始。 check_sudoku很少會失敗，因爲我們還處於處理的早期階段，而且大多數未填充的數獨可能會允許給定單元格中的多個值。

你想要做的就是防止buggy_solve重新開始，即刪除列重置並使其僅針對無效列返回false。這樣buggy_solve將在某個點返回false，並且回溯實際上可以開始。