Python递归数独求解器重复值问题及优化后死循环困境

我尝试通过递归实现数独求解器，将每个空位的可能值存储在以索引为键、可能值集合为值的字典中。参数b是扁平化处理后的数独棋盘列表，get_row、get_col、get_box方法可正确返回对应行、列、宫的数值。当字典中某一条目的集合仅含单个元素时，将其填入棋盘b；若不存在此类集合，则从可能值中选取一个并启动递归。

初始完整可复现代码 #

from typing import List

class Sudoku:
    def solve_it(self, board: List[List[str]]) -> None:
        """
        :param board: sudoku board gets modified inplace at .create_board_from_list
        :return: None
        """
        unit_values = []
        for i in range(len(board)):  # 扁平化棋盘为一维列表
            for j in range(len(board[i])):
                unit_values.append(board[i][j])
        self.go_through_recursive(board, unit_values)

    def get_row(self, n: int, b):  # 获取第n行的所有元素
        assert 0 <= n <= 8
        return set(b[9 * n: 9 * (n + 1)])

    def get_col(self, n: int, b):  # 获取第n列的所有元素
        assert 0 <= n <= 8
        return set(b[n::9])

    def get_box(self, n: int, b):  # 获取第n宫的所有元素
        assert 0 <= n <= 8
        return set(b[i] for i in range(81) if (i // 27) == (n // 3) and i % 9 // 3 == n % 3)

    def go_through_recursive(self, board, b, d=False):
        """
        :param board: 二维矩阵形式的数独棋盘
        :param b: 一维列表形式的数独棋盘
        """
        numbers = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
        while True:

            if d:
                return True

            missing_dict = {}  # 填充空位的可能值字典
            for idx in range(len(b)):
                if b[idx] == '.':
                    row, col, box = idx // 9, idx % 9, (idx // 27) * 3 + (idx % 9) // 3
                    # 合并当前行、列、宫中已存在的数值
                    values = self.get_row(row, b).union(self.get_col(col, b)).union(self.get_box(box, b))
                    values.remove('.')
                    missing_ones = numbers.difference(values)  # 当前空位的可能值
                    if len(missing_ones) == 0:  # 无可行值，当前路径无效
                        return False
                    missing_dict[idx] = missing_ones

            old_count = b.count('.')
            # 遍历字典，填入唯一可能值
            for idx, missings in missing_dict.items():
                if len(missings) == 1:
                    b[idx] = missings.pop()

            if b.count('.') == 0:  # 棋盘已填满
                self.create_board_from_list(board, b)
                return True

            if b.count('.') == old_count:  # 无进展，启动递归尝试
                for idx, s in missing_dict.items():
                    for number in s:
                        if d:
                            return True
                        bb = b[:]
                        bb[idx] = number
                        d = self.go_through_recursive(board, bb)

    def create_board_from_list(self, board, b):
        temp_board = []
        chunk = 9
        for idx in range(0, len(b), chunk):
            temp_board.append(b[idx: idx + chunk])
        for idx in range(len(board)):
            board[idx] = temp_board[idx]
        print('done')

问题现象 #

求解完成后，棋盘的行、列或宫中存在重复数值。排查发现，在计算空位可能值时，偶尔会返回全量的1-9集合，这可能是导致数值错误覆盖的原因：

row, col, box = idx // 9, idx % 9, (idx // 27) * 3 + (idx % 9) // 3
values = self.get_row(row, b).union(self.get_col(col, b)).union(self.get_box(box, b))
values.remove('.')  # 有时得到的集合仅包含少量元素，但偶尔会返回全量1-9

测试输入棋盘 #

board = 
[[".",".","9","7","4","8",".",".","."],
 ["7",".",".",".",".",".",".",".","."],
 [".","2",".","1",".","9",".",".","."],
 [".",".","7",".",".",".","2","4","."],
 [".","6","4",".","1",".","5","9","."],
 [".","9","8",".",".",".","3",".","."],
 [".",".",".","8",".","3",".","2","."],
 [".",".",".",".",".",".",".",".","6"],
 [".",".",".","2","7","5","9",".","."]]

正确输出 #

board =
[["5","1","9","7","4","8","6","3","2"],
 ["7","8","3","6","5","2","4","1","9"],
 ["4","2","6","1","3","9","8","7","5"],
 ["3","5","7","9","8","6","2","4","1"],
 ["2","6","4","3","1","7","5","9","8"],
 ["1","9","8","5","2","4","3","6","7"],
 ["9","7","5","8","6","3","1","2","4"],
 ["8","3","2","4","9","1","7","5","6"],
 ["6","4","1","2","7","5","9","8","3"]]

代码错误输出 #

board = 
[["3","1","9","7","4","8","6","5","2"],
 ["7","8","5","6","3","2","1","1","9"],
 ["4","2","6","1","5","9","8","7","3"],
 ["5","3","7","9","8","6","2","4","1"],
 ["2","6","4","3","1","7","5","9","8"],
 ["1","9","8","5","2","4","3","6","7"],
 ["9","7","1","8","6","3","4","2","5"],
 ["8","5","2","4","9","1","7","3","6"],
 ["6","4","3","2","7","5","9","8","4"]]

编辑说明 #

修改了go_through_recursive方法，将唯一可能值直接填入棋盘，此时字典中仅存在长度为2及以上的集合，但修改后代码陷入无限循环：

def go_through_recursive(self, board, b, d=False):
    """
    :param board: 二维矩阵形式的数独棋盘
    :param b: 一维列表形式的数独棋盘
    """
    numbers = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
    while True:

        old_count = b.count('.')
        missing_dict = {}  # 填充空位的可能值字典
        for idx in range(len(b)):
            if b[idx] == '.':
                row, col, box = idx // 9, idx % 9, (idx // 27) * 3 + (idx % 9) // 3
                # 合并当前行、列、宫中已存在的数值
                values = self.get_row(row, b).union(self.get_col(col, b)).union(self.get_box(box, b))
                values.remove('.')
                missing_ones = numbers.difference(values)  # 当前空位的可能值
                if len(missing_ones) == 0:  # 无可行值，当前路径无效
                    return False
                elif len(missing_ones) == 1:
                    b[idx] = missing_ones.pop()
                else:
                    missing_dict[idx] = missing_ones

        if b.count('.') == 0:  # 棋盘已填满
            self.create_board_from_list(board, b)
            return True

        if b.count('.') == old_count:  # 无进展，启动递归尝试
            for idx, s in missing_dict.items():
                for number in s:
                    bb = b[:]
                    bb[idx] = number
                    if self.go_through_recursive(board, bb):
                        return True

内容的提问来源于stack exchange，提问作者Fabio Olivetto