Sudoku求解器的代碼解釋

Question

我對以下代碼片斷有疑問： 這是一個數獨求解器，它通過填充空單元格來解決數獨難題。 我無法真正理解求解器方法背後的邏輯。爲什麼在嘗試k = 1-9後返回false，並且在遍歷所有單元格之後返回true。我認爲我們是遞歸地進入solver（）方法，並且一旦數獨完成，它將作爲調用順序返回真，最後第一個被調用的求解器（）將返回true。我認爲我必須省略一些高於兩個「回報」的場景。有人能向我解釋爲什麼這些「迴歸」存在？

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

每次遞歸調用都要照顧第一個'。'還有待處理。這將暫時用一個數字代替。如果更改成功（不會使板失效），請執行遞歸操作（將嘗試下一個'。'）。如果這將無法撤消在本地完成的更改並返回false，因爲在此搜索分支上嘗試的任何數字都是無效的。這意味着強制呼叫者（直到根）嘗試下一個選擇。

Answer 2

這是一個簡單的蠻力解算器。它只是在每個開放空間嘗試每個數字。如果棋盤在填充給定空格後用一個數字「有效」（遵循遊戲規則），則遞歸調用同一個求解器函數，填充另一個空白點並測試棋盤是否仍然有效上。

這是一個非常低效的解算器，但易於編碼。

Answer 3

此代碼檢查Sudoku。如果它是正確的，那麼check_sudoku（）方法返回true，如果它錯誤，則顯示具有重複元素的行號和列號。

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

}