[LeetCode] 37. 解数独（java实现）dfs_使用java的dfs方法求解九宫格

1. 题目

2. 读题（需要重点注意的东西）

思路（）：
第一反应是可以用类似于数字排列的dfs来实现，如果本题实现有困难，可以先完成[AcWing]842. 排列数字（C++实现）dfs模板题，递归思想的解释，再理解本题会容易很多。

原九宫格如下图所示，用 i 表示行、 j 表示列

将9个小的九宫格编号，因此它们可以表示为cell[i / 3][j / 3]

字符的 ‘1’ ~ ‘9’ 转变为数字的 0 ~ 8：'1' ~ '9' - '1'

3. 解法

---------------------------------------------------解法---------------------------------------------------：

class Solution {
    public boolean[][] row = new boolean[9][9];
    public boolean[][] col = new boolean[9][9];
    public boolean[][][] cell = new boolean[3][3][9];

    public void solveSudoku(char[][] board) {
        // 记录已经出现过的值,初始化row、col、cell
        for(int i = 0;i < 9; i++){
            for(int j = 0;j < 9; j++){
                if(board[i][j] != '.'){
                    int t = board[i][j] - '1'; // 将字符 1 ~ 9 转换为数字 0 ~ 8
                    row[i][t] = true; // 读作第i行的t已经出现过了
                    col[j][t] = true; // 读作第j列的t已经出现过了
                    cell[i/3][j/3][t] = true; // 第i/3 j/3的九宫格内t已经出现过了
                }
            }
        }
        dfs(board,0,0); // dfs一遍,从左上角（0,0）开始dfs
    }
    // x 行，y 列
    public boolean dfs(char[][] board,int x,int y){
        // 列走完了，行跳到下一行
        if(y == 9){
            x++;
            y = 0;
        }
        // 行和列都走完了，说明有解，返回true
        if(x == 9) return true;
        // 当前位置不为空，走下一个位置
        if(board[x][y] != '.') return dfs(board,x,y+1);
        // 当前位置为空，尝试填值 --- dfs
        for(int i = 0;i < 9;i++){
            if(row[x][i] == false && col[y][i] == false && cell[x/3][y/3][i] == false){
                board[x][y] = (char)(i + '1');
                row[x][i] = col[y][i] = cell[x/3][y/3][i] = true;
                if(dfs(board,x,y+1) == true) return true;
                // 恢复现场
                board[x][y] = '.';
                row[x][i] = col[y][i] = cell[x/3][y/3][i] = false;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

---

可能存在的问题：

4. 可能有帮助的前置习题

• [AcWing]842. 排列数字（C++实现）dfs模板题，递归思想的解释
• [LeetCode] 36. 有效的数独（java实现）模拟题

5. 所用到的数据结构与算法思想

• dfs
• 递归

6. 总结

1. 学会如何表达某个数在行、列、某一个九宫格内出现过的方法；
2. 学会如果恢复现场（回溯）