java - 带解计数器的数独回溯

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

该解决方案运行良好（它可以解决数独问题）。

我试图达到的目标

我现在想要实现算法告诉我的，是否只有一个解决方案或多个解决方案。

我试过的

我试图通过将返回类型更改为 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”，然后算法停止。

问题

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

标签： javabacktrackingsudoku

Answer 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：一旦你找到了一个解决方案，你需要用更严格的约束将它反馈给你的代码（即强制增加一个有效值，看看它是否仍然给你另一个解决方案）。