什麼時候遞歸回溯適當？

Question

我爲一個班級製作了SudokuSolver，並且遇到了解決方法問題。我目前的解決方案使用遞歸回溯（我認爲）。

分配要求

INT解決（） - 試圖解決使用上述策略了這個難題。返回解決方案的數量。

（上面描述的策略）

當指定一個數字以一個點，從未分配一個編號的是，在那一刻，與點的行，列，或方形的衝突。我們在分配合法數字到現場時要小心，而不是分配任何數字1..9，並在遞歸後期找到問題。假設初始網格全部合法，並且此後僅進行合法的現場分配。

僞理念

我可以按照這個反覆的小的輸入。例如，說我必須解決單元格＃1和單元＃2。 ＃1有可能性{1,3}，＃2有可能性{2,3}。然後我會

set 1 to 1 
    set 2 to 2 
     hasConflicts? 0 : 1 
    set 2 to 3 
     hasConflicts? 0 : 1 
set 1 to 3 
    set 2 to 2 
     hasConflicts? 0 : 1 
    set 2 to 3 
     hasConflicts? 0 : 1 

實際代碼

public int solve() { 
    long startTime = System.currentTimeMillis(); 
    int result = 0; 

    if (!hasConflicts()) { 
     Queue<VariableCell> unsolved = getUnsolved(); 
     reduceUnsolvedPossibilities(unsolved); // Gets the possibilities down from all of 1-9 

     if (!hasConflicts()) { 
      result = solveRec(unsolved); 
     } 
    } 

    mElapsedTime = System.currentTimeMillis() - startTime; 
    return result; 
} 

protected int solveRec(Queue<VariableCell> unsolved) { 
    if (unsolved.isEmpty()) { 
     return (hasConflicts()) ? 0 : 1; 
    } 

    int result = 0; 
    VariableCell cell = unsolved.remove(); 
    Iterator<String> possibilityIt = cell.getPossibilities().iterator(); 

    while (possibilityIt.hasNext()) { 
     cell.setSymbol(possibilityIt.next()); 

     if (hasConflicts()) { 
      possibilityIt.remove(); 
     } else { 
      ++result; 
     } 
    } 

    return result + solveRec(unsolved); 
} 

測試結果遞歸回溯的

• This answer到StackOverflow上

  testSolveSingleSolution 
      expected 1, actual 1 
  
  testSolveSolved 
      expected 1, actual 1 
  
  testSolveUnsolvable 
      expected 0, actual 0 
  
  testSolveMultiSolutions 
      expected 2, actual 7 // MAJOR PROBLEM! 
  

  一些好解釋 - 遞歸解決數獨發電機

• This answer來的StackOverflow - 回溯在迷宮
• This answer來的StackOverflow - 回溯算法的黃金序列
• This answer到StackOverflow上 - 如何找到第一個解決方案只能用這種回溯
• 維基百科的文章Backtracking
• Recursive Backtracking Explanation

問題

我已經完成了遞歸回溯，我已經查看了上面的所有鏈接以及更多，而且我仍然遇到了麻煩。我認爲問題在於我如何解決這個問題。 （請參閱僞代碼想法。）使用遞歸回溯進行徹底搜索是否合適？回溯正確但實施錯誤？有沒有比遞歸回溯更好的算法？

Answer 1

這看起來像是一個實現問題。檢查你正在增加結果的塊。你真的想爲該單元的每個有效值增加嗎？如果存在多個有效值，那麼覆蓋舊的有效值？