如何解決深度優先數獨解決？

Question

我正嘗試在Python中創建一個數獨謎題求解器，它使用depth-first「蠻力」來解決這個難題。然而，在重新編碼多次之後，我會一遍又一遍地提出同樣的錯誤。

我會盡我所能地儘可能清楚地解釋問題 - 因爲這是我的第一個與深度優先搜索有關的問題，可能是我錯過了一些明顯的東西。

這裏是裁切下來的代碼（與在細節是沒有必要的地方僞代碼混合）：

def solvePuzzle(puzzle): 
    <while the puzzle is still not solved>: 
     <make a copy of the puzzle> 
     <go through each unsolved box>: 
      <try to find the value of the box> 
      <if the current solution is impossible, return to the parent branch> 
     <if the copy of the puzzle is exactly the same as the puzzle now, no changes have been made, so its time to start branching into different possibilities>:  
      <pick a random box to guess the number of> 
      <go through each possible value and run solvePuzzle() on that puzzle>: 
       <if a solution is returned, return it> 
       <else, try the next possible value> 
    <return the puzzle> 

這是因爲砍掉，因爲我可以把它 - 對不起，如果它仍然是一個有點的閱讀/困惑。

出於某種原因，甚至設置程序solvePuzzle（）拼圖的每一創建的副本後，發現所有的拷貝都不可能（通過是不可能的，我的意思是錯誤的猜測已經取得）。這是不可能的，因爲每個數字都在測試！

Here's the full code（只有大約50行代碼），以防萬一不夠清楚。

如果任何人甚至可以建議爲什麼這不起作用，我會非常感激。

謝謝！

編輯：As promised, here's the "isSolved()" method.

Answer 1

我強烈懷疑問題就在這裏：

# Go through each possibility in the branch until one solution is found 
clone = deepcopy(puzzle) 
values = clone[index/9][index % 9] 
for value in values: 
    clone[index/9][index % 9] = value 
    branch = solvePuzzle(clone) 
    # If a list is returned, it worked! Otherwise, try the next possibility 
    if isinstance(branch, list): 
     return branch 

那變異的clone副本的每個候選值，並且不會恢復到半解謎狀態當它發現矛盾時。試試這個：

# Go through each possibility in the branch until one solution is found 
values = puzzle[index/9][index % 9] 
for value in values: 
    clone = deepcopy(puzzle) 
    clone[index/9][index % 9] = value 
    branch = solvePuzzle(clone) 
    # If a list is returned, it worked! Otherwise, try the next possibility 
    if isinstance(branch, list): 
     return branch