leetcode 第37题 解数独

leetcode 第37题 解数独

题目

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

一个数独。

答案被标成红色。

提示：

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

来源：力扣（LeetCode）
链接：

思路

        这个题乍看容易懵，因为数独如果没接触过，做起来会比较难。我之前做了第36题，有了前置知识，有一定的基础。

        前置知识是这样的：一个空格需要考虑其所在行、列和区域，不能有重复。我们可以在一次遍历，也就是O(n^2)的时间复杂度内得到当前每行、每列和每个区域的已有数字情况。

        接下来就是对空白格进行填充。这里其实也可以加一个前置知识，就是我们可以在一次遍历中获得所有的需要填充的空白格，之后只对这些空格进行处理。

        这里的思考就开始偏差了，我想着如果每个按照递归的方式去做，可能会导致复杂度极高，所以没在此处深入考虑递归，以后遇到这种问题，看起来极其适合递归的，还是用递归来做，解题速度其实是最快的。

        记录一下偏差后的思考内容，恰巧与官方解题中的一个优化方向一致，但优化应该是在解题之后进行，特此提醒自己。从题目中给出的例子中，可以看到右下角的方格是最容易计算出4的，因为这个位置只能填4。于是我就想到是不是可以先找到所有空格的可能解，然后那些可能解只有一个的，就直接填上，然后对同行、同列、同区域的其他空白格去掉这个可能取值。依次做下去，应该就会到达一种状态：所有的空白格的可能取值都是大于1的。

        基于优化，再次做递归，对剩下的空白格进行填充即可，整体的思路其实是没变的。

        还有一个优化点是，当我们记录每行、每列和每个区域的已有数字时，最直观的方法是用hashset，其实可以用一个int数字的低9位进行记录。但用int数字进行记录的时候，有很多的位操作，这个是真的漂亮，摘抄官方解法的说明如下：

• 对于第 i 行第 j列的位置，line[i] ∣ column[j] ∣ block[⌊i/3⌋][⌊j/3⌋] 中第 k 位为 1，表示该位置不能填入数字 k+1（因为已经出现过），其中 | 表示按位或运算。如果我们对这个值进行∼ 按位取反运算，那么第 k 位为 1 就表示该位置可以填入数字 k+1，我们就可以通过寻找 1 来进行枚举。由于在进行按位取反运算后，这个数的高位也全部变成了 1，而这是我们不应当枚举到的，因此我们需要将这个数和0x1ff 进行按位与运算 &，将所有无关的位置为 0；
• 我们可以使用按位异或运算 ∧，将第 i 位从 0 变为 1，或从 1 变为 0。具体地，与数 1<<i 进行按位异或运算即可，其中 << 表示左移运算；
• 我们可以用 b & (−b) 得到 b 二进制表示中最低位的 1，这是因为 (−b) 在计算机中以补码的形式存储，它等于 ∼b+1。bb 如果和 ∼b 进行按位与运算，那么会得到 0，但是当 ∼b 增加 1 之后，最低位的连续的 1 都变为 0，而最低位的 0 变为 1，对应到 b 中即为最低位的 1，因此当 b 和 ∼b+1 进行按位与运算时，只有最低位的 1 会被保留；
• 当我们得到这个最低位的 1 时，我们可以通过一些语言自带的函数得到这个最低位的 1 究竟是第几位（即 i 值），具体可以参考下面的代码；
• 我们可以用 b 和最低位的 1 进行按位异或运算，就可以将其从 b 中去除，这样就可以枚举下一个 1。同样地，我们也可以用 b 和 b−1 进行按位与运算达到相同的效果，读者可以自行尝试推导。

作者：LeetCode-Solution
链接：/

代码如下：

import java.util.*;class Solution {int[] rows = new int[9];int[] cols = new int[9];int[] regions = new int[9];boolean valid = false;List<Point> needCalPoints = new ArrayList<>();public void solveSudoku(char[][] board) {for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] == '.') {needCalPoints.add(new Point(i,j));continue;}int currentNum = board[i][j] - '0' - 1;int region = i / 3 * 3 + j / 3;rows[i] |= 1 << currentNum;cols[j] |= 1 << currentNum;regions[region] |= 1 << currentNum;}}dfs(board, 0);}// 递归方式对所有空白格进行尝试赋值public void dfs(char[][] board, int position) {if (position == needCalPoints.size()) {valid = true;return;}Point cal = (position);int row = w;int col = l;int region = row / 3 * 3 + col / 3;int mask = ~(rows[row] | cols[col] | regions[region]) & 0x1ff;for (; mask != 0 && !valid; mask &= (mask - 1)) {int digitMask = mask & (-mask);int digit = Integer.bitCount(digitMask - 1);flip(row, col, region, digit);board[row][col] = (char)(digit + 1 + '0');dfs(board, position + 1);flip(row, col, region, digit);}}// 对行、列、区域进行处理，记录上某位数字是否使用，或者将某位数字置为未用，通过异或运算进行public void flip(int i, int j, int region, int digit) {rows[i] ^= 1 << digit;cols[j] ^= 1 << digit;regions[region] ^= 1 << digit;}class Point {int row;int col;public Point(int row, int col) {w = l = col;}}
}

时间复杂度：遍历一次O(n^2)；递归最深是81层，每层的取值可能性都是9，所以填充空白格的时间复杂度是O(9^81)。

耗时：158min