Java:递归数独计算算法

Question

我轻松地制作了数独检查器/解算器，但我需要一个能判断是否有不止一个解决方案的算法，而且我无法理解它。我找到了一个有效的算法，但我正在努力理解它为什么有效。这是这个问题的答案，由@fabian 提供

复制如下：

// returns 0, 1 or more than 1 depending on whether 0, 1 or more than 1 solutions are found
static byte solve(int i, int j, int[][] cells, byte count /*initailly called with 0*/) {
    if (i == 9) {
        i = 0;
        if (++j == 9)
            return 1+count;
    }
    if (cells[i][j] != 0)  // skip filled cells
        return solve(i+1,j,cells, count);
    // search for 2 solutions instead of 1
    // break, if 2 solutions are found
    for (int val = 1; val <= 9 && count < 2; ++val) {
        if (legal(i,j,val,cells)) {
            cells[i][j] = val;
            // add additional solutions
            count = solve(i+1,j,cells, count));
        }
    }
    cells[i][j] = 0; // reset on backtrack
    return count;
}

我试着实现了它，而且它应该是有效的。然而，尽管我认为我理解代码的每个部分的作用，但我不明白它为什么有效。

第一个：一旦达到2d数组中的最终数字，第一个if语句就会停止该方法。我从找到一个单一的解决方案中得到了这一点，但为什么它能在找到多个解决方案中起作用呢？在找到解决方案后，该方法不应该只返回0+1=1吗？

第二个：在if (cells[i][j] != 0)之后，为什么递归solve(...)调用前面需要return语句？我已经做了几个递归算法，但总是通过再次调用该方法。

第三：如果没有找到合适的数字，则for循环停止，0输入到单元格位置。既然它应该已经有0了，那么回溯不应该把0放在最后一位而不是当前位置吗？至少这就是我自己制作的求解器的方式。

第四：在回溯集之后，只有return count。为什么程序仍然有效？它不应该只返回count＝0，然后在面对不允许任何数字的第一名后停止吗？为什么结尾没有递归调用？

如果你在这个棘手的问题上做到了这一点，很明显，我对一些事情的理解是完全错误的。我非常感谢您的帮助/解释，因为就学习代码而言，使用不理解的代码是完全失败的。

Answer 1

好吧，谷歌优雅地提供了哈佛大学的Powerpoint讲座：http://www.fas.harvard.edu/~cscie119/讲座/recursion.pdf

如果其他人在递归回溯方面遇到问题，我建议您检查一下。非常简短，但内容丰富。

我的问题似乎只是我愚蠢地（至少事后看来）假设该方法在递归调用自己后停止。我忘记了，在它从递归调用中得到结果后，它会一直执行到最后。有趣的是，仅仅因为你最初的思维过程有缺陷，你就可以用无数个小时来解决问题。好吧，我想，生活和学习。