2
我很轻松地制作了Sudoku检查器/求解器，但是我需要一个能够告诉我有多个解决方案的解决方案，并且无法将其包裹在它周围。我发现了一个工作算法，但我试图理解它为什么工作。这是从this question，答案由@fabianJava：递归数独解法计数算法
复制以下提供：
// 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;
}
我想实现它，因为它应该，它的工作原理。然而，尽管我认为我明白代码的每个部分都是，但我无法理解它为什么可行。
第一个：第一个if语句在达到第2个数组中的最后一个数字后停止该方法。我找到了这个解决方案，但是为什么它能够找到多个解决方案？找到解决方案后，该方法不应该返回0 + 1 = 1吗？
二：if (cells[i][j] != 0)后为什么递归调用solve(...)需要在它前面return声明？我做了几个递归算法，但总是通过再次调用该方法。
第三：如果没有找到合适的数字，则for循环停止，并且0被输入到单元格位置。由于它应该已经有0，不应该回溯到0而不是当前的最后一个地方？至少我是这样解决自己的问题的。
第四：在回溯设置后，只有return count。为什么程序还在工作？不应该只是返回count = 0，并在面对不允许任何数字的第一个地方后停止？如何在最后没有递归调用？
如果你在这个棘手的问题上做得这么远，很显然，我理解一些完全错误的东西。我非常感谢帮助/解释，因为使用代码不理解的代码是完全失败的。