修改回溯法解谜函数以统计谜题全部可行解数量

问题描述 #

我有一个用回溯法解决谜题的函数，原本只能找到并返回单个解。现在我修改它来统计该谜题的所有可行解数量——复用了原单解函数的逻辑实现统计功能，但调试时能看到计数在增加，最终却返回不了真实的统计结果。

原代码 #

def helper_solve_puzzle(picture,constraints_set,row,col,count,find_all):
    if check_constraints(picture, constraints_set) == 1 and is_full(picture):  # 找到一个解
        count[0] += 1
        if not find_all:
            return picture
    if type(index_validity(picture,row,col)) == tuple:
        row, col = index_validity(picture, row, col)  # 检查索引有效性并更新
        picture = paint_cell(picture,row,col) # 涂色单元格
        is_legal = check_constraints(picture,constraints_set)
        if is_legal == 0: # 涂色不合法，撤销并处理下一个单元格
            picture = paint_cell(picture, row, col)
            return helper_solve_puzzle(picture,constraints_set,row,col+1,count,find_all)
        elif is_legal == 2: # 涂色合法，标记为"最后修改"并处理下一个单元格
            return helper_solve_puzzle(picture,constraints_set,row,col+1,count,find_all)
    elif not index_validity(picture,row,col): # 索引无效，回溯到最后修改的单元格重新尝试
        row,col = find_last_changed(picture)
        if no_solution(picture):
            return count[0]
        picture = update_picture(picture,row, col)
        return helper_solve_puzzle(picture,constraints_set,row,col+1,count,find_all)
    return count[0]

问题根源 #

1. 提前返回截断回溯流程：
   代码在多个分支中用return直接返回递归结果，比如涂色合法/不合法时直接终止当前分支的后续操作，导致解空间未被完整遍历。此外，找到解且开启全解统计时，没有继续回溯探索其他可能的解路径。

2. 回溯撤销逻辑不完整：
   仅在涂色不合法时执行了撤销操作，合法涂色后的递归返回阶段，没有撤销当前涂色来尝试其他可能性，遗漏了部分解路径。

3. 返回时机混乱：
   回溯到无有效索引时提前返回计数，此时可能还有未遍历的分支，导致统计结果不准确。

修复方案 #

核心修改点 #

• 移除不必要的提前返回，确保递归遍历所有解分支；
• 为每个修改操作添加对应的撤销步骤，放在递归调用之后；
• 区分单解/全解的返回逻辑：单解找到即返回，全解遍历完所有分支后再返回计数。

修改后的代码 #

def helper_solve_puzzle(picture, constraints_set, row, col, count, find_all):
    # 找到完整合法解时的处理
    if check_constraints(picture, constraints_set) == 1 and is_full(picture):
        count[0] += 1
        # 找单解则直接返回，找全解则继续回溯其他分支
        if not find_all:
            return picture
        return

    idx_result = index_validity(picture, row, col)
    if isinstance(idx_result, tuple):
        row, col = idx_result
        # 尝试第一种涂色状态
        picture = paint_cell(picture, row, col)
        is_legal = check_constraints(picture, constraints_set)
        # 合法则继续递归，不提前返回
        if is_legal in (1, 2):
            result = helper_solve_puzzle(picture, constraints_set, row, col+1, count, find_all)
            # 找单解时如果已经找到，直接返回结果
            if not find_all and result is not None:
                return result
        
        # 撤销涂色，尝试另一种状态
        picture = paint_cell(picture, row, col)
        result = helper_solve_puzzle(picture, constraints_set, row, col+1, count, find_all)
        if not find_all and result is not None:
            return result
    
    elif not idx_result:
        row, col = find_last_changed(picture)
        # 确认无可行解时，终止当前分支
        if no_solution(picture):
            return None if find_all else None
        # 回溯修改，尝试其他可能
        picture = update_picture(picture, row, col)
        result = helper_solve_puzzle(picture, constraints_set, row, col+1, count, find_all)
        if not find_all and result is not None:
            return result
    
    # 全解模式返回最终计数；单解模式没找到则返回None
    return count[0] if find_all else None

说明 #

• 每次尝试涂色后，递归返回都会执行撤销操作，确保能探索当前单元格的两种状态（涂色/不涂色）；
• 全解模式下，找到解后不返回，继续遍历剩余分支；
• 仅在单解模式下找到解时才立即返回，避免打断回溯；
• 所有分支遍历完成后才返回计数，保证统计结果完整。

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