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

问题

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

Answer 1

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

假设这是您数独的最后一行(您缺少最后一个值)，并且您的计数目前为 0(即目前没有解决方案):

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

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

在递归调用中，您的代码将找不到任何空值，因此它将计数增加 1(因此计数现在为 1)并返回，特别是这一行: 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 |

也许这不会返回解决方案，因此您再返回一个(将倒数第二个单元格设置为 0 并增加前一个单元格:

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

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

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