python - 填写数独板-回溯解题

Question

我为下面复制的 Leetcode 问题编写了以下解决方案:

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character '.'. Note:

The given board contain only digits 1-9 and the character '.'. You may assume that the given Sudoku puzzle will have a single unique solution. The given board size is always 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 的棋盘。该问题保证每个测试用例都有正确的解决方案。我已经遍历此代码数十次，但看不出问题所在。

(我知道我可以使用约束传播来加速解决方案，但当前的问题不是我的解决方案太慢 - 而是它的不正确)。

有人知道为什么吗？此外，如果问题陈述中不清楚这一点，则每个数字都应该是一个字符串。

Answer 1

如果您提供正确的解决方案，您的验证函数将返回真。您可以通过给它提供一个已解决的数独板来自己验证这一点:

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()，而不仅仅是在电路板完成时...但这是值得的，因为否则您将花费​​大量时间探索显然永远不会起作用的电路板。

您需要先解决这两个问题，然后您的算法才能工作。