Mã giải thích về Sudoku Solver

Question

Tôi có câu hỏi về đoạn mã sau: Đó là trình giải Sudoku giải quyết câu đố Sudoku bằng cách điền vào các ô trống. Tôi thực sự không thể có được logic đằng sau phương pháp giải quyết. Tại sao nó trả về false sau khi thử k = 1-9 và trả về true sau khi lặp qua tất cả các ô. Những gì tôi nghĩ là chúng ta đệ quy vào phương thức solver() và một khi sudoku được thực hiện, nó sẽ trả về true theo thứ tự gọi và cuối cùng là trình giải mã được gọi đầu tiên() sẽ trả về true. Tôi nghĩ rằng tôi phải bỏ qua một số kịch bản mà trên hai "trở lại" xảy ra. Ai đó có thể giải thích cho tôi tại sao những "trở lại" đó tồn tại?

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

Mỗi cuộc gọi đệ quy đều quan tâm đến '.' Đầu tiên vẫn được xử lý. Điều đó sẽ được thay thế bằng một chữ số. Nếu thay đổi thành công (không làm mất hiệu lực hội đồng quản trị) thì hãy chuyển tiếp (sẽ thử tiếp theo '.'). Nếu điều đó sẽ không hoàn tác thay đổi được thực hiện cục bộ và trả về false, vì bất kỳ chữ số nào được thử trên nhánh tìm kiếm này đều không hợp lệ. Điều này có nghĩa là để buộc người gọi (lên đến root) để thử sự lựa chọn tiếp theo.

Answer 2

Đây là bộ giải mã lực mạnh mẽ đơn giản. Nó chỉ cố gắng mọi số trong mọi không gian mở. Nếu hội đồng quản trị là 'hợp lệ' (tuân thủ các quy tắc của trò chơi) sau khi điền vào một không gian nhất định với một số, sau đó nó đệ quy gọi cùng một hàm giải quyết điền vào một chỗ trống khác và kiểm tra xem bảng đó có còn hợp lệ không trên.

Đó là trình giải mã không hiệu quả cao, nhưng dễ mã.

Answer 3

Mã này Kiểm tra Sudoku.Nếu đúng thì phương thức check_sudoku() trả về true nếu sai rồi hiển thị số hàng và cột có phần tử trùng lặp.

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; 
} 

}