背景资料
我已经实现了一个数独解算器算法（回溯），看起来像这样。
//Backtracking-Algorithm
public static boolean solver(int[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0) {
for (int n = 1; n < 10; n++) {
if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {
board[i][j] = n;
if (!solver(board)) {
board[i][j] = 0;
} else {
return true;
}
}
}
return false;
}
}
}
return true;
}
这个方法很好用（它可以解决数独）。
我试图实现的是
我现在想实现的是，算法告诉我，到底是只有一个解还是多个解。
我试过的
我试图通过将返回类型改为int，并计算可能的解决方案来实现我的目标（停止在2，因为如果有两个解决方案，我可以说有 "多个 "解决方案）。所以基本上，我只想知道是没有、一个还是多个解。
// Backtracking-Algorithm
public int solver(int[][] board, int count) { //Starts with count = 0
if (count < 2) {
for (int i = 0; i < GRID_SIZE; i++) {
for (int j = 0; j < GRID_SIZE; j++) {
/*
* Only empty fields will be changed
*/
if (board[i][j] == EMPTY) {
/*
* Try all numbers between 1 and 9
*/
for (int n = 1; n <= GRID_SIZE; n++) {
/*
* Is number n safe?
*/
if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {
board[i][j] = n;
if (solver(board, count) > count) {
count++;
} else {
board[i][j] = 0;
}
}
}
return count;
}
}
}
return count + 1;
}
return count;
}
问题是... count 始终为 "1"，然后算法停止。
疑问
在代码中需要做哪些修改才能使其工作？
你的代码的问题是它在找到第一个解之后就停止了--更具体地说，你的代码永远不会改变一个单元格的赋值，除非它是错误的。这是标准的回溯，你已经实现了。你需要做的是，一旦你找到一个解，你需要强制你的代码使用其他值，看看它是否也返回一个有效的解。
假设这是你的数独的最后一行（你缺少最后一个值），而你的计数目前是0（即到目前为止没有解）。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 |
你的代码会尝试最后一个单元格的1 -9的所有值 一旦发现9是正确的值 它就会填入并进行递归调用。
在递归调用中，你的代码将不会找到任何空值，所以它将把count递增1（所以count现在是1）并返回，特别是这一行。return count + 1;因为此时你不会再进行任何递归调用，所以递增的count会在递归堆栈中传递给你，而你最终会得到一个1的值。
你需要做的是，一旦你找到了一个解决方案，你需要再次回溯并强制递增其中一个值。你找到的解决方案中的最后一行是这样的。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
你不能递增最后一个单元格，因为它已经是9了 所以你把它设为0 EMPTY，然后回到之前的值。前一个值是8，可以递增到9，所以你就这样做，然后解决这块板。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 0 |
也许这并没有返回一个解决方案，所以你再返回一个（将最后一个单元格设置为0，然后递增前一个单元格）。
| 1 | 2 | 3 | 4 | 5 | 6 | 8 | 0 | 0 |
现在看看这是否能给你一个解决方案 以此类推...
TLDR：一旦你找到了一个解决方案，你需要用更严格的约束条件将其反馈给你的代码（即强制递增其中一个有效值，看看它是否仍然给你另一个解决方案）。
感谢 这个 由Aziz Sonawalla回答，我想我想明白了。
下面的实现能够解决给定的唯一可解的数独。此处. 此外，该算法现在能够解决多于一个解的sudokus (例子)并识别出有多个解。如果是这种情况，程序将只给出其中一个可能的解决方案。
代码看起来像这样。
// Backtracking-Algorithm
public int[][] board2 = new int[GRID_SIZE][GRID_SIZE];
public int solver(int[][] board, int count) { // Starts with count = 0
for (int i = 0; i < GRID_SIZE; i++) { //GRID_SIZE = 9
for (int j = 0; j < GRID_SIZE; j++) {
/*
* Only empty fields will be changed
*/
if (board[i][j] == EMPTY) { //EMPTY = 0
/*
* Try all numbers between 1 and 9
*/
for (int n = 1; n <= GRID_SIZE && count < 2; n++) {
/*
* Is number n safe?
*/
if (checkRow(board, i, n) && checkColumn(board, j, n) && checkBox(board, i, j, n)) {
board[i][j] = n;
int cache = solver(board, count);
if (cache > count) {
count = cache;
for (int k = 0; k < board.length; k++) {
for (int l = 0; l < board.length; l++) {
if (board[k][l] != EMPTY) {
board2[k][l] = board[k][l];
}
}
}
board[i][j] = EMPTY;
} else {
board[i][j] = EMPTY;
}
}
}
return count;
}
}
}
return count + 1;
}
解决方案被保存在数组中 board2 现在。
这个实现是按照预期工作的（据我所知）。如果你发现任何错误，请留言。