当前位置：首页 > article >正文

【暴力搜索】有效的数独

article 2025/2/5 13:44:21

文章目录

36. 有效的数独
解题思路：暴力搜索 + 布尔值数组判断

36. 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 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"]]
输出：true

示例 2：

输入：board = 
[["8","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"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

解题思路：暴力搜索 + 布尔值数组判断

这道题其实就是得暴力搜索，遍历每个位置看看是否符合数独要求，但其实我们可以在判断要求的时候进行一点小优化（也不算是大优化，因为是用空间换时间），就是用布尔值类型的数组来表示某一行、某一列、某一九宫格是否已经出现过该数字，基于这个想法，我们可以给出以下三个数组：

bool row[9][10]：
- 这个数组表示在 0~8 行中，数字 1~9 是否出现过，出现过为 true，否则为 false。举个例子，row[3][7] 就表示第 3 行中是否出现过元素 7！
- 因为这道题给的整个区间就是 0~8 行，所以我们不需要考虑越界问题，并且因为要求的是 1~9 的数字，所以我们直接开辟 10 个元素的空间，这样子就可以用下标表示该数字了！
bool col[9][10]：
- 这个数组表示在 0~8 列中，数字 1~9 是否出现过，出现过为 true，否则为 false。
bool grid[3][3][10]：
- 这个就比较特殊了，首先我们把每个九宫格看作一个整体，以水平为例，因为一共有 9 个元素，那么我们让 3 个元素为一组，其中第一组作为大的下标 0，第二组作为大的下标 1，以此类推！
- 对于垂直方向也是如此，所以可以得到水平和垂直方向一共就是 0~3 组，如下图所示：
- 但是我们还需要表示这个九宫格中是否出现该元素，所以还需要第三维度来表示，所以这是一个三维数组，最后一维就是表示该元素是否出现过，所以范围就是 1~9，所以一共开辟 10 个空间！
- 并且我们这样子做有个好处，小坐标中的 0~2 为大坐标的 0，它可以直接 通过 0~2 除以 3 就能得到大坐标 0；而小坐标中的 3~5 为大坐标的 1，它可以直接通过 3~5 除以 3 就能得到大坐标 1，这是很妙的，后面以此类推！

有了上面三个数组，其实就类似哈希表，我们走到每个元素都能快速判断是否符合该要求，剩下的就是遍历整个区间，判断是否符合即可，不符合的话直接返回错误！

class Solution {
private:
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int x = 0; x < 9; ++x)
        {
            for(int y = 0; y < 9; ++y)
            {
                if(board[x][y] != '.')
                {
                    // 判断是否重复
                    int tmp = board[x][y] - '0';
                    if(row[x][tmp] == true || col[y][tmp] == true || grid[x/3][y/3][tmp] == true)
                        return false;
                    
                    // 记录当前元素已经走过
                    row[x][tmp] = col[y][tmp] = grid[x/3][y/3][tmp] = true;
                }
            }
        }
        return true;
    }
};