Zatrzymany w Solvoku soltrackowanie solver (Java)

Question

Próbowałem rozgryźć mój błąd w solvtrackowaniu Sudoku przez trzy dni. Problem jest z leetcode Sudoku Solver.

Mój solver jest oparty na odliczeniu na załączonym zdjęciu. Problem polega na tym, że moja tablica jest zmieniana, nawet jeśli ścieżka od korzenia do liścia jest nieprawidłowa.

Innymi słowy, po przejściu przez nieprawidłową ścieżkę, wartości, które próbowano, są ustalane na mojej oryginalnej planszy. Jednakże aktualizuję tylko oryginalną tablicę, gdy jej dzieci zwracają wartość true (zobacz część w metodzie pomocnika: // wstaw numer i wygeneruj dzieci).

Zasadniczo, dla każdego ".", Generuję wszystkie możliwości od 1 do 9, konstruuję płytę temp, która wypełnia bieżący "." z jedną możliwością, a następnie wywołaj pomocnika następnego "." z tablicą temp. Wiem, że nie jest dobre przechowywanie tego samego rozmiaru boardTemp dla każdego możliwego dziecka z powodu kosztów przestrzeni, ale moim głównym problemem jest teraz rozwiązanie problemu przed optymalizacją kosztów.

Podsumowując, dlaczego tablica zmienia się, nawet jeśli wszystkie dzieci są nieprawidłowe?

Na przykład, baza na początkowej planszy

..9748 ...; 7 ........; .2.1.9 ...;

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

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

mam ostateczny wynik po biegnę:

139748652; 745326189; 826159437;

35769.24 .; .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

Nie ma różnicy między używaniem boardTemp i board. char[][] boardTemp = board oznacza, że ​​wskazują na tej samej pamięci ... Czego brakowało w oryginalnym kodzie jest else udział w po umieścić numer nieprawidłowy:

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] = '.'; 
    } 
}