LeetCode-37. 解数独

问题地址

LeetCode每日一题/2020-09-15

LeetCode37. 解数独

问题描述

规则

• 编写一个程序，通过已填充的空格来解决数独问题。
• 一个数独的解法需遵循如下规则：
  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。
  • 空白格用 ‘.’ 表示。

示例

• 示例
  
• 数独答案（答案被标成红色）
  

提示

• 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9×9 形式的。

解析

解题思路

数据操作分析

编码实现

官方解法

前言

我们可以考虑按照「行优先」的顺序依次枚举每一个空白格中填的数字，通过递归 + 回溯的方法枚举所有可能的填法。当递归到最后一个空白格后，如果仍然没有冲突，说明我们找到了答案；在递归的过程中，如果当前的空白格不能填下任何一个数字，那么就进行回溯。
由于每个数字在同一行、同一列、同一个九宫格中只会出现一次，因此我们可以使用 \textit{line}[i]，\textit{column}[j]，\textit{block}[x][y] 分别表示第 i 行，第 j 列，第 (x, y) 个九宫格中填写数字的情况。在下面给出的三种方法中，我们将会介绍两种不同的表示填写数字情况的方法。
九宫格的范围为 0 \leq x \leq 2 以及 0 \leq y \leq 2。
具体地，第 i 行第 j 列的格子位于第 (\lfloor i/3 \rfloor, \lfloor j/3 \rfloor) 个九宫格中，其中 \lfloor u \r 表示对 u 向下取整。
由于这些方法均以递归 + 回溯为基础，算法运行的时间（以及时间复杂度）很大程度取决于给定的输入数据，而我们很难找到一个非常精确的渐进紧界。因此这里只给出一个较为宽松的渐进复杂度上界 O(9^{9 \times 9})，即最多有 9 \times 9 个空白格，每个格子可以填 [1, 9] 中的任意整数。

方法一：递归

思路：

• 最容易想到的方法是用一个数组记录每个数字是否出现。由于我们可以填写的数字范围为 [1, 9]，而数组的下标从 0 开始，因此在存储时，我们使用一个长度为 9 的布尔类型的数组，其中 i 个元素的值为 \text{True}，当且仅当数字 i+1 出现过。例如我们用 \textit{line}[2][3] = \text{True} 表示数字 4 在第 2 行已经出现过，那么当我们在遍历到第 2 行的空白格时，就不能填入数字 4。

算法：

• 我们首先对整个数独数组进行遍历，当我们遍历到第 i 行第 j 列的位置：
  • 如果该位置是一个空白格，那么我们将其加入一个用来存储空白格位置的列表中，方便后续的递归操作；
  • 如果该位置是一个数字 x，那么我们需要将 \textit{line}[i][x-1]，\textit{column}[j][x-1] 以及 \textit{block}[\lfloor i/3 \rfloor][\lfloor j/3 \rfloor][x-1] 均置为 \text{True}。
• 当我们结束了遍历过程之后，就可以开始递归枚举。当递归到第 i 行第 j 列的位置时，我们枚举填入的数字 x。根据题目的要求，数字 x 不能和当前行、列、九宫格中已经填入的数字相同，因此 \textit{line}[i][x-1]，\textit{column}[j][x-1] 以及 \textit{block}[\lfloor i/3 \rfloor][\lfloor j/3 \rfloor][x-1] 必须均为 \text{False}。
• 当我们填入了数字 x 之后，我们要将上述的三个值都置为 \text{True}，并且继续对下一个空白格位置进行递归。在回溯到当前递归层时，我们还要将上述的三个值重新置为 \text{False}。

复杂度分析

编码实现

class Solution {
    private boolean[][] line = new boolean[9][9];
    private boolean[][] column = new boolean[9][9];
    private boolean[][][] block = new boolean[3][3][9];
    private boolean valid = false;
    private List<int[]> spaces = new ArrayList<int[]>();

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.add(new int[]{i, j});
                } else {
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }

        dfs(board, 0);
    }

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

        int[] space = spaces.get(pos);
        int i = space[0], j = space[1];
        for (int digit = 0; digit < 9 && !valid; ++digit) {
            if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                board[i][j] = (char) (digit + '0' + 1);
                dfs(board, pos + 1);
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
            }
        }
    }
}

