什么时候递归回溯适当？

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

这看起来像是一个实现问题。检查你正在增加结果的块。你真的想为该单元的每个有效值增加吗？如果存在多个有效值，那么覆盖旧的有效值？