如何实现无模块导入的Alphametics（字母算术题）求解函数？

问题需求 #

实现Python函数alphametics(puzzle)，输入为大写字母算术题字符串（例如'SEND + MORE = MONEY'），需满足：

• 将每个唯一字母替换为唯一十进制数字，使加法等式成立
• 禁止导入任何模块
• 等式中的数字不能有前置零
• 左侧加数数量为2-7个，每个加数长度2-8字符
• 输入始终有效，无需校验
• 存在多解时返回任意一个即可
• 避免暴力枚举超时（最多包含10个唯一字母）

当前错误实现：

def alphametics(puzzle):
    return [ord(char) - 96 for char in puzzle.lower()]

该代码返回字母对应的序号列表，正确输出应为替换后的算术等式字符串（如'9567 + 1085 = 10652'）。

解决方案 #

采用带剪枝的回溯算法，通过位权重转化和分支剪枝大幅减少搜索空间，核心步骤如下：

1. 输入解析与预处理 #

拆分加数和结果，提取所有唯一字母，记录不能为0的首字母，并按字母出现频率排序（高频优先，加速剪枝）。

2. 构建权重方程 #

将加法等式转化为权重线性方程：每个字母的权重等于其在所有加数中的位值之和，减去其在结果中的位值之和。最终等式成立的条件是所有字母的（数字×权重）总和为0。

3. 回溯搜索与剪枝 #

递归分配数字，每一步验证当前已分配字母的权重和，结合剩余字母的最大/最小可能权重和，判断是否有可能满足等式，提前排除无效分支。

完整代码 #

def alphametics(puzzle):
    # 拆分加数和结果
    left_part, result = puzzle.split(' = ')
    addends = left_part.split(' + ')
    all_words = addends + [result]
    
    # 提取唯一字母和首字母集合（首字母不能为0）
    unique_chars = list(set(''.join(all_words)))
    first_chars = {word[0] for word in all_words}
    
    # 按字母出现频率降序排序，优先处理高频字母
    char_count = {}
    for word in all_words:
        for c in word:
            char_count[c] = char_count.get(c, 0) + 1
    unique_chars.sort(key=lambda x: -char_count[x])
    
    # 计算每个字母的权重：加数中的位值和减去结果中的位值和
    char_weight = {}
    for word in addends:
        for idx, c in enumerate(reversed(word)):
            char_weight[c] = char_weight.get(c, 0) + 10 ** idx
    for idx, c in enumerate(reversed(result)):
        char_weight[c] = char_weight.get(c, 0) - 10 ** idx
    
    assigned = {}
    used_digits = set()
    
    def backtrack(char_idx):
        if char_idx == len(unique_chars):
            # 验证权重和为0，等式成立
            total = 0
            for c, w in char_weight.items():
                total += assigned[c] * w
            return total == 0
        
        current_char = unique_chars[char_idx]
        # 首字母不能为0，起始数字从1开始
        start = 1 if current_char in first_chars else 0
        
        for digit in range(start, 10):
            if digit in used_digits:
                continue
            
            assigned[current_char] = digit
            used_digits.add(digit)
            
            # 剪枝：计算当前权重和，判断剩余字母的可能范围能否抵消当前值
            current_total = sum(assigned[c] * char_weight.get(c, 0) for c in assigned)
            remaining_min = 0
            remaining_max = 0
            
            for c in unique_chars[char_idx+1:]:
                w = char_weight.get(c, 0)
                if w > 0:
                    remaining_min += 0 * w
                    remaining_max += 9 * w
                else:
                    remaining_min += 9 * w
                    remaining_max += 0 * w
            
            if current_total + remaining_min <= 0 <= current_total + remaining_max:
                if backtrack(char_idx + 1):
                    return True
            
            # 回溯
            del assigned[current_char]
            used_digits.remove(digit)
        
        return False
    
    # 执行回溯搜索
    backtrack(0)
    
    # 替换字母为数字，生成结果字符串
    def replace(s):
        return ''.join(str(assigned[c]) for c in s)
    
    replaced_addends = [replace(add) for add in addends]
    return ' + '.join(replaced_addends) + ' = ' + replace(result)

代码说明 #

• 权重计算：将加法逻辑转化为数学方程，简化等式验证
• 剪枝优化：通过高频字母优先和实时权重范围校验，避免无效搜索分支
• 前置零处理：首字母分配数字时从1开始，直接排除非法情况

测试示例 #

print(alphametics('SEND + MORE = MONEY'))
# 输出：9567 + 1085 = 10652

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