带解决方案计数器的数独回溯

Question

背景

我已经实现了一个数独求解器算法（回溯），如下所示：

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

这个解决方案工作正常（它可以解决数独问题）。

我努力实现的目标

我现在想实现算法告诉我，是只有一个解还是多个解。

我试过的

我试图通过将 return 类型更改为 int 并计算可能的解决方案来实现我的目标（在 2 处停止，因为如果有两个解决方案，我可以说有 "multiple" 解决方案）。所以基本上，我只想知道是否有没有、一个或多个解决方案：

// 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”，然后算法停止。

问题

需要对代码进行哪些更改才能使其正常工作？

Answer 1

您的代码的问题是它在找到第一个解决方案后停止 - 更具体地说，您的代码永远不会更改分配给单元格的值，除非它是错误的。这是您实施的标准回溯。您需要做的是，一旦找到一种解决方案，您需要强制您的代码使用其他值并查看它是否也是 return 有效的解决方案。

假设这是数独的最后一行（您缺少最后一个值），并且您的计数当前为 0（即到目前为止没有解决方案）：

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 |

您的代码将为最后一个单元格尝试从 1 到 9 的所有值，一旦发现 9 是正确的值，它将填充它并进行递归调用。

在递归调用中，您的代码不会找到任何空值，因此它会将计数递增 1（因此计数现在为 1）和 return，特别是这一行：return count + 1;因为您此时不进行任何进一步的递归调用，递增的计数将传递到递归堆栈，您最终将得到值 1。

你需要做的是，一旦你找到一个解决方案，你需要再次回溯并强制增加其中一个值。您找到的解决方案中的最后一行如下所示：

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

您不能递增最后一个单元格，因为它已经是 9，所以您将它设置为 0 / EMPTY 并转到之前的值。之前的值是 8，可以增加到 9，所以你这样做然后解决那个板：

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 0 |

也许这不是 return 解决方案，所以您再返回一个（将倒数第二个单元格设置为 0 并递增前一个单元格：

| 1 | 2 | 3 | 4 | 5 | 6 | 8 | 0 | 0 |

现在看看这是否能为您提供解决方案。等等...

TLDR：找到解决方案后，您需要将其反馈给具有更严格约束的代码（即强制增加一个有效值，看看它是否仍然为您提供另一个解决方案）。

Answer 2

感谢 Aziz Sonawalla 的回答，我想我明白了。

以下实现能够解决给定 here. Also the algorithm is now able to solve sudokus with more than one solution (example) 的唯一可解数独问题，并认识到存在不止一种解决方案。如果是这种情况，程序将只给出一种可能的解决方案。

代码如下所示：

// 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中。

此实现按预期工作（据我所知）。如果您发现任何错误，请发表评论。

带解决方案计数器的数独回溯

Sudoku Backtracking with Solution Counter

java

sudoku

backtracking