leetcode_37.解数独

37. 解数独

题目描述：编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
输出：[
["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

backTrack 方法：

1. 这是一个递归方法，用于回溯填充数独。它使用两层嵌套循环来遍历数独的每个格子。
2. 如果当前格子为空（即 board[i][j] == '.'），则尝试填充数字 '1' 到 '9'。
3. 对于每个尝试填充的数字，首先调用 Judge 方法来判断当前数字是否符合数独的规则。
4. 如果当前数字符合数独的规则，则将其填充到当前格子，并递归调用 backTrack 方法填充下一个格子。
5. 如果递归调用返回 true，表示数独已经填充完成，则直接返回 true，结束递归。
6. 如果递归调用返回 false，表示当前填充的数字导致后续无法填充完成，则回溯到上一步，尝试下一个数字。
7. 如果所有数字都尝试过了仍然无法填充完成，则返回 false。

Judge 方法：

1. 这是一个辅助方法，用于判断当前填充的数字是否符合数独的规则。
2. 它通过检查当前行、当前列和当前小九宫格来确定当前数字是否与已有的数字冲突。
3. 如果存在冲突，则返回 false，否则返回 true。

class Solution {
  public void solveSudoku(char[][] board) {
        backTrack(board);
    }

    public boolean backTrack(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') continue;
                for (char k = '1'; k <= '9'; k++) {
                    if(!Judge(board, i, j, k))continue;
                    board[i][j] = k;
                    if (backTrack(board)) return true;
                    board[i][j] = '.';
                }
                return false;
            }
        }
        return true;
    }
    public boolean Judge(char[][] board, int x, int y, char k) {
        for (int i = 0; i < 9; i++) if (board[x][i] == k) return false;
        for (int i = 0; i < 9; i++) if (board[i][y] == k) return false;
        int nx = (x / 3) * 3;
        int ny = (y / 3) * 3;
        for (int i = nx; i < nx + 3; i++) {
            for (int j = ny; j < ny + 3; j++) {
                if (board[i][j] == k) return false;
            }
        }
        return true;
    }

}