LeetCode 37、解数独（位运算法）

一、题目描述

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

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

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

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

示例 1：

img

输入：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、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的数独（LeetCode 36）（位运算法）：https://leetcode.cn/problems/sudoku-solver/
class Solution {
    
        // 数独的长宽大小
        final int N = 9;

        // 用数组记录每一行、每一列、每一个小九宫格的情况
        // 000000001 表示当前这一行中出现了数字 1 
        // 000000010 表示当前这一行中出现了数字 2
        // 000000011 表示当前这一行中出现了数字 1 和数字 2
        // 100000100 表示当前这一行中出现了数字 3 和数字 9

        // rows 里面的每个元素可以用一个二进制来表示当前这一行数字的出现情况
        private int[] rows = new int[N];

        // columns 里面的每个元素可以用一个二进制来表示当前这一列数字的出现情况
        private int[] columns = new int[N];

        // subboxes 里面的每个元素可以用一个二进制来表示当前这一小九宫格数字的出现情况
        private int[][] subboxes = new int[3][3];

        public void solveSudoku(char[][] board) {

            // 统计未填的个数
            int count = 0;

            // 通过两轮循环，获取 board 里面有多少个空白格需要填充
            for (int i = 0; i < N; i++) {

                for (int j = 0; j < N; j++) {

                    char ch = board[i][j];

                    // 如果当前位置为空白格，记录一下
                    if (ch == '.') {

                        count++;

                    // 如果当前位置为数字
                    } else {
                        // 那么这个位置所处的行、列、小九宫格都得更新一下数据
                        fillNumber(i, j, ch - '1', true);
                    }
                }
            }
            //上面是一些计算前的准备工作，从这里开始调用回溯算法
            backtrace(board, count);
        }

        private boolean backtrace(char[][] board, int count) {
            // 如果 board 里面的所有空格都填好了数字，没有多余的位置填充
            if ( count == 0 ) {
                // 递归终止
                return true;
            }

            // 开始寻找合适的位置进行分析
            // 即去寻找出某个位置可以选择数字比较少
            int[] pos = getMinOkMaskCountPos(board);

            // 获取到这个位置的坐标
            int x = pos[0], y = pos[1];
          
            // 再获取这个位置究竟有哪些数字可以进行选择
            // 比如坐标 ( 4 , 1 ) 有 3 、4 、 5 三个数字符合要求
            int mask = getMask(x, y);

            // 每个位置可以填充的数字都能从 1 到 9 进行选择 
            for (char c = '1'; c <= '9'; c++) {

                // 由于数组的索引是从 0 开始的，而小方格的值是从 1 开始的
                int index = c - '1';

                // 判断这个位置是否可以填字符数字 c
                // 比如 mask 为 101111100
                // 可以填充 1 、2 、8 ，那么就先尝试填 1 ，发现是可以的，再继续填充下一个
                if (testMask(mask, index)) {

                    // 坐标（ x , y ) 的位置的填充的值为 index 的数字
                    // 比如 mask 为 101111100
                    // 填入 1 之后
                    // mask 可以选择的数字就变成了 2 和 8 
                    // 即 mask 变成了 101111101
                    fillNumber(x, y, index, true);

                    // 把字符数字 c 填入到坐标（ x , y ) 的位置
                    board[x][y] = c;

                    // 开始考虑填充下一个位置
                    // 如果下一个位置和后续所有位置都填充成功
                    // 那么说明当前填充 c 这个数字是正确的
                    // 直接返回 true，不用再去考虑后续的情况了
                    if (backtrace(board, count - 1))
                        return true;

                    // 否则，还原现场
                    // 1、当前位置还原为空白格
                    board[x][y] = '.';

                    // 2、当前位置填充的数字抹去
                    fillNumber(x, y, index, false);
                }
            }
            return false;
        }

