通过回溯解决数独 (java)

Question

public static int[][] solve(int[][] input){

        for (int i = 0; i < 9*9; i++){
            if(input[i / 9][i % 9] != 0){
                continue;
            }
            for (int j = 1; j <= 9; j++){
                    if(validNumber(input, i / 9, i % 9, j)){
                        input[i / 9][i % 9] = j;
                        solve(input);
                    }
            }
        }
        return input;
    }

无论初始情况如何，此方法都应通过回溯解决（可解决的）数独难题。它是这样工作的：

给定一个数独游戏，它从每行的左上角迭代到二维数组的右下角。当已经有一个数字时，它会被跳过。当存在零（空字段）时，它通过 validNumber 方法计算可能的值。第一个有效数字（从 1 到 9）被放入该字段，该方法转到下一个字段。

在此算法中，该方法现在不考虑有效数字是否最终会导致拼图无法解决。

我想这样修改它：

最后，当该方法完成对整个二维数组的迭代时，将测试数组的每个条目是否为零。

即使有一个零，整个算法也必须转到第一个 "valid" 数字被放入的地方。现在，下一个 "valid" 数字被放入，依此类推，直到算法末尾没有零。

我在实现这个想法时遇到了一些麻烦。在我看来，某处必须有另一个 for 循环，或者类似 goto 语句的东西，但我不知道该放在哪里。

有什么建议吗？

Answer 1

我以前实现过一次数独解算器。它比您拥有的要复杂一些，但眨眼间就解决了游戏。 :)

您正在尝试做的是通过 "Brute Force" 并使用（尾）递归来解决数独问题。这意味着您正在尝试通过遍历所有 9⁸¹ 可能的组合来解决棋盘问题。 9 的 81 次方是……这是一个很大的数字。因此，您的方法将花费永恒，但您将运行从尾递归中 space 出栈。

当我实现数独时，它更直接了。它保留了一个 "items" 的 9x9 数组，其中每个项目都是正方形中的值，以及一个代表候选人的 9 个布尔值数组（true == viable，false == eliminated）。然后它只是做了一个非递归循环来解决这个问题。

主循环将从寻找仅剩 1 个候选方格的简单过程开始。然后下一步将根据已经分配的值进行简单的候选消除。然后它将进入更复杂的消除技术，例如 X-Wing.

Answer 2

最终 validNumber() 方法不会 return 任何数字，因为没有任何可能性，这意味着之前的选择之一是不正确的。试想算法是从空格子开始的（显然这个谜题是可以解的¹）。

解决方案是保留可能的选择树，如果某些选择不正确，则只需将它们从树中删除并使用下一个可用的选择（或者退回到树的更高级别，如果没有选择留在这个分支）。如果有的话，这个方法应该找到解决方案。（实际上这就是我前段时间实现我的数独解算器的方式。）

¹ 恕我直言，有 3 种不同的数独：

"true"正确的数独有一个唯一的完整解决方案；
具有多个不同完整解决方案的模棱两可的数独，例如一个只有 7 个不同数字的谜题，因此它至少有两个不同的解决方案，通过交换第 8 个和第 9 个数字来区分；
没有完整解法的错误数独，例如同一行出现两次或多次相同的数字。

根据这个定义，求解器算法应该：

证明无解；
return满足初始网格的完整解

在 "true" 数独的情况下，根据定义，结果是 "true" 解。在模棱两可的数独的情况下，结果可能因算法而异。空网格是模棱两可的数独游戏的终极例子。

Answer 3

你的算法实际上并没有回溯。如果可以，它会向前移动，但当它意识到自己被困在角落时，它永远不会向后移动。这是因为它从不 returns 堆栈中的任何知识，也从不重置方块。除非你真的很幸运，否则你的代码会让游戏板进入角落状态，然后打印出那个角落状态。要回溯，您需要将您设置的最后一个方块（让您走投无路的那个）重置为零，这样您的算法就会知道继续尝试其他事情。

为了理解回溯，我强烈推荐 Steven Skiena 的一本名为《算法设计手册》的书。我在准备 SWE 面试时读了它，它确实提高了我对回溯、复杂性和图搜索的知识。本书后半部分是75道classic算法题的目录，数独就是其中之一！他对您可以进行的优化进行了有趣的分析，以修剪搜索树并解决非常困难的拼图板。下面是我很久以前读完本章后写的一些代码（按照我目前的标准可能不是那么高质量，但它可以工作）。我很快地通读了它并在 solve 方法中添加了 solveSmart 布尔值，它允许您打开或关闭这些优化之一，这在解决 "hard" class 数独板（一开始只有 17 个方格填满）。

