何时使用递归回溯算法？

Question

何时使用递归回溯算法？

javarecursionbacktracking

11

我正在为一门课程制作数独求解器，但是我的解决方法在solve方法上有问题。我目前的解决方法使用了递归回溯（我想）。

任务要求

int solve() -- 尝试使用上述策略解决谜题。返回解的数量。

（上述策略如下）

当给一个格子分配数字时，从不分配与该行、列或宫冲突的数字。我们事先小心地将合法数字分配给一个格子，而不是分配任何数字 1..9 并在递归中后来才发现问题。假设初始网格都是合法的，在此之后只进行合法的格子分配。

伪代码思路

对于小输入，我可以按迭代方式遵循这个策略。例如，假设我有两个未解决的单元格Cell＃1和Cell＃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-迷宫中的BackTracking
这个答案来自StackOverflow - 素数序列的回溯算法
这个答案来自 StackOverflow - 如何只用这种回溯找到第一个解
维基百科文章回溯法
递归回溯解释

问题

我以前做过递归回溯，我看了上面所有的链接以及更多内容，但我仍然有困难。我认为问题在于我的思考如何解决这个问题（请参见伪代码想法）。对于穷举搜索，使用递归回溯是否合适？回溯是否正确但实现不正确？是否有比递归回溯更好的算法？

- Eva

回溯法是一种合理的方法，如果您能够剪枝搜索的话。 - nikhil

1

它是一个不可或缺的部分，但它唯一的作用就是帮助提高性能（在最坏情况下，你基本上必须搜索整个树才能找到正确的解决方案；与对抗游戏相反，在给定时间段内，你不一定需要“最佳”可能的移动，只需要找到最好的移动即可）。仅允许有效的移动已经是一种修剪。无论如何，如果你得到了错误的结果，那不是原因（除非你有一个错误）。可能的算法来解决它。 - Voo

1

使用精确覆盖来解决数独问题非常有趣，而且比暴力递归解法更加有收获，因此你可能想要深入了解一下 - 它也可以立即解决任何类型的9x9难题（话虽如此，即使是最坏情况的数独问题，也可以通过良好编写的暴力递归方法在几秒钟内解决）。 - Voo

@Voo 感谢提供链接。不幸的是，我太蠢了，一点也看不懂。 - Eva

1

@Eva 不错的链接 - 虽然集合论解释具有简洁和准确的优点，但我可以理解为什么有些人更喜欢更详细的描述。而且，写那篇文章的人非常好地解释了这个问题。很高兴听到你已经找到了一个可行的解决方案，并同时学习了一个非常有用的新概念。 - Voo

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thomas · Accepted Answer

这看起来像是一个实现问题。检查你增加结果的块。你真的想为该单元格的每个有效值都增加吗？就此而言，如果有几个有效值，你是否要覆盖旧的有效值？