Valid Sudoku
你会得到一个 9 × 9 的数独棋盘 board，它是一个列表，包含 9 个字符串，每个字符串有 9 个字符，每行对应一个字符串。每个字符都是 1 到 9 的数字，或表示空单元格的 .。如果每一行、每一列或每个 3 × 3 方格中都没有重复的数字，则返回 true，否则返回 false。只检查已填入的单元格：棋盘不一定有解。
函数
- boardstring-array
- 9 个由 9 个字符组成的字符串，每行一个，使用数字 1 到 9，空单元格用 . 表示
- 返回值boolean
- 如果没有任何行、列或 3 × 3 宫格重复出现数字，则为真；否则为假
约束条件
board.length == 9并且board[i].length == 9board[i][j]是一个从1到9的数字，或.- 棋盘可能无法完成；只需关注已填单元格中的重复项。
示例
- 输入
- board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
- 输出
- true
- 解释
- 从 0 开始计数的第 4 行，
.74..89.3中的 7、4、8、9 和 3 各出现一次，其他 26 组也都没有重复数字。
- 输入
- board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
- 输出
- false
- 解释
- 第 0 行和第 7 行都以
3开头，所以第 0 列有两个 3。它们不在同一行或同一个宫格中，因此只有检查列才能发现这个问题。
- 输入
- board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
- 输出
- false
- 解释
- 第 0 行、第 8 列的
5和第 2 行、第 7 列的5不在同一行或同一列，但它们都位于右上方的宫格中，所以答案是false。
进阶
对于一个 16 × 16 的棋盘，其中有 4 × 4 的宫格，符号为 1 到 9 和 A 到 G，你会如何检查？宫格公式会变成什么？
提示
逐个打开提示，每个都会多透露一点。
列出规则中提到的组。共有多少组？哪种组最难建立索引？
位于第
r行、第c列的单元格恰好属于一个方框。使用整数除法，r / 3表示它位于哪一组连续的三行中，c / 3表示它位于哪一组连续的三列中。将这两个值合并为一个 0 到 8 之间的数字。每个单元格只访问一次。为每个（行，数字）、（列，数字）和（宫，数字）对保留一个已访问标记。如果某个已填充单元格在这三个分组中的任意一个分组里，对应的标记已经设置，那么它就是重复项。
题解
每个数字都属于三个组：所在行、所在列和所在的 3 × 3 宫。行和列可以直接索引；宫则是 bug 藏身之处。用 (r / 3) * 3 + c / 3 给宫编号，从 0 到 8。遍历 81 个单元格一次，就能检查全部 27 个组。
逐一检查每一行、每一列和每一个宫格
思路
规则中有 27 个分组：9 行、9 列和 9 个宫。收集每组中的 9 个单元格，查找重复的数字，忽略点号。当且仅当每个分组都没有重复数字时，棋盘才有效。
为每个数字设置一个已见标记，就能在 9 个单元格中找到重复项。81 个单元格中的每个单元格都会在其所属的 3 个分组中各读取一次：共读取 243 次，工作量固定。对于 n × n 棋盘，同样的方法需要 O(n²) 的时间。
算法
- 对于从 0 到 8 的
i，收集第i行、第i列和第i个宫格。 - 第
i个宫格的左上角位于第3 * (i / 3)行、第3 * (i % 3)列；其中第k个单元格位于它下方k / 3行、右侧k % 3列。 - 使用全新的已见标记遍历每个分组，跳过点。如果某个数字已经标记，则返回
false。 - 遍历完全部 27 个分组后，返回
true。
def has_repeat(cells):
seen = set()
for ch in cells:
if ch == '.':
continue
if ch in seen:
return True
seen.add(ch)
return False
def isValidSudoku(board):
for r in range(9):
if has_repeat(board[r][c] for c in range(9)):
return False
for c in range(9):
if has_repeat(board[r][c] for r in range(9)):
return False
for top in (0, 3, 6):
for left in (0, 3, 6):
box = (board[top + i][left + j] for i in range(3) for j in range(3))
if has_repeat(box):
return False
return True每行、每列和每个宫格都使用一个已访问表进行一次遍历
思路
每个单元格只访问一次，并同时检查全部三个条件。用三张 9 × 9 的标记表：seenRow[r][d] 表示数字 d+1 已经出现在第 r 行中，seenCol 和 seenBox 的作用相同。
单元格 (r, c) 属于区块 (r / 3) * 3 + c / 3。前半部分选出由三个区块组成的横排，c / 3 则选出横排中的区块。单元格 (4, 7) 位于区块 1 * 3 + 2 = 5，也就是中间偏右的区块。
如果某个标记已经设置，就表示该数字在对应的组中重复了。每个单元格只读取一次，这些表共存储 243 个标记：在这里，时间和内存都是固定的；对于 n × n 棋盘，复杂度为 O(n²)。
算法
- 创建
seenRow、seenCol和seenBox，每个都是 9 × 9，且所有值都为 false。 - 对于每个已填入的单元格
(r, c)，令d等于该单元格中的数字减 1，并令b = (r / 3) * 3 + c / 3。 - 如果
seenRow[r][d]、seenCol[c][d]或seenBox[b][d]已设置，则返回false；否则，将这三个值都设置为 true。 - 检查完最后一个单元格后，返回
true。
def isValidSudoku(board):
# seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
seen_row = [[False] * 9 for _ in range(9)]
seen_col = [[False] * 9 for _ in range(9)]
seen_box = [[False] * 9 for _ in range(9)]
for r in range(9):
for c in range(9):
ch = board[r][c]
if ch == '.':
continue
d = int(ch) - 1
b = (r // 3) * 3 + c // 3
if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
return False
seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
return True
易错点和边界情况
- 用
r / 3 + c / 3计算宫格编号。它只会得到 0 到 4，因此(0, 3)和(3, 0)虽然位于不同的宫格，却会得到相同的编号，那里两个 7 会被报告为重复项。 - 在 JavaScript、Python 3 或 Lua 中用
/做除法，此时4 / 3的结果是1.33。要向下取整。 - 把
.当作一个值。空棋盘每行有 9 个点，也是有效的。 - 试图解开谜题。第 0 行是
12345678.，而第 8 列下方有一个 9，这种情况永远无法完成，但没有任何重复项：true。 - 忽略宫格。一个完整的网格中，每一行都是上一行向左移动一位，行或列中都没有重复项，但每个宫格里都有重复项。
常见问题3
有效数独的时间复杂度是多少？
棋盘始终有 81 个单元格，因此这两种方法的运行时间和内存占用都是 O(1)。对于一般的 n × n 数独，一次遍历检查会读取每个 n² 单元格一次，并保存 3n² 个标记：时间和内存复杂度都是 O(n²)。
有效的数独棋盘一定有解吗？
不对。这里的“有效”仅表示已填入的数字在同一行、同一列或同一个 3 × 3 宫内没有重复。棋盘可能通过这项检查，但仍然无解。判断是否有解需要使用回溯等搜索方法，这是另一个问题。
可以用位掩码解决 Valid Sudoku 吗？
是的。给每一行、每一列和每一个宫格分配一个整数，其中位 d 表示已出现数字 d+1。对于已填入的单元格，如果 1 << d 与这三个掩码中的任意一个进行 AND 运算后结果非零，就说明数字重复了；否则就将它 OR 到这三个掩码中。这样只需 27 个整数，而不是 243 个标记。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isValidSudoku(board):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
预期输出
true