Objaśnienie kodu Sudoku Solver

Question

Mam pytanie dotyczące następującego fragmentu kodu: Jest to sudoku, który rozwiązuje sudoku, wypełniając puste komórki. Nie mogę naprawdę zrozumieć logiki metody solver. Dlaczego zwraca false po próbie k = 1-9 i zwraca true po zapętleniu wszystkich komórek. Myślałem, że rekursywnie wejdziemy w metodę solver(), a gdy zostanie ukończone sudoku, to zwróci true jako zlecenie wywołujące, a na koniec pierwsza wywoływana funkcja solver() zwróci wartość true. Myślę, że muszę pominąć pewne scenariusze, które mają miejsce powyżej dwóch "powrotów". Czy ktoś mógłby mi wytłumaczyć, dlaczego powinien istnieć "powrót"?

public class Solution { 

public static void main(String[] args) { 
    Solution s = new Solution(); 
    char[][] board = {{'.', '2', '6', '5', '.', '.', '.', '9', '.'}, 
         {'5', '.', '.', '.', '7', '9', '.', '.', '4'}, 
         {'3', '.', '.', '.', '1', '.', '.', '.', '.'}, 
         {'6', '.', '.', '.', '.', '.', '8', '.', '7'}, 
         {'.', '7', '5', '.', '2', '.', '.', '1', '.'}, 
         {'.', '1', '.', '.', '.', '.', '4', '.', '.'}, 
         {'.', '.', '.', '3', '.', '8', '9', '.', '2'}, 
         {'7', '.', '.', '.', '6', '.', '.', '4', '.'}, 
         {'.', '3', '.', '2', '.', '.', '1', '.', '.'}}; 

    s.solver(board); 
} 
public boolean solver(char[][] board) { 
    for (int r = 0; r < board.length; r++) { 
     for (int c = 0; c < board[0].length; c++) { 
      if (board[r][c] == '.') { 
       for (int k = 1; k <= 9; k++) { 
        board[r][c] = (char) ('0' + k); 
        if (isValid(board, r, c) && solver(board)) { 
         return true; 
        } else { 
         board[r][c] = '.'; 
        } 
       } 
       return false; 
      } 
     } 
    } 
    return true; 
} 

public boolean isValid(char[][] board, int r, int c) { 
    //check row 
    boolean[] row = new boolean[9]; 
    for (int i = 0; i < 9; i++) { 
     if (board[r][i] >= '1' && board[r][i] <= '9') { 
      if (row[board[r][i] - '1'] == false) { 
       row[board[r][i] - '1'] = true; 
      } else { 
       return false; 
      } 
     } 
    } 

    //check column 
    boolean[] col = new boolean[9]; 
    for (int i = 0; i < 9; i++) { 
     if (board[i][c] >= '1' && board[i][c] <= '9') { 
      if (col[board[i][c] - '1'] == false) { 
       col[board[i][c] - '1'] = true; 
      } else { 
       return false; 
      } 
     } 
    } 

    //check the 3*3 grid 
    boolean[] grid = new boolean[9]; 
    for (int i = (r/3) * 3; i < (r/3) * 3 + 3; i++) { 
     for (int j = (c/3) * 3; j < (c/3) * 3 + 3; j++) { 
      if (board[i][j] >= '1' && board[i][j] <= '9') { 
       if (grid[board[i][j] - '1'] == false) { 
        grid[board[i][j] - '1'] = true; 
       } else { 
        return false; 
       } 
      } 
     } 
    } 

    return true; 
} 
} 

Answer 1

Każda rozmowa rekurencyjna zajmie się pierwszym "." nadal do załatwienia. Zostanie to zastąpione próbnie cyfrą. Jeśli zmiana się powiedzie (nie powoduje unieważnienia tablicy), przejdź do rekurencji (spróbujesz dalej "."). Jeśli to się nie powiedzie, cofnij zmianę wykonaną lokalnie i zwróć wartość false, ponieważ każda cyfra wypróbowana w tej gałęzi wyszukiwania jest nieprawidłowa. Oznacza to zmuszenie dzwoniącego (do root'a) do wypróbowania następnego wyboru.

Answer 2

To prosty solver force. Po prostu próbuje każdej liczby w każdej otwartej przestrzeni. Jeśli plansza jest "ważna" (zgodnie z regułami gry) po wypełnieniu danej przestrzeni numerem, to rekursywnie wywołuje tę samą funkcję solver, która wypełnia kolejne puste miejsce i sprawdza, czy tablica jest nadal ważna, a więc na.

Jest to wysoce nieefektywny solver, ale łatwy do kodowania.

Answer 3

Ten kod Sprawdź Sudoku. Jeśli jest poprawny, to metoda check_sudoku() zwraca wartość true, jeśli jest nieprawidłowa, a następnie pokazuje numer wiersza i kolumny z duplikatem elementu.

public static void main(String[] args) { 
    int array[][]={{9,6,3,1,7,4,2,5,8}, 
        {1,7,8,3,2,5,6,4,9}, 
        {2,5,4,6,8,9,7,3,1}, 
        {8,2,1,4,3,7,5,9,6}, 
        {4,9,6,8,5,2,3,1,7}, 
        {7,3,5,9,6,1,8,2,4}, 
        {5,8,9,7,1,3,4,6,2}, 
        {3,1,7,2,4,6,9,8,5}, 
        {6,4,2,5,9,8,1,7,3}}; 

    Sudoku sudoku=new Sudoku(); 
    if(sudoku.check_sudoku(array)) 
    { 
     System.out.println("You won the game :)"); 
    } 


} 


public class Sudoku { 

private int temp1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, temp2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
private int data1, data2; 

public boolean check_sudoku(int array[][]) { 
    for (int i = 0; i < 9; i++) { 
     for (int j = 0; j < 9; j++) { 
      data1 = array[i][j]; 
      data2 = array[j][i]; 
      if (data1 >= 10 || data2 >=10 || data1 <= 0 || data2 <= 0) { 
       System.out.println("Invalid Solution because value must be in between 1 to 9"); 
       return false; 
      } else if (temp1[data1 - 1] == 0 || temp2[data2 - 1] == 0) { 
       System.out.println("Invalid Solution please check " + (i + 1) + " row " + (j + 1) + " column or " + (j + 1) + " row " + (i + 1) + " column"); 
       return false; 
      } else { 
       temp1[data1 - 1] = 0; 
       temp2[data2 - 1] = 0; 
      } 
     } 
     int check1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
     int check2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
     temp1 = check1; 
     temp2 = check2; 
    } 
    return true; 
} 

}