方法二：位运算优化

思路：

• 在方法一中，我们使用了长度为 9 的数组表示每个数字是否出现过。我们同样也可以借助位运算，仅使用一个整数表示每个数字是否出现过。
• 具体地，数 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 << i1<<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 值），具体可以参考下面的代码；
  • 我们可以用 b 和最低位的 1 进行按位异或运算，就可以将其从 b 中去除，这样就可以枚举下一个 1。同样地，我们也可以用 b 和 b-1 进行按位与运算达到相同的效果，读者可以自行尝试推导。
• 实际上，方法二中整体的递归 + 回溯的框架与方法一是一致的。不同的仅仅是我们将一个数组「压缩」成了一个数而已。

复杂度分析

编码实现

class Solution {
    private int[] line = new int[9];
    private int[] column = new int[9];
    private int[][] block = new int[3][3];
    private boolean valid = false;
    private List spaces = new ArrayList();

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.add(new int[]{i, j});
                } else {
                    int digit = board[i][j] - '0' - 1;
                    flip(i, j, digit);
                }
            }
        }

        dfs(board, 0);
    }

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

        int[] space = spaces.get(pos);
        int i = space[0], j = space[1];
        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
        for (; mask != 0 && !valid; 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);
        }
    }

    public void flip(int i, int j, int digit) {
        line[i] ^= (1 << digit);
        column[j] ^= (1 << digit);
        block[i / 3][j / 3] ^= (1 << digit);
    }
}

方法三：枚举优化

思路：

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

复杂度分析

编码实现

class Solution {
    private int[] line = new int[9];
    private int[] column = new int[9];
    private int[][] block = new int[3][3];
    private boolean valid = false;
    private List spaces = new ArrayList();

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

        while (true) {
            boolean modified = false;
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') {
                        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
                        if ((mask & (mask - 1)) == 0) {
                            int digit = Integer.bitCount(mask - 1);
                            flip(i, j, digit);
                            board[i][j] = (char) (digit + '0' + 1);
                            modified = true;
                        }
                    }
                }
            }
            if (!modified) {
                break;
            }
        }

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

        dfs(board, 0);
    }

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

        int[] space = spaces.get(pos);
        int i = space[0], j = space[1];
        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
        for (; mask != 0 && !valid; 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);
        }
    }

    public void flip(int i, int j, int digit) {
        line[i] ^= (1 << digit);
        column[j] ^= (1 << digit);
        block[i / 3][j / 3] ^= (1 << digit);
    }
}

精彩评论

跳转地址1：「手画图解」解数独 | 回溯算法 Sudoku Solver

思路

• 每一个空白格都要选一个数字去填，有多少个空白格，就要做多少次选择。我们可以想到递归，递归函数每次填当前的格子，选填 i，board 的状态就更新了。
• 子递归呢？基于填了 i 的新 board，给下一个格子填数。每个递归的子问题，面对一个新 board。
• 按顺序填下去，如果不是空白格，就继续递归填下一个。
• 直到递归到最后一个格子，board 填满了，结束递归。
  

为什么要回溯

• 每填一个空白格都是尝试，选一个数字，如果没有冲突，就填上去，是一种试探。
• 但如果发现，在填下一个格子时，怎么填都有问题：填 1 到 9 都会冲突。
• 意味着，基于当前 board 的状态，这个格子填不了，做不下去了，此路不通。
• 所以，要回到上一格，撤销它的选择，改填别的数，再试探、探索。

递归函数的准确定义

• 子递归是填下一个格子，下一个格子填不了，要告知当前递归，撤销当前的选择。
  • 即，根据子递归的结果，判断当前递归的选择是否正确，或者说，当前的 board 状态是否正确。
  • 所以，递归函数要返回一个Boolean值，定义是：基于当前的 board，给当前的格子board[i][j]填一个数，能否最后生成正确的数独。
• 能否最后生成正确的数独，是要递归的子调用协助的，一个个去填，当发现填不下去，就撤回上一个选择，尝试别的选择。

算法优化

• 其实可以用三个数组：
  • $rows$ 数组，长度为 9，对应每一行，都有一个 hashSet，hashSet 存放可填的数字。
  • $cols$ 数组，长度为 9，对应每一列，都有一个 hashSet，hashSet 存放可填的数字。
  • $blocks$ 数组，长度为 9，对应 9 个框，都有一个 hashSet，hashSet 存放可填的数字。
