数独回溯算法与解决方案计数器

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

问题：

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

- user13634030

---

EMPTY的值是多少？在“ if（solver（board，count）> count）”的else条件中，您也应该使用EMPTY而不是0。如果EMPTY不是0，则会使您的代码出错。 - Aziz Sonawalla

谢谢您的提问，EMPTY 表示为 0。您是否有解决主要问题的想法？ - user13634030

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 |

现在看看这是否给你提供了一个解决方案。等等...

简而言之：一旦找到解决方案，您需要使用更严格的约束将其反馈到您的代码中（即强制递增其中一个有效值并查看它是否仍然为您提供另一个解决方案）。

- Aziz Sonawalla

Answer 2

我有完全相同的问题，需要找到多个解决方案的数量，但我有不同的代码，您将如何修改代码以找到所有可能的解决方案并输出解决方案的数量？ 谢谢！ :)

代码：

board = [
    [7,8,0,4,0,0,1,2,0],
    [6,0,0,0,7,5,0,0,9],
    [0,0,0,6,0,1,0,7,8],
    [0,0,7,0,4,0,2,6,0],
    [0,0,1,0,5,0,9,3,0],
    [9,0,4,0,6,0,0,0,5],
    [0,7,0,3,0,0,0,1,2],
    [1,2,0,0,0,7,4,0,0],
    [0,4,9,2,0,6,0,0,7]
]


def solve(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find

    for num in range(1,10):
        if valid(bo, num, (row, col)):
            bo[row][col] = num          

            if solve(bo):                 
                return True

            bo[row][col] = 0              

    return False


def valid(bo, num, pos):
    # Check row
    for field in range(len(bo[0])):                     
        if bo[pos[0]][field] == num and pos[1] != field:
            return False

    # Check column
    for line in range(len(bo)):
        if bo[line][pos[1]] == num and pos[0] != line:
            return False

    # Check box
    box_x = pos[1] // 3
    box_y = pos[0] // 3

    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x * 3, box_x*3 + 3):
            if bo[i][j] == num and (i,j) != pos:
                return False

    return True


def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - - ")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j]) + " ", end="")


def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return (i, j)  # row, col

    return None
if __name__ == "__main__":
    print_board(board)
    solve(board)
    print("___________________")
    print("")
    print_board(board)

- hobbes18

Answer 3

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

以下实现能够解决 这里 给出的唯一可解数独。此外，该算法现在能够解决具有多个解决方案（示例）的数独，并识别出存在多个解决方案的情况。如果是这种情况，程序将只给出其中一个可能的解决方案。

代码如下：

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

这个实现按预期工作（就我所知）。如果您发现任何错误，请留言评论。

- user13634030