LeetCode-37 - 解数独_leetcode数独解题-CSDN博客

题目

<困难> 解数独

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

数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 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"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

在这里插入图片描述

提示：

$b o a r d . l e n g t h = = 9$
$b o a r d [i] . l e n g t h = = 9$
$b o a r d [i] [j] 是一位数字（ 1 - 9 ）或者^{'} .^{'}$
$题目数据保证输入数独仅有一个解$

接下来看一下解题思路：

填充数字的时候需要满足以下三个条件：

同一个数字在每一行只能出现一次；
同一个数字在每一列只能出现一次；
同一个数字在每一个小九宫格只能出现一次。

通过递归 + 回溯的方法枚举所有可能的填法。当递归到最后一个空白格后，如果仍然没有冲突，说明我们找到了答案；在递归的过程中，如果当前的空白格不能填下任何一个数字，那么就进行回溯。

由于每个数字在同一行、同一列、同一个九宫格中只会出现一次，因此我们可以使用 $\textit{rows}[i]$ ， $\textit{cols}[j]$ ， $\textit{subs}[x][y]$ 分别表示第 $i$ 行，第 $j$ 列，第 $(x, y)$ 个九宫格中填写数字的情况。

思路一：递归：

在存储时，我们使用一个长度为 $9$ 的布尔类型的数组，其中 $i$ 个元素的值为 $\text{True}$ ，当且仅当数字 $i + 1$ 出现过。例如我们用 $\textit{rows}[2][3] = \text{True}$ 表示数字 $4$ 在第 $2$ 行已经出现过，那么当我们在遍历到第 $2$ 行的空白格时，就不能填入数字 $4$ 。

具体做法是，首先对整个数独数组进行遍历，当遍历到第 $i$ 行第 $j$ 列的位置：

如果该位置是一个空白格，将其加入列表，方便后续递归操作；
如果该位置是一个数字 $x$ ，那么需要将 $\textit{rows}[i][x-1]$ ， $\textit{cols}[j][x-1]$ 以及 $\textit{subs}[\lfloor i/3 \rfloor][\lfloor j/3 \rfloor][x-1]$ 均置为 $\text{True}$ 。

当填入数字 $x$ 之后，需要将上述的三个值都设置为 $t r u e$ ，并且对下一个空白格位置进行递归。
在回溯到当前递归层时，还要讲上述的三个值重新设置为 $f a l s e$ 。这就需要一个变量用于记录，如果数独表都填写完成，找到合适的数字，就不需要回溯了，以防回溯将正确的值覆盖。

java实现

class Solution {
    // 记录每一行存在的数字 
    boolean[][] rows = new boolean[9][9];
    // 记录每一列存在的数字
    boolean[][] cols = new boolean[9][9];
    // 记录每一个 3*3宫存在的数字 
    boolean[][][] subs = new boolean[3][3][9];
    // 这个list用来记录所有空格的位置，整数数组第一个位置为行的位置 ，第二个位置为列的位置
    List<int[]> space = new ArrayList<>();
    // 判断是否填完所有空格
    boolean vaild = false;

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[i].length; ++j) {
                char c = board[i][j];
                // 如果位置为空，把该位置加入space中
                if (c == '.') {
                   space.add(new int[]{i, j});
                } else {
                    int index = c - '0' - 1;
                    rows[i][index] = cols[index][j] = subs[i/3][j/3][index] = true;
                }
            }
        }
        dfs(board, 0);
    }

    void dfs(char[][] board, int pos) {
        //如果 space 被遍历完了，说明填完了空格，将valid改为true，通过return结束这个函数
        if (pos == space.size()) {
            vaild = true;
            return;
        }
		// 获取第一个空格的位置 
        int[] value = space.get(pos);
        int i = value[0];
        int j = value[1];
        for (int index = 0; index < 9 && !vaild; ++index) {
            if (!rows[i][index] && !cols[index][j] && !subs[i/3][j/3][index]) {
                board[i][j] = (char) (index + '0' + 1);
                rows[i][index] = cols[index][j] = subs[i/3][j/3][index] = true;
                // 递归，考虑下一空节点
                dfs(board, pos + 1);
                // 回退之后，复原
                rows[i][index] = cols[index][j] = subs[i/3][j/3][index] = false;
            }
        }
    }
}

思路二：状态压缩 + 位运算：

用数组来保存每个值出现的位置，需要创建三个数组，分别保存行、列和 $3 * 3$ 的小矩阵，需要一定的空间开销。
其实，可以进一步优化，通过位运算，用每一位来记录对应位置值，如果是1说明访问过，如果是0说明没访问过
具体地，数 $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$ 二进制表示中最低位的 $1$ ，这是因为 $(- b)$ 在计算机中以补码的形式存储，它等于 $\sim b + 1$ 。 $b$ 如果和 $\sim b$ 进行按位与运算，那么会得到 $0$ ，但是当 $\sim b$ 增加 $1$ 之后，最低位的连续的 $1$ 都变为 $0$ ，而最低位的 $0$ 变为 $1$ ，对应到 $b$ 中即为最低位的 $1$ ，因此当 $b$ 和 $\sim b + 1$ 进行按位与运算时，只有最低位的 $1$ 会被保留；
当得到这个最低位的 $1$ 时，可以通过一些语言自带的函数 java 中是 Integer.bitcount() 得到这个最低位的 $1$ 究竟是第几位（即 $i$ 值），具体可以参考下面的代码；
可以用 $b$ 和最低位的 $1$ 进行按位异或运算，就可以将其从 $b$ 中去除，这样就可以枚举下一个 $1$ 。同样地，我们也可以用 $b$ 和 $b - 1$ 进行按位与运算达到相同的效果。

