我正在为一个班级制作一个 SudokuSolver，但我在解决方法时遇到了问题。我目前的解决方案使用递归回溯（我认为）。
作业要求
int solve() -- 尝试使用上述策略解决难题。返回解决方案的数量。
（上述策略）
为点分配数字时，切勿分配在那个时刻与点的行、列或正方形发生冲突的数字。我们预先小心地为一个点分配合法数字，而不是分配任何数字 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);
}
试验结果
testSolveSingleSolution
expected 1, actual 1
testSolveSolved
expected 1, actual 1
testSolveUnsolvable
expected 0, actual 0
testSolveMultiSolutions
expected 2, actual 7 // MAJOR PROBLEM!
递归回溯的一些很好的解释
- StackOverflow 的这个答案- 数独生成器的递归解决方案
- StackOverflow 的这个答案- 迷宫中的回溯
- StackOverflow的这个答案- 素数序列的回溯算法
- StackOverflow 的这个答案- 如何仅通过此回溯找到第一个解决方案
- 维基百科关于回溯的文章
- 递归回溯解释
问题
我以前做过递归回溯，我已经查看了上面的所有链接等等，但我仍然遇到问题。我认为问题在于我在思考如何解决这个问题。（请参阅伪代码理念。）使用递归回溯进行穷举搜索是否合适？回溯是正确的，但执行是错误的吗？有没有比递归回溯更好的算法？