数独バックトラックソルバー（Java）

Question

私は3日間、数独バックトラッキングソルバーで私の間違いを把握しようとしています。問題はleetcode Sudoku Solverです。

私のソルバーは添付画像のdeductionに基づいています。問題は、ルートからリーフへのパスが無効であっても、私のボードが変更されることです。

つまり、無効なパスを通過した後、試行した値は元のボードに固定されます。しかし、私は元のボードが子どもが真を返すときにのみ更新します（ヘルパーメソッドの部分を参照してください：//数値を入れて子供を生成する）。

基本的に、各 '。'に対して、1から9までのすべての可能性を生成し、現在の '。'を塗りつぶす一時ボードを構築します。 1つの可能性を持って、次のヘルパーに電話してください。臨時ボード付き。スペースコストのために、それぞれの子供のために同じサイズのboardTempを保存するのは良いことではありませんが、私の主な関心事は、まずコストを最適化する前に問題を解決することです。

すべての子供が正当でない場合でも私のボードはなぜ変わるのですか？例えば

、最初のボード

..9748のベース...。 7........; .2.1.9 ...;

.. 7 ... 24。 ; 64.1.59。 .98 ... 3 ..;

... 8.3.2。 ........ 6; ... 2759 ..;

私が実行した後、私は最終的な結果を得た：

139748652。 745326189; 826159437;; 64.1.59。 .98 ... 3 ..;

... 8.3.2。 ........ 6; ... 2759 ..;

public void sudokuSolver(char[][] board) { 
    for (int i = 0 ; i < board.length ; i++) { 
     for (int j = 0 ; j < board.length ; j++) { 
      if (board[i][j] == '.') { 
       // find the first '.' as root 
       helper(i, j, board); 
       return; 
      } 
     } 
    } 
} 

private boolean helper(int row, int col, char[][] board) { 
    // case 2. check if it has following '.' and store its position 
    boolean hasNext = false; 
    boolean nextSearching = false; 
    int nextRow = row; 
    int nextCol = col; 
    for (int i = 0 ; i < board.length ; i++) { 
     for (int j = 0; j < board.length ; j++) { 
      if (nextSearching && !hasNext && board[i][j] == '.') { 
       hasNext = true; // there is next! 
       nextRow = i; 
       nextCol = j; 
      } 
      if (i == row && j == col) { 
       nextSearching = true; 
      } 
     } 
    } 

    // exit condition: last '.' 
    if (!hasNext) { 
     for (char put = '1' ; put <= '9' ; put ++) { 
      if (isValid(row, col, board, put)) { 
       return true; 
      } 
     } 
     return false; 
    } 

    // put a number and generate children 
    for (char put = '1' ; put <= '9' ; put ++) { 
     if (isValid(row, col, board, put)) { 
      char[][] boardTemp = board; 
      boardTemp[row][col] = put; 
      boolean valid = helper(nextRow, nextCol, boardTemp); 
      if (valid) { 
       // board is supposed to change only when valid is true. 
       board[row][col] = put; 
       return true; 
      } 
     } 
    } 
    return false; 
} 

private boolean isValid(int row, int col, char[][] board, char c) { 
    // go through each row, column, and subblock to determine if c is a valid choice based on current board. 
    for (int jCol = 0 ; jCol < 9 ; jCol ++) { 
     if (board[row][jCol] == c) { 
      return false; 
     } 
    } 
    for (int iRow = 0 ; iRow < 9 ; iRow ++) { 
     if (board[iRow][col] == c) { 
      return false; 
     } 
    } 
    for (int i = row/3*3 ; i < row/3*3 + 3 ; i++) { 
     for (int j = col/3*3 ; j < col/3*3 + 3 ; j++) { 
      if (board[i][j] == c) { 
       return false; 
      } 
     } 
    } 
    return true; 
} 

Answer 1

boardTempとboardを使用しての間に違いはありません。

for (char put = '1' ; put <= '9' ; put ++) { 
    if (isValid(row, col, board, put)) { 
     char[][] boardTemp = board; // board and boardTemp are essentially the same thing 
     boardTemp[row][col] = put; 
     boolean valid = helper(nextRow, nextCol, boardTemp); 
     if (valid) { 
      // board is supposed to change only when valid is true. 
      board[row][col] = put; 
      return true; 
     } 
     // THIS IS WHAT YOU MISSED!! 
     // if you don't reset the '.' back, your later backtrack will not work 
     // because you put an invalid number on your board and you will never find a solution 
     boardTemp[row][col] = '.'; 
    } 
}