通過回溯解決數獨（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(); 
    } 
}