通过回溯解决数独（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）放在该字段中，方法进入下一个字段。

在这个算法中，该方法现在不会生成一个有效的数字是否最终会使难题无法解决。

我想改变它像这样：

在结束时，当该方法结束通过整个2D阵列迭代，如果是零或不阵列的每个条目被测试。

如果甚至有一个零，则整个算法必须到达第一个“有效”号码所在的位置。现在，下一个“有效”号码被放入，直到没有零点算法的结尾。

我有一些麻烦实施这个想法。在我看来，在某个地方必须有另一个for循环，或者类似goto声明，但我不知道该把它放在哪里。

有什么建议吗？

Answer 1

我之前实现了一个Sudoku解算器。这比你想象的要复杂一点，但是瞬间解决了比赛。 :)

你试图做的是通过“蛮力”和使用（尾）递归解决Sudoku。这意味着您正试图通过遍历所有可能的组合来遍历所有的电路板。 9到81的威力是......好吧，这是一个很大的数字。所以你的方法将会永恒，但你很快就会从尾递归中耗尽堆栈空间。

当我实施Sudoko时，它更加直线上升。它保留了一个9x9的“项目”数组，其中每个项目都是正方形中的值，并且包含9个代表候选项的布尔值数组（true ==可行，false ==消除）。然后它只是做了一个解决电路板的非递归循环。

主循环将从只有1个剩余候选人找到正方形的简单过程开始。然后下一步将根据已分配的值进行简单候选消除。然后它将以更复杂的消除技术的方式工作，如X-Wing。

Answer 2

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

解决方案是保留树的可能选择，如果某些选择不正确，那么只需从树中删除它们并使用下一个可用选项（或退回到树的更高级别，如果没有选择留在这个分支）。这种方法应该找到解决方案（其实这是我前段时间如何实施我的数独求解器。）

---

IMHO有3种不同种类的数独的：

1. “真” 正确的，具有单一的独特完整的解决方案独;

2. 含有多个不同完整解决方案（例如，一个只有7个不同数字的难题，所以它至少有两个不同的解决方案，通过交换第8和第9个数字而不同。

3. 不正确的数独，没有完整的解决方案，例如一行有两个或更多的相同数字。

利用这个定义，求解器算法应该：

1. 证明不存在溶液;

2. 返回满足初始网格的完整解决方案。

在“true”数独的情况下，结果是根据定义的“真实”解决方案。在模糊数独的情况下，结果可以根据算法而不同。空网格是模糊数独的最终例子。

Answer 3

你的算法实际上并没有回溯。如果可以的话，它会向前移动，但当它意识到它卡在一个角落时，它不会向后移动。这是因为它永远不会向堆栈返回任何知识，并且它不会重置方块。除非你真的很幸运，否则你的代码会让游戏板进入角色状态，然后打印出角色状态。为了回溯，您需要重置您设置的最后一个方块（使您被限制的方块）为零，以便您的算法知道继续尝试其他方法。

为了理解回溯，我强烈推荐一本名为Steven Skiena的算法设计手册。当我准备参加SWE时，我读了它，它真的提高了我对回溯，复杂性和图表搜索的知识。本书的后半部分是75个经典算法问题的目录，而数独就是其中之一！他有一个有趣的分析，你可以优化你的修剪搜索树并解决非常困难的拼图板。下面是我在阅读本章后很久以前写的一些代码（可能不是我现有标准的高质量，但它有效）。我只是快速阅读它，并在solve方法中添加了solveSmart布尔值，该方法允许您打开或关闭这些优化中的一个，这样在解决“难”类Sudoku板时会节省相当多的时间（仅包含一个首先填入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(); 
    } 
}