题目

请你判断一个 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）或者 '.'

具体思路

这道题的核心是判断一个已经部分填写的 9x9 数独棋盘是否“有效”。有效性判断基于三条规则：

每一行中的数字 1-9 不能重复出现。
每一列中的数字 1-9 不能重复出现。
每一个 3x3 的小宫格内的数字 1-9 不能重复出现。

重要的是，我们只需要检查已经填入了数字的格子，空白格（用 . 表示）可以忽略。

解决这个问题的最直观和高效的方法是一次遍历整个棋盘。在遍历每个单元格的时候，我们同时检查它是否满足上述的三个规则。

为了能够高效地检查一个数字是否已经在某一行、某一列或某一个 3x3 宫格中出现过，我们需要使用能够快速进行查找的数据结构。哈希表 是理想的选择，因为它支持近乎 $O(1)$ 复杂度的添加和查找操作。

我们可以创建三个哈希表（或数组/列表的哈希表）来分别记录每一行、每一列和每一个 3x3 宫格已经出现过的数字。

详细步骤：

初始化数据结构：
- 行记录：创建一个包含 9 个哈希表的列表（或数组），rows = [set(), set(), ..., set()]。rows[i] 用来存储第 i 行已经出现过的数字。
- 列记录：同样创建一个包含 9 个哈希表的列表，cols = [set(), set(), ..., set()]。cols[j] 用来存储第 j 列已经出现过的数字。
- 3x3 宫格记录：创建一个包含 9 个哈希表的列表，boxes = [set(), set(), ..., set()]。boxes[k] 用来存储第 k 个 3x3 宫格已经出现过的数字。
遍历棋盘：
- 使用嵌套循环遍历整个 9x9 棋盘，从 board[0][0] 到 board[8][8]。假设当前遍历到的单元格坐标为 (r, c)，其中 r 是行索引，c 是列索引。
检查与记录：
- 对于每个单元格 board[r][c]：
  - 跳过空格：如果该单元格是 .，则直接跳过，继续检查下一个单元格。
  - 获取数字：如果不是空格，获取该单元格的数字 num。
  - 检查行：检查 num 是否已经存在于 rows[r] 中。如果存在，说明同一行内有重复数字，数独无效，可以直接返回 false。
  - 检查列：检查 num 是否已经存在于 cols[c] 中。如果存在，说明同一列内有重复数字，数独无效，返回 false。
  - 检查 3x3 宫格：
    - 首先，需要确定当前单元格 (r, c) 属于哪一个 3x3 宫格。我们可以用一个简单的数学公式来计算宫格的索引 box_index： box_index = (r // 3) * 3 + (c // 3)
      - r // 3 确定了它在哪一个大行（0, 1, or 2）。
      - c // 3 确定了它在哪一个大列（0, 1, or 2）。
      - 这个公式将 9 个 3x3 宫格从左到右、从上到下映射到索引 0 到 8。
    - 然后，检查 num 是否已经存在于 boxes[box_index] 中。如果存在，说明同一个 3x3 宫格内有重复数字，数独无效，返回 false。
  - 添加记录：如果上述三个检查都通过了，说明到目前为止该数字是有效的。我们需要将这个数字 num 添加到对应的记录中，以备后续检查：
    - rows[r].add(num)
    - cols[c].add(num)
    - boxes[box_index].add(num)
返回结果：
- 如果整个棋盘都遍历完了，都没有触发任何返回 false 的条件，那就说明所有已填写的数字都满足规则。此时，函数最后返回 true。

具体代码

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // 使用三个二维数组来记录每一行、每一列和每一个 3x3 宫格中数字的出现情况
        // rows[i][num] 表示数字 num+1 是否在第 i 行出现过
        // cols[j][num] 表示数字 num+1 是否在第 j 列出现过
        // boxes[k][num] 表示数字 num+1 是否在第 k 个 3x3 宫格出现过
        array<array<bool, 9>, 9> rows = {{{{false}}}};
        array<array<bool, 9>, 9> cols = {{{{false}}}};
        array<array<bool, 9>, 9> boxes = {{{{false}}}};
        // 遍历整个 9x9 棋盘
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                // 如果当前单元格是空白格，则跳过
                if (board[r][c] == '.') {
                    continue;
                }
                // 将字符数字转换为整数索引 (例如 '1' -> 0, '9' -> 8)
                int num = board[r][c] - '1';
                // 计算当前单元格所属的 3x3 宫格的索引 (0-8)
                int box_index = (r / 3) * 3 + (c / 3);
                // 检查该数字是否已在当前行、当前列或当前 3x3 宫格中出现过
                if (rows[r][num] || cols[c][num] || boxes[box_index][num]) {
                    // 如果任意一个条件为真，说明存在重复，数独无效
                    return false;
                }
                // 如果没有重复，将该数字记录下来
                rows[r][num] = true;
                cols[c][num] = true;
                boxes[box_index][num] = true;
            }
        }
        // 如果成功遍历完所有单元格都没有发现冲突，则数独有效
        return true;
    }
};

36. 有效的数独

beautifulremi

题目

具体思路

详细步骤：

具体代码