0%

leetcode每日一题-解数独

Posted on In ,

解数独

image1

image2

方法一：回溯

用布尔数组记录横坐标，纵坐标，小方格内出现过的数字，同时记录需要填充的格子的位置和个数。当全部填充完后就返回，否则就继续搜索。这里需要注意设置一个valid变量记录是否需要继续填充格子，如果不设置这个变量的话，循环会出现一种情况即已经填充完毕但因为没有退出循环而继续填充导致错误。

1
class Solution {
2
    
3
    boolean[][] row = new boolean[9][9];
4
    boolean[][] col = new boolean[9][9];
5
    boolean[][][] card = new boolean[3][3][9];
6
    List<int[]> spaces = new ArrayList<>();
7
    boolean valid = false;
8
    public void solveSudoku(char[][] board) {
9
        for(int i=0; i<9; i++){
10
            for(int j=0; j<9; j++){
11
                if(board[i][j] != '.') {
12
                    int num = board[i][j] - '1';
13
                    row[i][num] = true;
14
                    col[j][num] = true;
15
                    card[i / 3][j / 3][num] = true;
16
                }else{
17
                    spaces.add(new int[]{i,j});
18
                }
19
            }
20
        }
21
        dfs(board, 0);
22
    }
23
24
    public void dfs(char[][] board, int pos){
25
        if(pos == spaces.size()){
26
            valid = true;
27
            return;
28
        }
29
        int[] space = spaces.get(pos);
30
        int x = space[0];
31
        int y = space[1];
32
        for(int i=0; i<9 && !valid; i++){
33
            if(!row[x][i] && !col[y][i] && !card[x/3][y/3][i]){
34
                board[x][y] = (char)('1'+i);
35
                row[x][i] = true;
36
                col[y][i] = true;
37
                card[x/3][y/3][i] = true;
38
                dfs(board, pos+1);
39
                // 回溯
40
                row[x][i] = false;
41
                col[y][i] = false;
42
                card[x/3][y/3][i] = false;
43
            }
44
        }
45
    }
46
}

方法二：状态压缩

使用位运算进行优化，在方法一中，我们使用了长度为 99 的数组表示每个数字是否出现过。我们同样也可以借助位运算，仅使用一个整数表示每个数字是否出现过。

具体地，数 $b$ 的二进制表示的第 $i$ 位（从低到高，最低位为第 $0$ 位）为 $1$，当且仅当数字 $i+1$ 已经出现过。例如当 $b$ 的二进制表示为$ (011000100)_2$时，就表示数字 $3$，$7$，$8$ 已经出现过。

位运算有一些基础的使用技巧。下面列举了所有在代码中使用到的技巧：

  • 对于第 $i$ 行第 $j$ 列的位置，$\textit{line}[i] | \textit{column}[j] | \textit{block}[\lfloor i/3 \rfloor][\lfloor j/3 \rfloor]$ 中第 $k$ 位为 $1$，表示该位置不能填入数字 $k+1$（因为已经出现过），其中 $|$ 表示按位或运算。如果我们对这个值进行 $\sim$ 按位取反运算，那么第 $k$ 位为 $1$ 就表示该位置可以填入数字 $k+1$，我们就可以通过寻找 $1$ 来进行枚举。由于在进行按位取反运算后，这个数的高位也全部变成了 $1$，而这是我们不应当枚举到的，因此我们需要将这个数和$ (111111111)2 = (\text{1FF}){16}$进行按位与运算 $&$，将所有无关的位置为 $0$；

  • 我们可以使用按位异或运算 $\wedge$，将第 $i$ 位从 $0$ 变为 $1$，或从 $1$ 变为 $0$。具体地，与数 $1 << i$ 进行按位异或运算即可，其中 $<<$ 表示左移运算；回溯时候用到

  • 我们可以用 $b & (-b)$ 得到$ b$ 二进制表示中最低位的 $1$，这是因为 $(-b)$ 在计算机中以补码的形式存储，它等于$ \sim b + 1$。$b$ 如果和$ \sim b$ 进行按位与运算，那么会得到 $0$，但是当 $\sim b$加$ 1$ 之后，最低位的连续的 $1 $都变为 $0$，而最低位的 $0$ 变为 $1$，对应到 $b$ 中即为最低位的 $1$，因此当 $b$ 和 $\sim b + 1$ 进行按位与运算时，只有最低位的 $1$ 会被保留；

  • 当我们得到这个最低位的 $1$ 时，我们可以通过一些语言自带的函数得到这个最低位的 $1$ 究竟是第几位（即 $i$ 值），具体可以参考下面的代码；

    Integer.bitCount((x & (x-1))-1)

  • 我们可以用 $b$ 和最低位的 $1$ 进行按位异或运算，就可以将其从 $b$ 中去除，这样就可以枚举下一个 $1$。同样地，我们也可以用 $b$ 和 $b-1$ 进行按位与运算达到相同的效果。

1
class Solution {
2
    int[] row = new int[9];
3
    int[] col = new int[9];
4
    int[][] card = new int[3][3];
5
    List<int[]> spaces = new ArrayList<>();
6
    boolean valid = false;
7
    public void solveSudoku(char[][] board) {
8
        for(int i=0; i<9; i++){
9
            for(int j=0; j<9; j++){
10
                if(board[i][j] != '.') {
11
                    int num = board[i][j] - '1';
12
                    flip(i, j, num);
13
                }else{
14
                    spaces.add(new int[]{i,j});
15
                }
16
            }
17
        }
18
        dfs(board, 0);
19
    }
20
21
    public void dfs(char[][] board, int pos){
22
        if(pos == spaces.size()){
23
            valid = true;
24
            return;
25
        }
26
        int[] space = spaces.get(pos);
27
        int i = space[0];
28
        int j = space[1];
29
        int mask = ~(row[i] | col[j] | card[i/3][j/3]) & 0x1ff;
30
        for(; mask!=0 && !valid; mask &= (mask-1)){
31
            int digitmask = mask & (-mask);
32
            int digit = Integer.bitCount(digitmask-1);
33
            //System.out.println("i:"+i+" j:"+j+" digit:"+digit);
34
            flip(i, j, digit);
35
            board[i][j] = (char)(digit + '1');
36
            dfs(board, pos+1);
37
            flip(i, j, digit);
38
        } 
39
    }
40
41
    public void flip(int i, int j, int digit){
42
        row[i] ^= (1<<digit);
43
        col[j] ^= (1<<digit);
44
        card[i/3][j/3] ^= (1<<digit);
45
    }
46
}