我为下面复制的Leetcode问题编写了以下解决方案：
编写一个程序，通过填充空单元格来解决数独难题。
数独解决方案必须满足以下所有规则：
每个数字 1-9 必须在每行中恰好出现一次。每个 数字 1-9 必须在每列中恰好出现一次。每个 数字 1-9 必须在 9 个 3x3 子框中的每一个中恰好出现一次 网格。空单元格由字符"."表示。 注意：
给定的板仅包含数字 1-9 和字符"."。你可以 假设给定的数独谜题将具有一个唯一的 溶液。给定的电路板尺寸始终为 9x9。
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
EMPTY_CELL = '.'
target = set(str(n) for n in range(1, 10))
def _validate():
cols = [[board[r][c] for r in range(9)] for c in range(9)]
boxes = []
for i in (0, 3, 6):
for j in (0, 3, 6):
boxes.append([board[a][b] for a in range(i, i + 3) for b in range(j, j + 3)])
valid_rows = all(set(row) == target for row in board)
valid_cols = valid_rows and all(set(col) == target for col in cols)
valid_boxes = valid_cols and all(set(box) == target for box in boxes)
return valid_boxes
def helper(r, c):
if c == len(board[0]):
return helper(r + 1, 0)
if r == len(board):
return _validate()
if not board[r][c] == EMPTY_CELL:
return helper(r, c + 1)
for n in range(1, 10):
board[r][c] = str(n)
if helper(r, c + 1):
return True
return False
helper(0, 0)
这是我用简单的英语制定的策略。对于每个空的单元格，我尝试在该单元格中放置一个数字，并在板的其余部分递归。如果这不能导致有效的解决方案，我会回溯，增加数字，然后递归将该数字放在空单元格中。
我的验证函数是为所有内容返回False，我最终在空白处得到一个带有9的板。该问题保证每个测试用例都有一个正确的解决方案。我已经浏览了数十次这段代码，但无法看到问题所在。
(我知道我可以使用约束传播来加速解决方案，但当前的问题不是我的解决方案太慢 - 而是它不正确)。
有人明白为什么吗？此外，如果问题陈述中不清楚这一点，则每个数字都应该是一个字符串。
如果您向验证函数提供正确的解决方案，它将返回 true。您可以通过向它提供已解决的数独板来自己验证这一点：
solved_text = '''435269781
682571493
197834562
826195347
374682915
951743628
519326874
248957136
763418259'''
solved_board = [ list(line) for line in solved_text.split('n') ]
有两个问题。首先，您实际上并没有搜索解决方案的完整空间。如果你打印每个完整的板进入_validate()，你会注意到一些奇怪的事情：整个板总是按词法顺序排列！这不是 10^81 组可能的板。这可以通过简单地省略这两行代码来解决：
if not board[r][c] == EMPTY_CELL:
return helper(r, c + 1)
这些会导致问题，因为您将板状态作为副作用进行变异，但在回溯时不会清理(放回空单元格)。您可以简单地省略这两行(这样helper()中的算法就永远不会关心 (r，c) 词法排序中的右边是什么)，或者通过添加代码来设置回溯时的board[r][c] = EMPTY_CELL。
另一个问题是，因为你只在完整的板上运行验证，并且因为你的验证函数只能检查完整的板的正确性，所以你的算法实际上必须遍历所有 10^81 个可能的板才能找到解决方案。这不仅很慢，而且完全难以解决！相反，您应该重写验证函数，以便它可以验证部分电路板。例如，如果第一行是 ['1'， '1'， '.'， ...， '.']，它应该返回 False，但如果第一行是 ['1'， '2'， '.'， ...， '.']，它应该返回 True，因为到目前为止没有任何问题。显然，您现在还必须在每一步都调用 _validate()，而不仅仅是在电路板完成时......但这是值得的，因为否则您将花费大量时间探索显然永远不会起作用的板。
在算法起作用之前，您需要解决这两个问题。
你没有正确的验证！您的验证仅适用于最终解决方案。除非您尝试为您的数独提供所有可能的填写，否则此验证不会给您任何检查(并且始终为假)。
我脑海中回溯算法的伪代码如下：
- 从单元格 (0,0) 扫描到单元格 (8,8)，找到一个空的
- 测试选项"1"到"9"
- 对每个选项调用验证，如果有效，则重复到上面的扫描行
- 如果验证失败，请尝试其他选项
- 如果将所有选项"1"放大到"9"，以前的递归级别无效，请尝试另一个
所以验证不是检查是否所有行、列、框都有 1 到 9，而是检查它们是否没有重复！在python代码中，它表示len(x) == len(set(x))x行，列或框，它只需要"1"到"9"，而不是"."。