Python中类数独行无重复排列的高效生成方案求助

你的核心问题是避免先生成所有可能组合再过滤，而是在生成过程中就排除重复数字，这里用回溯法是最优解——在每一步选择数字时，只选当前位置候选集中未被使用过的数字，从根源上避免无效组合的生成。

基础回溯实现 #

先统一处理输入（把确定值转为单元素候选集），再通过递归逐个位置选择合法数字，过程中维护已使用的数字集合，确保不重复：

def get_valid_row_combinations(row):
    # 预处理：将所有元素转为候选集合，同时检查初始冲突
    processed = []
    used_fixed = set()
    for item in row:
        if isinstance(item, (int, float)):
            num = int(item)
            if num in used_fixed:
                return []  # 存在重复的确定值，无合法组合
            processed.append({num})
            used_fixed.add(num)
        else:
            # 列表/集合转成集合，去重候选值并排除已占用数字
            candidates = set(item) - used_fixed
            if not candidates:
                return []  # 当前位置无可用候选，无合法组合
            processed.append(candidates)
    
    result = []
    
    def backtrack(pos, used, path):
        if pos == len(processed):
            result.append(tuple(path))
            return
        # 遍历当前位置的候选，且未被使用过的数字
        for num in processed[pos] - used:
            backtrack(pos + 1, used | {num}, path + [num])
    
    backtrack(0, used_fixed, [])
    return result

# 测试示例1
row1 = [[1, 2, 3, 4], [1, 2, 3], [1, 2, 3, 6], [1, 2, 4], [1, 3, 4, 5, 6], [2, 3, 4, 5]]
print(len(get_valid_row_combinations(row1)))  # 输出32，和原方法结果一致

# 测试示例2
row2 = [[1, 2, 3], [1, 2, 3], 5, 6, [1, 3, 4], [2, 3, 4]]
print(len(get_valid_row_combinations(row2)))

优化：启发式回溯（优先处理候选少的位置） #

如果行中某些位置候选集很小（比如只有1个选项），优先处理这些位置可以更早剪枝，大幅减少递归次数。实现思路是先对位置按候选集大小排序，记录原始索引，最后再把结果还原回原始顺序：

def get_valid_row_combinations_optimized(row):
    # 预处理，同时记录原始索引
    processed = []
    used_fixed = set()
    for idx, item in enumerate(row):
        if isinstance(item, (int, float)):
            num = int(item)
            if num in used_fixed:
                return []
            processed.append(({num}, idx))
            used_fixed.add(num)
        else:
            candidates = set(item) - used_fixed
            if not candidates:
                return []
            processed.append((candidates, idx))
    
    # 按候选集大小升序排序，优先处理候选少的位置
    processed.sort(key=lambda x: len(x[0]))
    
    result = []
    
    def backtrack(pos, used, path_map):
        if pos == len(processed):
            # 还原回原始顺序
            final_path = [None] * len(row)
            for num, idx in path_map.items():
                final_path[idx] = num
            result.append(tuple(final_path))
            return
        candidates, idx = processed[pos]
        for num in candidates - used:
            # 记录数字对应的原始索引
            new_path = path_map.copy()
            new_path[num] = idx
            backtrack(pos + 1, used | {num}, new_path)
    
    backtrack(0, used_fixed, {})
    return result

# 测试优化版本
print(len(get_valid_row_combinations_optimized(row1)))  # 同样输出32，但效率更高

为什么比原方法高效？ #

原方法用itertools.product会生成所有笛卡尔积（比如你的例子是4×3×4×3×5×4=2880个），再过滤掉重复的；而回溯法在每一步只选择未使用过的数字，完全不会生成无效组合，对于候选集约束越强的场景，效率提升越明显。

比如你的第一个示例，回溯法只会生成32个合法组合对应的分支，不会浪费资源在重复数字的组合上。

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