• 如果当前格子，选填的数，在对应的三个 hashSet 里，有一个里面没有它，那就不能选。
• 这样就避免每次去遍历判断，用空间换取时间。
  

跳转地址2：回溯法解数独

思路

• 类似人的思考方式去尝试，行，列，还有 3*3 的方格内数字是 1~9 不能重复。
• 我们尝试填充，如果发现重复了，那么擦除重新进行新一轮的尝试，直到把整个数组填充完成。

算法步骤：

• 数独首先行，列，还有 3*3 的方格内数字是 1~9 不能重复。
• 声明布尔数组，表明行列中某个数字是否被使用了， 被用过视为 true，没用过为 false。
• 初始化布尔数组，表明哪些数字已经被使用过了。
• 尝试去填充数组，只要行，列， 还有 3*3 的方格内 出现已经被使用过的数字，我们就不填充，否则尝试填充。
• 如果填充失败，那么我们需要回溯。将原来尝试填充的地方改回来。
• 递归直到数独被填充完成。

编码实现

class Solution {
    public void solveSudoku(char[][] board) {
        // 三个布尔数组 表明 行, 列, 还有 3*3 的方格的数字是否被使用过
        boolean[][] rowUsed = new boolean[9][10];
        boolean[][] colUsed = new boolean[9][10];
        boolean[][][] boxUsed = new boolean[3][3][10];
        // 初始化
        for(int row = 0; row < board.length; row++){
            for(int col = 0; col < board[0].length; col++) {
                int num = board[row][col] - '0';
                if(1 <= num && num <= 9){
                    rowUsed[row][num] = true;
                    colUsed[col][num] = true;
                    boxUsed[row/3][col/3][num] = true;
                }
            }
        }
        // 递归尝试填充数组 
        recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0);
    }

    private boolean recusiveSolveSudoku(char[][]board, boolean[][]rowUsed, boolean[][]colUsed, boolean[][][]boxUsed, int row, int col){
        // 边界校验, 如果已经填充完成, 返回true, 表示一切结束
        if(col == board[0].length){
            col = 0;
            row++;
            if(row == board.length){
                return true;
            }
        }
        // 是空则尝试填充, 否则跳过继续尝试填充下一个位置
        if(board[row][col] == '.') {
            // 尝试填充1~9
            for(int num = 1; num  {
    // 判断是否有行列和框框的冲突
    const hasConflit = (r, c, val) => {
        for (let i = 0; i < 9; i++) {
            if (board[i][c] == val || board[r][i] == val) { // 行或列里有冲突
                return true;
            }
        }
        // 对于小框，行、列有三种起始索引 0、3、6
        const subRowStart = Math.floor(r / 3) * 3;
        const subColStart = Math.floor(c / 3) * 3;
        // 遍历所在的小框
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j  {
        // 列越界，填完一行，填下一行
        if (j == 9) {
            i++;
            j = 0;
            // 都填完了，返回true
            if (i == 9) return true; 
        }
        if (board[i][j] != ".") return fill(i, j + 1); // 不是空白格，递归填下一格

        for (let num = 1; num  {
    const rows = new Array(9);
    const cols = new Array(9);
    const blocks = new Array(9);
    const options = ['1', '2', '3', '4', '5', '6', '7', '8', '9']; 
    for (let i = 0; i  {
        return (i / 3 | 0) * 3 + j / 3 | 0;
    };
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j  {
        if (j == 9) {
            i++;
            j = 0;
            if (i == 9) return true;
        }
        if (board[i][j] != ".") return fill(i, j + 1);
        const blockIndex = getBlockIndex(i, j);
        for (let num = 1; num <= 9; num++) {
            const s = String(num);
            if (!rows[i].has(s) || !cols[j].has(s) || !blocks[blockIndex].has(s)) continue;
            board[i][j] = s;
            rows[i].delete(s);
            cols[j].delete(s);
            blocks[blockIndex].delete(s);
            if (fill(i, j + 1)) return true;
            board[i][j] = ".";
            rows[i].add(s);
            cols[j].add(s);
            blocks[blockIndex].add(s);
        }
        return false;
    };
    fill(0, 0);
    return board;
};