java - 检测无限循环？

Question

我正在开发数独求解器程序。这个想法是用户输入数独谜题，然后程序为他们解决。

程序在输入任何普通拼图时运行良好。然而，有些谜题是无法解开的。这是我输入的一个示例:http://i.imgur.com/5L8pF8Q.png

输入完全合法，但右上角的方 block 无法填写，因为所有数字 1-9 都已在该行和列中使用。如果我点击“解决”，我的程序会在进入无限循环时卡住。

所以我的问题是，如何防止这种情况发生？

我尝试实现“boolean 标志”方法，但转念一想我意识到这可能不可行。

这是我的求解器方法:

public boolean solve(int i, int j) {
    for (int a = 0; a < 9; a++) {
        for (int b = 0; b < 9; b++) {
            if (sudokuArray[a][b] == 0) {
                for (int k = 1; k <= 9; k++) {
                    sudokuArray[a][b] = k;
                    if (checkNumber(a, b, k) && solve(a, b)) {
                        return true;
                    }else {
                        sudokuArray[a][b] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

checkNumber() 方法检查数字 k 是否可以合法地插入 a 行，b 列并相应地返回 true/false。

想法？提示？

谢谢。

PS:根据要求添加了checkNumber():

public boolean checkNumber(int i, int j, int num) {
    for (int a = 0; a < 9; a++) {
        if (a != i) {
            if (sudokuArray[a][j] == num) {
                return false;
            }
        }
        if (a != j) {
            if (sudokuArray[i][a] == num) {
                return false;
            }
        }
    }
    for (int a = (i / 3) * 3; a < (i / 3) * 3 + 3; a++) {
        for (int b = (j / 3) * 3; b < (j / 3) * 3 + 3; b++) {
            if ((a != i) && (b != j)) {
                if (sudokuArray[a][b] == num) {
                    return false;
                }
            }
        }
    }
    return true;
}

Answer 1

这只是一个想法(我会发表评论，但这个帐户太新了)。尝试这样做，如果 0-9 的所有数字都返回 false，那么它会返回某种错误。例如，如果到 9 还没有找到答案，则向上移动到 10。如果程序检测到 10，则执行某种 System.out.println("Unsolvable") 或类似的操作。对不起，如果我让你感到困惑。有人告诉我我不善于解释事情。