Python的數獨遞歸，以蠻力回溯錯誤

Question

我做功課一道數獨題求解，但我遇到了一些困難。現在的代碼循環通過解決方案，雖然它確實達到了它的容易謎題，而對於更難的謎題，它沒有明顯的原因卡住了幾個9。我將不勝感激任何幫助。 （check_cell確定該位置是否有效。）

1. 是回溯這段代碼正確實施，如果沒有，怎麼會縫？
2. 如何阻止求解器凍結？它解決了大約3行然後凍結，將大部分值更改爲9。

一些代碼：

def solve_helper(self, row, col): 
# Try placing a number in each column of current row 
    board = self.the_board 
    if board[row][col] != 0: 
     ????? 
    elif board[row][col] == 0: 
     for i in range(1,10): 
      print("Setting value at i with ") + str (i) + (" located at ") + str(row) + str(col) 
      self.set_cell(row, col, i) 
      self.guesses = self.guesses + 1 
      if self.check_cell(row, col): 
       if self.solve_helper(row, col): return True 
      else: 
       self.set_cell(row, col, 0) 
    else: 
     return self.mover(row,col) 
    return False 

def mover(self, row, col): 
    if col + 1 != 9: 
     return self.solve_helper(row, (col+1)) 
    elif row + 1 != 9: 
     print "Moving to row" + str(row + 1) 
     return self.solve_helper((row+1),0) 
    else: 
     print "SOLUTION FOUND" 
     return True 

Answer 1

你遇到麻煩的是，你的一些遞歸調用沒有返回結果正常，那麼你的解決方案，當它被發現，被遺忘了幾遞歸堆棧。這裏有您需要的第一個定位，增加return在mover所做的遞歸調用：

def mover(self, row, col): 
    if col + 1 != 9: 
     return self.solve_helper(row, (col+1)) # added return 
    elif row + 1 != 9: 
     print "Moving to row" + str(row + 1) 
     return self.solve_helper((row+1),0)  # here too 
    else: 
     print "SOLUTION FOUND" 
     return True 

你還需要在你跳過預先解決您的細胞功能solve_helper的特殊情況下，類似的東西。該函數的結尾應爲：

else: 
    return self.mover(row, col) # added return 
return False 

編輯：

好吧，我發現代碼中的幾個問題。其中兩個是求解器的邏輯問題，另一個是顯示問題，除了在求解期間看起來奇怪外，不會引起任何實際問題。

的問題：

1. 首先，你最新的代碼solve_helper自稱，而不是調用mover。這使得它在移動之前需要額外的函數調用（儘管我認爲它可能實際上並不打破解算器）。
2. 其次，如果solve_helper將單元格設置爲9，但隨後回溯到（稍後一些單元格無法解析之後），則在進一步回溯之前，9不會重置爲零。
3. 最後，顯示問題。將單元格設置爲0不會停止顯示舊值。這看起來很像第二個問題，（回溯後有9個被留下），但實際上它只是表面化妝。

第一個問題很容易解決。相反，只需將solve_helper呼叫更改爲mover。這實際上就是您在問題中提出的原始代碼中的含義。直接調用solve_helper實際上並沒有得到錯誤的結果（因爲solve_helper將第二次跳過已經填充的單元格），但它會爲遞歸的每個級別添加一個不必要的額外函數調用。

第二個問題是一個有點複雜，這是你被卡住了一些板在哪裏。你需要做的就是將self.set_cell(row, col, 0)這一行移出它當前所在的else塊。實際上，如果你想要的話，你實際上可以將它完全移到循環之外（因爲如果你願意的話，它確實是必須的）在沒有任何當前單元格的值工作後回溯）。以下是我認爲這是在for循環（也移動return False聲明上）最好的安排：

for i in range(1,10): 
    print("Setting value ") + str (i) + (" at ") + str(row) + ", " + str(col) 
    self.set_cell(row, col, i) 
    self.guesses = self.guesses + 1 
    if self.check_cell(row, col): 
     if self.mover(row, col): 
      return True 
print "Backtracking" 
self.set_cell(row, col, 0) 
return False 

最後，固定顯示問題需要兩個變化。首先，擺脫set_cell的條件。您想要始終更新顯示。接下來，在update_textfield中，將delete呼叫移動到if塊之外，以便始終發生（將insert保留在if之下）。這使得將單元格設置爲零將刪除以前的值，但不會使其顯示實際的0字符（它不會顯示任何內容）。

我想這應該這樣做。請注意，您使用的算法仍然很慢。解決a board I found on the internet in a quick Google search花了122482次猜測和超過5分鐘，但它終於工作。其他電路板（特別是那些在開放空間中需要8s或9s的電路板）可能需要更長的時間。