确定数独是否具有独特的解决方案

Question

我正在努力使用回溯算法来确定数独是否具有唯一的解决方案，或者它是否具有多个解决方案。这是我使用的回溯代码：

    static boolean solve(int i, int j, int[][] cells) {
    if (i == 9) {
        i = 0;
        if (++j == 9)
            return true;
    }
    if (cells[i][j] != 0)  // skip filled cells
        return solve(i+1,j,cells);

    for (int val = 1; val <= 9; ++val) {
        if (legal(i,j,val,cells)) {
            cells[i][j] = val;
            if (solve(i+1,j,cells))
                return true;
        }
    }
    cells[i][j] = 0; // reset on backtrack
    return false;
}

第一种方法：如果我改变

for (int val = 1; val <= 9; ++val) {
for (int val = 9; val >= 1; val--) {

我得到两个不同的求解算法，它们应该找到不同的解决方案（如果存在不同的解决方案）。这种方法的问题是，即使算法稍有变化，算法也不会终止，我也不知道为什么。

第二种方法：重置回溯并继续寻找解决方案。如果我尝试这样做，也不会起作用。

我试图找到一个Java示例，但是我只能找到诸如“在回溯时重置并继续寻找第二个解决方案”之类的信息。

有人可以提供一个示例，说明如何更改算法，以便告诉我是否存在多个解决方案（不需要确切的数字）

要么

有人可以向我解释为什么我的第一种方法没有终止吗？

谢谢！

Answer 1

如果您返回数字而不是布尔值，则可以区分存在0、1或多于1个解决方案的情况。

// 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;
}