$$\color{Red}{解数独【leetcode37 dfs格点分组】}$$

下面的链接是——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

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

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

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] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

解析

这道题，其实理解了如何给不同格点分组就差不多 结束了，本质就是简单的爆搜。

给一个小方格的点分成一组，其实本质就是找每组小方格的公共特点，随便拿第一个小方格，和第二排第二个小方格来看。

1. 横坐标 [0 -> 2] 纵坐标 [0 -> 2]
2. 横坐标 [3 -> 5] 纵坐标 [3 -> 5]

可以找到同组内的关系 =》 box[x / 3][y / 3] 相等。

剩下的部分就是 dfs 了。

class Solution {

    public static boolean dfs(int x, int y, char [][] board, boolean [][] row, boolean [][] col, boolean[][][] box) {
        if (y == 9) {
            y = 0;
            x ++;
        }
        if (x == 9) return true;

        if (board[x][y] != '.') return dfs(x, y + 1, board, row, col, box);
        for (int k = 0; k < 9; k ++) {
            if (!row[x][k] && !col[y][k] && !box[x / 3][y / 3][k]) {
                row[x][k] = col[y][k] = box[x / 3][y / 3][k] = true;
                board[x][y] = (char) (k + '1');
                if (dfs(x, y + 1, board, row, col, box)) return true;
                row[x][k] = col[y][k] = box[x / 3][y / 3][k] = false;
                board[x][y] = '.';
            }
        }

        return false;
    }

    public void solveSudoku(char[][] board) {
        boolean row[][] = new boolean [9][9];
        boolean col[][] = new boolean [9][9];
        boolean box[][][] = new boolean [3][3][9];
        for (int i = 0; i < 9; i ++) 
            for (int j = 0; j < 9; j ++) {
                if (board[i][j] != '.') {
                    int t = board[i][j] - '1';
                    row[i][t] = true;
                    col[j][t] = true;
                    box[i / 3][j / 3][t] = true;
                }
            }

        dfs(0, 0, board, row, col, box);
    }
}