实际上，方法二中整体的递归 + 回溯的框架与方法一是一致的。不同的仅仅是将一个数组「压缩」成了一个数而已。

java实现

class Solution {
    // 储存每一行存在的数字
    int[] rows = new int[9];
    // 储存 每一列存在的数字
    int[] cols = new int[9];
    // 储存每一个 3*3宫存在的数字
    int[][] subs = new int[3][3];
    // 这个list用来记录所有空格的位置，整数数组第一个位置为行的位置 ，第二个位置为列的位置
    List<int[]> space = new ArrayList<>();
    // 这个布尔数组用来判断是否填完所有空格
    boolean vaild = false;

    public void solveSudoku(char[][] board) {
    	// 遍历所有位置
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[i].length; ++j) {
                char c = board[i][j];
                // 如果位置为空，我们把该位置加入spaces中
                if (c == '.') {
                   space.add(new int[]{i, j});
                } else {
                	// 不为空则把该数字分别纳入对应的行，列，3*3宫中
                    int digital = c - '0' - 1;
                    flip(i, j, digital);
                }
            }
        }
        dfs(board, 0);
    }

    void dfs(char[][] board, int pos) {
        // 如果 spaces 被遍历完了，说明我们填完了空格，将 valid 改为 true，通过 return 结束这个函数
        if(pos == space.size()){
            vaild = true;
            return;
        }

		// 获取第一个空格的位置
        int[] value = space.get(pos);
        int i = value[0];
        int j = value[1];
        // |为or，通过3个或运算我们可以得到一个9位的二进制数字，
        // 从右到左分别代表1-9这个9个数是否可以填入该空格，通过~运算（取反），
        // 我们用1表示该数字是一个可填入的选项，0x1ff为十六进制 ，等同于111111111）
        int mask = ~(rows[i] | cols[j] | subs[i/3][j/3]) & 0x1FF;
        // 当mask不为0并且 valid为false表示还有数待填入，继续这个循环，mask &= (mask - 1)把最低位的1变为0
        for(; mask != 0 && !vaild; mask &= (mask - 1)) {
            // 这个操作只保留最低位的1
            int digitMask = mask & (-mask); 
            // 最低位的1后面的位数，digitMask-1将原本1后面的0全部变为了1
            int digit = Integer.bitCount(digitMask - 1);
            // 更新行，列，宫
            flip(i, j, digit);
            // 把该数填入板中
            board[i][j] = (char)(digit + '0' + 1);
            dfs(board, pos + 1);
            // 撤回操作（原理是flip中的 ~ 运算，两个 1 则为0,0表示这个位置代表的 1-9 中的那个数 不再是一个可被填入的选项）
            flip(i, j, digit);
        }
    }

    void flip(int i, int j, int digital) {
        // ^ 代表异或，只有1个1的时候才为1。比如0011^1001=1010
        // << 代表左移，比如 1<<2=4 被加入到下面的三个数组中，在二进制4为100，意味着3这个数字被占用了
        // 统计出现的数字，出现 i 对应的 i - 1 位为 1
        rows[i] ^= (1 << digital);
        cols[j] ^= (1 << digital);
        subs[i/3][j/3] ^= (1 << digital);
    }
}

思路三：枚举优化

可以顺着方法二的思路继续优化下去：

如果一个空白格只有唯一的数可以填入，也就是其对应的 $b$ 值和 $b - 1$ 进行按位与运算后得到 $0$ （即 $b$ 中只有一个二进制位为 $1$ ）。此时，就可以确定这个空白格填入的数，而不用等到递归时再去处理它。
这样一来，可以不断地对整个数独进行遍历，将可以唯一确定的空白格全部填入对应的数。随后再使用与方法二相同的方法对剩余无法唯一确定的空白格进行递归 + 回溯。

class Solution {
    int[] rows = new int[9];
    int[] cols = new int[9];
    int[][] subs = new int[3][3];
    List<int[]> space = new ArrayList<>();
    boolean vaild = false;

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[i].length; ++j) {
                char c = board[i][j];
                if (c != '.') {
                    int digital = c - '0' - 1;
                    flip(i, j, digital);
                }
            }
        }

        while(true) {
            boolean modify = false;
            for(int i = 0; i < 9; ++i) {
                for(int j = 0; j < 9; ++j){
                    if(board[i][j] == '.') {
                        int mask = ~(rows[i] | cols[j] | subs[i/3][j/3]) & 0x1FF;
                        if((mask & (mask - 2)) == 0){
                            int digit = Integer.bitCount(mask - 1);
                            flip(i, j, digit);
                            board[i][j] = (char)(digit + '0' + 1);
                            modify = true;
                        }
                    }
                }
            } 
            if(!modify) {
                break;
            }
        }

        for(int i = 0; i < 9; ++i) {
            for(int j = 0; j < 9; ++j) {
                if(board[i][j] == '.') {
                    space.add(new int[]{i, j});
                }
            }
        }

        dfs(board, 0);
    }

    void dfs(char[][] board, int pos) {
        if(pos == space.size()){
            vaild = true;
            return;
        }

        int[] value = space.get(pos);
        int i = value[0];
        int j = value[1];
        int mask = ~(rows[i] | cols[j] | subs[i/3][j/3]) & 0x1FF;
        for(; mask != 0 && !vaild; mask &= (mask - 1)) {
            int digitMask = mask & (-mask); 
            int digit = Integer.bitCount(digitMask - 1);
            flip(i, j, digit);
            board[i][j] = (char)(digit + '0' + 1);
            dfs(board, pos + 1);
            flip(i, j, digit);
        }
    }

    void flip(int i, int j, int digital) {
        rows[i] ^= (1 << digital);
        cols[j] ^= (1 << digital);
        subs[i/3][j/3] ^= (1 << digital);
    }
}