public class Sudoku {

  static class RowCol {
    int row;
    int col;

    RowCol(int r, int c) {
      row = r;
      col = c;
    }
  }

  static int numSquaresFilled;
  static int[][] board = new int[9][9];

  static void printBoard() {
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        System.out.print(" " + (board[i][j] == 0 ? " " : board[i][j]) + " ");
        if (j % 3 == 2 && j < 8)
          System.out.print("|");
      }
      System.out.println();
      if (i % 3 == 2 && i < 8)
        System.out.println("---------|---------|---------");
    }
    System.out.println();
  }

  static boolean isEntireBoardValid() {
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        if (!isBoardValid(i, j)) {
          return false;
        }
      }
    }
    return true;
  }

  static boolean isRowValid(int row) {
    int[] count = new int[9];
    for (int col = 0; col < 9; col++) {
      int n = board[row][col] - 1;
      if (n == -1)
        continue;
      count[n]++;
      if (count[n] > 1)
        return false;
    }
    return true;
  }

  static boolean isColValid(int col) {
    int[] count = new int[9];
    for (int row = 0; row < 9; row++) {
      int n = board[row][col] - 1;
      if (n == -1)
        continue;
      count[n]++;
      if (count[n] > 1)
        return false;
    }
    return true;
  }

  static boolean isSquareValid(int row, int col) {
    int r = (row / 3) * 3;
    int c = (col / 3) * 3;
    int[] count = new int[9];
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        int n = board[r + i][c + j] - 1;
        if (n == -1)
          continue;
        count[n]++;
        if (count[n] > 1)
          return false;
      }
    }
    return true;
  }

  static boolean isBoardValid(int row, int col) {
    return (isRowValid(row) && isColValid(col) && isSquareValid(row, col));
  }

  static RowCol getOpenSpaceFirstFound() {
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        if (board[i][j] == 0) {
          return new RowCol(i, j);
        }
      }
    }
    return new RowCol(0, 0);
  }

  static RowCol getOpenSpaceMostConstrained() {
    int r = 0, c = 0, max = 0;
    int[] rowCounts = new int[9];
    int[] colCounts = new int[9];
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        if (board[i][j] != 0)
          rowCounts[i]++;
        if (board[j][i] != 0)
          colCounts[i]++;
      }
    }

    int[][] squareCounts = new int[3][3];
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        int count = 0;
        for (int m = 0; m < 3; m++) {
          for (int n = 0; n < 3; n++) {
            if (board[(i * 3) + m][(j * 3) + n] != 0)
              count++;
          }
        }
        squareCounts[i][j] = count;
      }
    }

    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        if (board[i][j] == 0) {
          if (rowCounts[i] > max) {
            max = rowCounts[i];
            r = i;
            c = j;
          }
          if (colCounts[j] > max) {
            max = rowCounts[j];
            r = i;
            c = j;
          }
        }
      }
    }
    return new RowCol(r, c);
  }

  static boolean solve() {
    if (81 == numSquaresFilled) {
      return true;
    }

    boolean solveSmart = true;
    RowCol rc = solveSmart ? getOpenSpaceMostConstrained() : getOpenSpaceFirstFound();
    int r = rc.row;
    int c = rc.col;
    for (int i = 1; i <= 9; i++) {
      numSquaresFilled++;
      board[r][c] = i;
      if (isBoardValid(r, c)) {
        if (solve()) {
          return true;
        }
      }
      board[r][c] = 0;
      numSquaresFilled--;
    }
    return false;
  }

  public static void main(String[] args) {

    // initialize board to a HARD puzzle
    board[0][7] = 1;
    board[0][8] = 2;
    board[1][4] = 3;
    board[1][5] = 5;
    board[2][3] = 6;
    board[2][7] = 7;
    board[3][0] = 7;
    board[3][6] = 3;
    board[4][3] = 4;
    board[4][6] = 8;
    board[5][0] = 1;
    board[6][3] = 1;
    board[6][4] = 2;
    board[7][1] = 8;
    board[7][7] = 4;
    board[8][1] = 5;
    board[8][6] = 6;
    numSquaresFilled = 17;

    printBoard();
    long start = System.currentTimeMillis();
    solve();
    long end = System.currentTimeMillis();
    System.out.println("Solving took " + (end - start) + "ms.\n");
    printBoard();
  }
}

通过回溯解决数独 (java)

Solve sudoku by backtracking (java)

java

recursion

backtracking