0036. Valid Sudoku ================== 题目信息 -------- :题号: 0036. 有效的数独 :难度: Medium :主题: 矩阵、集合、位掩码 :原题: `LeetCode 0036 `_ :重点: 从逐格重复检查同行同列同宫,推导到一次遍历同时维护三类数字集合 题目重述 -------- 给定一个 ``9 x 9`` 的数独棋盘 ``board``,判断当前已经填写的数字是否满足以下三类约束: #. 每一行中,数字 ``1`` 到 ``9`` 不能重复; #. 每一列中,数字 ``1`` 到 ``9`` 不能重复; #. 每个 ``3 x 3`` 九宫格中,数字 ``1`` 到 ``9`` 不能重复。 字符 ``'.'`` 表示空格,不参与重复检查。题目只判断当前局面是否违反约束,不要求证明棋盘能够继续填成一个完整 数独。因此,一个尚未填满但没有重复数字的棋盘仍然有效。 棋盘固定为 ``9 x 9``,其中每个字符只可能是 ``'.'`` 或 ``'1'`` 到 ``'9'``。 自建示例 -------- 以下坐标使用零基下标,未列出的格子都为 ``'.'``: * 同一行重复:``board[0][1] = '5'``、``board[0][7] = '5'``,返回 ``false``; * 同一列重复:``board[1][3] = '7'``、``board[8][3] = '7'``,返回 ``false``; * 同一宫重复:``board[0][0] = '4'``、``board[2][2] = '4'``,返回 ``false``; * 数字同时位于不同的行、列和宫:``board[0][0] = '6'``、``board[4][4] = '6'``,返回 ``true``; * 全空棋盘:所有格子均为 ``'.'``,返回 ``true``。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: bool conflictsWithPeers( const std::vector>& board, int row, int col ) { const char digit = board[row][col]; for (int index = 0; index < 9; ++index) { if (index != col && board[row][index] == digit) { return true; } if (index != row && board[index][col] == digit) { return true; } } const int boxRow = row / 3 * 3; const int boxCol = col / 3 * 3; for (int offset = 0; offset < 9; ++offset) { const int peerRow = boxRow + offset / 3; const int peerCol = boxCol + offset % 3; if ((peerRow != row || peerCol != col) && board[peerRow][peerCol] == digit) { return true; } } return false; } bool checkEveryCell(const std::vector>& board) { for (int row = 0; row < 9; ++row) { for (int col = 0; col < 9; ++col) { if (board[row][col] != '.' && conflictsWithPeers(board, row, col)) { return false; } } } return true; } bool booleanTables(const std::vector>& board) { std::array, 9> rows{}; std::array, 9> columns{}; std::array, 9> boxes{}; for (int row = 0; row < 9; ++row) { for (int col = 0; col < 9; ++col) { const char cell = board[row][col]; if (cell == '.') { continue; } const int digit = cell - '1'; const int box = row / 3 * 3 + col / 3; if (rows[row][digit] || columns[col][digit] || boxes[box][digit]) { return false; } rows[row][digit] = true; columns[col][digit] = true; boxes[box][digit] = true; } } return true; } bool bitMasks(const std::vector>& board) { std::array rows{}; std::array columns{}; std::array boxes{}; for (int row = 0; row < 9; ++row) { for (int col = 0; col < 9; ++col) { const char cell = board[row][col]; if (cell == '.') { continue; } const int bit = 1 << (cell - '1'); const int box = row / 3 * 3 + col / 3; if ((rows[row] & bit) != 0 || (columns[col] & bit) != 0 || (boxes[box] & bit) != 0) { return false; } rows[row] |= bit; columns[col] |= bit; boxes[box] |= bit; } } return true; } public: bool isValidSudoku(std::vector>& board) { return bitMasks(board); } }; 题解 ---- 逐格验证 ~~~~~~~~ 最直接的方法是访问每个已填格子 ``(row, col)``,再扫描它所在的整行、整列和 ``3 x 3`` 宫,确认没有另一个 相同数字。``checkEveryCell`` 完全按照题目定义工作,只要某个数字在任一所属区域中出现第二次,棋盘就无效。 这种方法的问题是重复读取。同一行中的多个已填格子会反复扫描整行,同一列和同一宫也存在相同浪费。验证一个新 格子真正需要的信息不是全部同伴格子,而是三个所属区域已经出现过哪些数字。 区域数字集合 ~~~~~~~~~~~~ 每个已填格子唯一属于一行、一列和一个九宫格。扫描到数字 ``digit`` 时,只需查询三个集合: * ``rows[row]``:当前行已经出现的数字; * ``columns[col]``:当前列已经出现的数字; * ``boxes[box]``:当前九宫格已经出现的数字。 数字若已存在于任一集合,就与此前格子发生冲突;三处都未出现时,同时登记到三个集合。这样每个格子只读取一次, 后续格子直接复用已登记的区域状态。 ``booleanTables`` 为每个区域保存九个布尔值。数字字符 ``cell`` 转为下标 ``cell - '1'``,使数字 ``1`` 到 ``9`` 分别映射到下标 ``0`` 到 ``8``。 九宫格映射 ~~~~~~~~~~ 整数除法 ``row / 3`` 得到宫格所在的大行,``col / 3`` 得到宫格所在的大列,二者都位于 ``0`` 到 ``2``。按行 展开后的九宫格编号为: .. math:: box=(row/3)\times3+col/3 因此左上宫映射为 ``0``,右下宫映射为 ``8``。同一 ``3 x 3`` 宫中的九个坐标会得到同一个 ``box``,可以共用 同一份数字集合。 单次扫描不变量 ~~~~~~~~~~~~~~ 处理任意格子前,三张表准确记录所有已扫描格子在各行、各列和各宫中出现过的数字。当前格子为空时跳过,不改变 状态;当前格子为数字时,先查询三个所属集合。 若某处已经登记该数字,当前格子就是该区域中的第二次出现,可以立即返回 ``false``。若三处都未登记,同时写入 三张表后,不变量继续成立。 任意违规都表现为同一数字在某个区域中至少出现两次。第一次出现会被登记,第二次出现一定触发冲突。扫描结束仍未 发现冲突,则每一行、每一列和每一宫中的已填数字都互不重复,正好满足题目对当前棋盘有效性的定义。算法不尝试 填写空格,也不会把尚未完成的合法局面误判为无效。 位掩码压缩 ~~~~~~~~~~ 每个区域只需表示九种数字是否出现,可以用一个整数的低九位代替九个布尔值。数字 ``cell`` 对应: .. code-block:: text bit = 1 << (cell - '1') ``mask & bit`` 非零表示该数字已经出现,``mask |= bit`` 表示登记数字。``bitMasks`` 与布尔表保存完全相同的集合 状态,只是把九个布尔值压缩为一个整数。 例如先处理 ``board[0][0] = '4'`` 时,数字 ``4`` 对应位 ``1 << 3``,该位被写入 ``rows[0]``、 ``columns[0]`` 和 ``boxes[0]``。随后处理 ``board[2][2] = '4'`` 时,行表与列表没有冲突,但两格同属 ``boxes[0]``,对应位已经存在,因此立即判定九宫格重复。 代码演进 ~~~~~~~~ ``checkEveryCell`` 每遇到一个数字都重新读取其全部同伴格子。``booleanTables`` 把重复读取压缩成三张区域数字表, 使每个已填格只查询和登记一次。 ``bitMasks`` 保留相同的一次遍历结构,再把每组九个布尔值压缩为一个整数掩码。公开入口采用位掩码方法;布尔表 更直观,位掩码则是同一状态的紧凑实现。 复杂度分析 ~~~~~~~~~~ 棋盘固定为 ``9 x 9``,三种方法的时间和空间在题目范围内都可视为 ``O(1)``,但实际工作量不同。 若把棋盘边长推广为 ``n``,逐格方法对 ``n^2`` 个格子分别扫描行、列和宫,时间为 ``O(n^3)``;一次登记方法只 遍历棋盘,时间为 ``O(n^2)``。布尔表保存各行、列和宫的数字集合,需要 ``O(n^2)`` 个布尔状态;在固定九阶数独 中,位掩码只使用 27 个整数,因此为常量额外空间。