11

我正在为一个班级制作一个 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!

递归回溯的一些很好的解释

问题

我以前做过递归回溯，我已经查看了上面的所有链接等等，但我仍然遇到问题。我认为问题在于我在思考如何解决这个问题。（请参阅伪代码理念。）使用递归回溯进行穷举搜索是否合适？回溯是正确的，但执行是错误的吗？有没有比递归回溯更好的算法？

4

1 回答 1

0

这看起来像是一个实现问题。检查要增加结果的块。您真的要为该单元格的每个有效值递增吗？如果有几个有效值，那么覆盖旧的有效值？

于 2012-07-17T16:49:18.683 回答