Sudoku Solver
数独棋盘是一个 9 × 9 的网格，分为九个 3 × 3 的方框。解出的棋盘中，每一行、每一列和每个方框都恰好包含一次从 1 到 9 的每个数字。
谜题以 9 个字符串的形式给出，从最上面一行开始，每行一个；. 表示空格。填满所有空格，并以相同的形式返回解出的棋盘。这个棋盘恰好有一个解。
函数
- boardstring-array
- 谜题的 9 行，每个空单元格中都有一个点
- 返回值string-array
- 已完成棋盘的 9 行
约束条件
board中有 9 个长度为 9 的字符串。- 每个字符都是
.或数字1到9中的一个。 - 给定的数字在每一行、每一列或每个宫格内都不会重复。
- 棋盘恰好有一个解。
示例
- 输入
- board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
- 输出
- ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
- 解释
- 最上面一行
9.7.....6已经有 9、7 和 6，所以这一行的六个空格要填入 1、2、3、4、5 和 8。列和宫格决定每个数字的位置，这一行最终变成957214386。
进阶
在杀手数独中，格子组成的笼也必须加起来等于给定的和。你会如何将这条规则加入搜索，并用它尽早剪掉分支？
提示
逐个打开提示，每个都会多透露一点。
记录每一行、每一列和每个 3 × 3 宫已经包含哪些数字。这样，你就能在 O(1) 时间内判断某个数字是否适合填入空格。
一次填写一个空格。尝试所有适合该空格的数字，然后继续填写下一个空格。如果用这个数字无法完成棋盘，就撤销它。
单元格的顺序很重要。接下来先填剩余数字最少的空单元格：只有一个选项的单元格不需要分支尝试，而没有选项的单元格会立即告诉你需要回退。
题解
用回溯法解决：放入一个合适的数字，继续尝试；如果无法完成棋盘，就撤销这一步。单元格的顺序会影响速度。在较难的棋盘上，按阅读顺序处理可能会遍历数亿个未完成的棋盘；优先填入可选项最少的单元格，大约只需遍历一百个。
按阅读顺序回溯
结果正确，但无法在最大的测试中运行完毕
思路
按读取顺序填入空白单元格，每格都填入符合条件的最小数字。如果某个单元格没有剩下可填的数字，就回到上一个单元格，尝试下一个数字。依次尝试每一种符合规则的组合，搜索就能找到答案。
用三个表让每次适配检查的时间复杂度为 O(1)：rowUsed[r][d]、colUsed[c][d] 和 boxUsed[b][d]，其中盒子的编号为 b = (r / 3) * 3 + c / 3。填入数字时设置这三个表中的对应项，移除数字时则清除它们。
固定顺序是这个方法的弱点：搜索可能会在整行填入局部看来符合条件的数字，之后才发现它们让许多单元格无数可填。对于顶部几行几乎没有提示数字、答案又是较大数字的棋盘，搜索会遍历超过 3 亿个部分棋盘。
算法
- 将棋盘读入一个网格，空单元格用 0 表示，填充
rowUsed、colUsed和boxUsed，并按从左到右、从上到下的顺序列出空单元格。 backtrack(k)：如果k等于空单元格的数量，则返回 true。- 对于单元格
k所在的行、列和宫中尚未使用的每个数字d（从 1 到 9），填入该数字并标记；如果backtrack(k+1)返回 true，则返回 true，否则取消标记。 - 如果没有可用的数字，就清空该单元格并返回 false。调用
backtrack(0)，然后将网格转换回字符串。
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# row_used[r][d] is True when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
row_used = [[False] * 10 for _ in range(9)]
col_used = [[False] * 10 for _ in range(9)]
box_used = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
else:
empties.append((r, c))
def backtrack(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
grid[r][c] = d
row_used[r][d] = col_used[c][d] = box_used[b][d] = True
if backtrack(k + 1):
return True
row_used[r][d] = col_used[c][d] = box_used[b][d] = False
grid[r][c] = 0
return False
backtrack(0)
return ["".join(str(d) for d in row) for row in grid]先填入最空的单元格
思路
答案不取决于填入顺序，所以要选择能缩小搜索范围的顺序：每一步都填入允许数字最少的空格。只允许一个数字的格子是确定的，不会增加分支。允许的数字为 0 个的格子会立即被选中，因此可以马上发现错误的棋盘。
为了快速统计每一步 81 个格子允许的数字，可以将每一行、每一列和每个宫格存为位掩码：当数字 d 在第 r 行中时，rows[r] 的第 d 位会被设为 1。一个格子允许的数字为 ~(rows[r] | cols[c] | boxes[b]) & 0x3FE，其中 0x3FE 保留第 1 位到第 9 位，允许的数字数量就是设为 1 的位数。放入 d 时，会在三个掩码中都设定第 d 位；执行异或运算则会将它移除。
算法
- 根据给定的数字构建网格以及掩码
rows、cols和boxes。 backtrack()：扫描所有单元格，计算每个空单元格允许填入的数字，并保留允许数字最少的第一个单元格。如果没有空单元格，则返回 true。- 对于该单元格允许填入的每个数字，填入该数字，并在三个掩码中设置对应的位。如果
backtrack()返回 true，则返回 true；否则清除这些位。 - 如果没有数字可用，则清空该单元格并返回 false。调用
backtrack()，再将网格转换回字符串。
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# Bit d of rows[r] is set when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
rows[r] |= 1 << d
cols[c] |= 1 << d
boxes[(r // 3) * 3 + c // 3] |= 1 << d
def backtrack():
# Pick the empty cell with the fewest digits left (the first one on a tie).
best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
# Bits 1 to 9 of 0x3FE are the nine digits.
allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
count = bin(allowed).count("1")
if count < best_count:
best_r, best_c, best_allowed, best_count = r, c, allowed, count
if best_r == -1:
return True # no empty cell is left: the board is solved
r, c = best_r, best_c
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
bit = 1 << d
if best_allowed & bit:
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
if backtrack():
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
grid[r][c] = 0
return False
backtrack()
return ["".join(str(d) for d in row) for row in grid]
易错点和边界情况
- 撤销时，忘记从行、列和宫格记录中清除数字。之后的单元格会将该数字视为已使用，搜索也就找不到解。
- 用
r / 3 + c / 3计算宫格。单元格(0, 4)和(4, 0)都会得到 1，因此两个宫格共用一条记录，棋盘永远无法填满。使用整数除法计算(r / 3) * 3 + c / 3。 - 找到第一个解后没有停止。在你读取棋盘之前，撤销步骤会再次清空棋盘。
常见问题3
回溯数独求解器的时间复杂度是多少？
最坏情况下，时间复杂度呈指数级，对于 m 个空格，复杂度为 O(9^m)，因为每个空格最多可以分支出 9 个数字。在实际数独题中，行、列和宫的规则会剪掉大多数分支，而优先填入空格最多的单元格可以剪掉剩下的大部分分支。
如何检查数独是否恰好有一个解？
运行相同的回溯搜索，但要统计解的数量，并在数量达到 2 时停止。数量为 1 表示谜题有唯一解，数量为 0 表示无解。谜题生成器会在每次移除一个提示后运行此检查。
有没有比回溯法更快的数独解法？
大多数快速求解器仍会回溯，但会在每次猜测前进行更多推理。约束传播会填入所有只有一个选项的单元格，以及所在行、列或宫中某个数字只能填入一个单元格的位置，然后重复这一过程。数独也可以表述为一个精确覆盖问题，并使用 Knuth 的算法 X 求解。
def solveSudoku(board):
# 在这里编写代码测试 #1
参数
board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
预期输出
["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]