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

}