        // 在 board 上坐标为 ( x , y ) 的位置上填充数字 index
        // 填充完毕后，当前位置所处的行、列、小九宫格记录的数据情况都需要更新
        // fill 为 true 表示填充数字
        // fill 为 true 表示抹去数字，还原为空白格
        private void fillNumber(int x, int y, int index, boolean fill) {
            if (fill) {
                // 比如 index 为 2
                // mask 就是 000000100
                int mask = 1 << index;
                rows[x] = rows[x] | mask;
                columns[y] = columns[y] | mask;
                subboxes[x / 3][y / 3] = subboxes[x / 3][y / 3] | mask;
            } else {

                // 取反操作
                int mask = ~(1 << index);
                // 通过按位与把这一位更新为 0
                rows[x] = rows[x] & mask;
                columns[y] = columns[y] & mask;
                subboxes[x / 3][y / 3] = subboxes[x / 3][y / 3] & mask;
            }
        }

        // 当前位置处于第 x 行、第 y 列、第( x / 3 , y / 3 )个小九宫格
        // row[x] 获取第 x 行的数字出现情况，比如 100000100，表示这一行出现了 3 、 9 这两个数字
        // columns[y] 获取第 y 列的数字出现情况，比如 010000010，表示这一列出现了 2 、 8 这两个数字
        // subboxes[x / 3][y / 3] 获取第第( x / 3 , y / 3 )个小九宫格的数字出现情况
        // 这三者通过按位或的操作之后，可以获取到当前位置剩下那些数字可以填写
        //   111111100 ，剩下 1 和 2 两个数字可以填
        // | 111010100 ，剩下 1 、 2 、 4 、 6 四个数字可以填
        // | 001010110 ，剩下 1 、 4 、 6 、 8 、 9 五个数字可以填
        // = 111111110
        // 只有最后一个位置可以填
        private int getMask(int x, int y) {
            
            // 按位或操作
            return rows[x] | columns[y] | subboxes[x / 3][y / 3];

        }

        // 统计当前位置可以填充的数字个数有几个
        // 比如目前的信息分析出当前位置可以填充 2 、 3 这两个数字
        private int getCount(int mask) {
            int count = 0;
            for (int i = 0; i < N; i++) {
                // 只需要获取 mask 的二进制的 0 的个数就可以知道答案
                if ((mask & (1 << i)) == 0)
                    count++;
            }
            return count;
        }

        // 由于 mask 可以填充的数字可以有多个，需要从小到大的顺序去尝试
        // mask 为 101111100
        // 可以填充 1 、2 、8 ，那么就先尝试填 1
        private boolean testMask(int mask, int index) {
            return (mask & (1 << index)) == 0;
        }

        // 查看所有的空白格
        // 判断哪个位置的空白格内可填数字比较少
        // 那么就优先去填这个位置，所以返回这个位置的下标
        private int[] getMinOkMaskCountPos(char[][] board) {

            // 一维数组，包含了两个元素，分别表示坐标 x 和坐标 y
            int[] res = new int[2];

            // 默认每个位置可以选择的数字总数为 10 个（一个不可能达到的数字）
            // 然后通过不断比较的操作获取到最小值
            int min = 10;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 当前位置为空白格才去判断
                    if (board[i][j] == '.') {

                        // 1、通过对当前位置的行、列、小九宫格同时进行按位或的操作后
                        // 可以获取到当前这个位置有哪些数字可以填进去
                        // 比如最终结果是 111111100 ， 表示只有 1 、 2 这两个数字符合要求
                        int mask = getMask(i, j);

                        // 2、通过 mask 可以知道有几个数字符合要求
                        int count = getCount(mask);

                        // 3、不断的比较，从而知道哪个位置可以选择的数字最小
                        // 把它的坐标记录到 res 里面
                        if (count < min) {
                            min = count;
                            res[0] = i;
                            res[1] = j;
                        }
                    }
                }
            }

            // 返回最合适的那个坐标
            return res;
        }
}