在数学和逻辑学中，有一种有趣的谜题叫做字母算术（Alphametics），也被称为文字算术或密码算术。这类谜题将数字替换为字母，要求找出每个字母代表的数字，使得等式成立。最著名的例子是 “SEND + MORE = MONEY”。在 Exercism 的 “alphametics” 练习中，我们将实现一个通用的字母算术求解器，这不仅能帮助我们理解约束满足问题，还能深入学习 Rust 中的算法实现和组合优化。

问题背景

字母算术谜题有以下规则：

  1. 每个字母代表一个唯一的数字（0-9）
  2. 不同的字母必须代表不同的数字
  3. 相同的字母必须代表相同的数字
  4. 单词的首字母不能为 0
  5. 等式必须成立

例如，经典的 “SEND + MORE = MONEY” 谜题的解是：
S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2

因为 9567 + 1085 = 10652。

让我们先看看练习提供的函数签名：

use std::collections::HashMap;

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
    unimplemented!("Solve the alphametic {:?}", input)
}

我们需要实现一个函数，它能够：

  1. 解析输入的字母算术表达式
  2. 找到满足条件的数字分配方案
  3. 返回字母到数字的映射关系，如果无解则返回 None

算法思路

解决字母算术问题主要有两种方法：

  1. 暴力搜索：尝试所有可能的数字组合
  2. 约束传播：利用约束条件减少搜索空间

考虑到问题的复杂性，我们将采用暴力搜索结合剪枝的方法。

实现步骤

1. 解析输入

首先我们需要解析输入字符串，提取所有字母和数字关系：

use std::collections::HashMap;

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
    // 移除空格并分割等式
    let parts: Vec<&str> = input.split("==").collect();
    if parts.len() != 2 {
        return None;
    }
    
    let right = parts[1].trim();
    let left_parts: Vec<&str> = parts[0].split('+').map(|s| s.trim()).collect();
    
    // 收集所有唯一字母
    let mut unique_chars = std::collections::HashSet::new();
    let mut first_chars = std::collections::HashSet::new();
    
    for part in &left_parts {
        if part.is_empty() {
            return None;
        }
        first_chars.insert(part.chars().next().unwrap());
        for c in part.chars() {
            if c.is_alphabetic() {
                unique_chars.insert(c);
            }
        }
    }
    
    first_chars.insert(right.chars().next().unwrap());
    for c in right.chars() {
        if c.is_alphabetic() {
            unique_chars.insert(c);
        }
    }
    
    let chars: Vec<char> = unique_chars.into_iter().collect();
    
    // 如果字母数超过10个，则无解
    if chars.len() > 10 {
        return None;
    }
    
    // ... 继续实现求解逻辑
    None
}

2. 生成排列并验证

我们需要生成 0-9 数字的所有排列，并验证哪个满足等式：

use std::collections::HashMap;

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
    // 解析输入
    let parts: Vec<&str> = input.split("==").collect();
    if parts.len() != 2 {
        return None;
    }
    
    let right = parts[1].trim();
    let left_parts: Vec<&str> = parts[0].split('+').map(|s| s.trim()).collect();
    
    // 收集所有唯一字母
    let mut unique_chars = std::collections::HashSet::new();
    let mut first_chars = std::collections::HashSet::new();
    
    for part in &left_parts {
        if part.is_empty() {
            return None;
        }
        first_chars.insert(part.chars().next().unwrap());
        for c in part.chars() {
            if c.is_alphabetic() {
                unique_chars.insert(c);
            }
        }
    }
    
    first_chars.insert(right.chars().next().unwrap());
    for c in right.chars() {
        if c.is_alphabetic() {
            unique_chars.insert(c);
        }
    }
    
    let chars: Vec<char> = unique_chars.into_iter().collect();
    
    // 如果字母数超过10个，则无解
    if chars.len() > 10 {
        return None;
    }
    
    // 生成 0-9 的所有排列
    let digits: Vec<u8> = (0..10).collect();
    let permutations = permute(&digits, chars.len());
    
    // 尝试每个排列
    for perm in permutations {
        let mapping: HashMap<char, u8> = chars.iter().zip(perm.iter()).map(|(&c, &d)| (c, d)).collect();
        
        // 检查首字母是否为0
        if first_chars.iter().any(|&c| mapping[c] == 0) {
            continue;
        }
        
        // 验证等式
        if verify_equation(&left_parts, right, &mapping) {
            return Some(mapping);
        }
    }
    
    None
}

// 生成排列的辅助函数
fn permute(digits: &[u8], size: usize) -> Vec<Vec<u8>> {
    let mut result = Vec::new();
    let mut used = vec![false; digits.len()];
    let mut current = Vec::with_capacity(size);
    
    permute_helper(digits, size, &mut used, &mut current, &mut result);
    result
}

fn permute_helper(
    digits: &[u8],
    size: usize,
    used: &mut [bool],
    current: &mut Vec<u8>,
    result: &mut Vec<Vec<u8>>,
) {
    if current.len() == size {
        result.push(current.clone());
        return;
    }
    
    for i in 0..digits.len() {
        if !used[i] {
            used[i] = true;
            current.push(digits[i]);
            permute_helper(digits, size, used, current, result);
            current.pop();
            used[i] = false;
        }
    }
}

// 验证等式的辅助函数
fn verify_equation(left_parts: &[&str], right: &str, mapping: &HashMap<char, u8>) -> bool {
    let left_sum: u64 = left_parts
        .iter()
        .map(|part| word_to_number(part, mapping))
        .sum();
    
    let right_value = word_to_number(right, mapping);
    
    left_sum == right_value
}

// 将单词转换为数字
fn word_to_number(word: &str, mapping: &HashMap<char, u8>) -> u64 {
    let mut result = 0;
    for c in word.chars() {
        if let Some(&digit) = mapping.get(&c) {
            result = result * 10 + digit as u64;
        }
    }
    result
}

完整实现

考虑到性能优化，我们可以使用 itertools crate 来生成排列：

use std::collections::HashMap;

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
    // 解析输入
    let parts: Vec<&str> = input.split("==").collect();
    if parts.len() != 2 {
        return None;
    }
    
    let right = parts[1].trim();
    let left_parts: Vec<&str> = parts[0].split('+').map(|s| s.trim()).collect();
    
    // 收集所有唯一字母
    let mut unique_chars = std::collections::HashSet::new();
    let mut first_chars = std::collections::HashSet::new();
    
    for part in &left_parts {
        if part.is_empty() {
            return None;
        }
        first_chars.insert(part.chars().next().unwrap());
        for c in part.chars() {
            if c.is_alphabetic() {
                unique_chars.insert(c);
            }
        }
    }
    
    first_chars.insert(right.chars().next().unwrap());
    for c in right.chars() {
        if c.is_alphabetic() {
            unique_chars.insert(c);
        }
    }
    
    let chars: Vec<char> = unique_chars.into_iter().collect();
    
    // 如果字母数超过10个，则无解
    if chars.len() > 10 {
        return None;
    }
    
    // 生成 0-9 的所有排列
    let digits: Vec<u8> = (0..10).collect();
    let permutations = permute(&digits, chars.len());
    
    // 尝试每个排列
    for perm in permutations {
        let mapping: HashMap<char, u8> = chars.iter().zip(perm.iter()).map(|(&c, &d)| (c, d)).collect();
        
        // 检查首字母是否为0
        if first_chars.iter().any(|&c| mapping[c] == 0) {
            continue;
        }
        
        // 验证等式
        if verify_equation(&left_parts, right, &mapping) {
            return Some(mapping);
        }
    }
    
    None
}

// 生成排列的辅助函数
fn permute(digits: &[u8], size: usize) -> Vec<Vec<u8>> {
    let mut result = Vec::new();
    let mut used = vec![false; digits.len()];
    let mut current = Vec::with_capacity(size);
    
    permute_helper(digits, size, &mut used, &mut current, &mut result);
    result
}

fn permute_helper(
    digits: &[u8],
    size: usize,
    used: &mut [bool],
    current: &mut Vec<u8>,
    result: &mut Vec<Vec<u8>>,
) {
    if current.len() == size {
        result.push(current.clone());
        return;
    }
    
    for i in 0..digits.len() {
        if !used[i] {
            used[i] = true;
            current.push(digits[i]);
            permute_helper(digits, size, used, current, result);
            current.pop();
            used[i] = false;
        }
    }
}

// 验证等式的辅助函数
fn verify_equation(left_parts: &[&str], right: &str, mapping: &HashMap<char, u8>) -> bool {
    let left_sum: u64 = left_parts
        .iter()
        .map(|part| word_to_number(part, mapping))
        .sum();
    
    let right_value = word_to_number(right, mapping);
    
    left_sum == right_value
}

// 将单词转换为数字
fn word_to_number(word: &str, mapping: &HashMap<char, u8>) -> u64 {
    let mut result = 0;
    for c in word.chars() {
        if let Some(&digit) = mapping.get(&c) {
            result = result * 10 + digit as u64;
        }
    }
    result
}

测试用例分析

通过查看测试用例，我们可以更好地理解需求：

#[test]
fn test_with_three_letters() {
    assert_alphametic_solution_eq("I + BB == ILL", &[('I', 1), ('B', 9), ('L', 0)]);
}

最简单的用例，I(1) + BB(99) = ILL(100)。

#[test]
fn test_must_have_unique_value_for_each_letter() {
    let answer = alphametics::solve("A == B");
    assert_eq!(answer, None);
}

不同字母必须代表不同数字，所以 A==B 无解。

#[test]
fn test_leading_zero_solution_is_invalid() {
    let answer = alphametics::solve("ACA + DD == BD");
    assert_eq!(answer, None);
}

单词首字母不能为 0，所以 A 和 B 不能为 0。

#[test]
fn test_puzzle_with_eight_letters() {
    assert_alphametic_solution_eq(
        "SEND + MORE == MONEY",
        &[
            ('S', 9),
            ('E', 5),
            ('N', 6),
            ('D', 7),
            ('M', 1),
            ('O', 0),
            ('R', 8),
            ('Y', 2),
        ],
    );
}

经典的 SEND + MORE = MONEY 谜题。

性能优化

对于复杂的问题，我们可以考虑以下优化：

  1. 提前剪枝：在生成排列时就检查首字母不能为0的约束
  2. 约束传播：利用数学关系减少搜索空间
  3. 启发式搜索：优先尝试更有可能的数字分配

优化版本：

use std::collections::HashMap;
use std::collections::HashSet;

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
    // 解析输入
    let parts: Vec<&str> = input.split("==").collect();
    if parts.len() != 2 {
        return None;
    }
    
    let right = parts[1].trim();
    let left_parts: Vec<&str> = parts[0].split('+').map(|s| s.trim()).collect();
    
    // 收集所有唯一字母
    let mut unique_chars = HashSet::new();
    let mut first_chars = HashSet::new();
    
    for part in &left_parts {
        if part.is_empty() {
            return None;
        }
        first_chars.insert(part.chars().next().unwrap());
        for c in part.chars() {
            if c.is_alphabetic() {
                unique_chars.insert(c);
            }
        }
    }
    
    first_chars.insert(right.chars().next().unwrap());
    for c in right.chars() {
        if c.is_alphabetic() {
            unique_chars.insert(c);
        }
    }
    
    let chars: Vec<char> = unique_chars.into_iter().collect();
    
    // 如果字母数超过10个，则无解
    if chars.len() > 10 {
        return None;
    }
    
    // 转换为数组以提高性能
    let first_char_indices: Vec<usize> = first_chars.iter()
        .map(|c| chars.iter().position(|&x| x == *c).unwrap())
        .collect();
    
    // 生成 0-9 的所有排列
    let digits: Vec<u8> = (0..10).collect();
    let permutations = permute(&digits, chars.len());
    
    // 尝试每个排列
    for perm in permutations {
        // 检查首字母是否为0
        if first_char_indices.iter().any(|&i| perm[i] == 0) {
            continue;
        }
        
        let mapping: HashMap<char, u8> = chars.iter().zip(perm.iter()).map(|(&c, &d)| (c, d)).collect();
        
        // 验证等式
        if verify_equation(&left_parts, right, &mapping) {
            return Some(mapping);
        }
    }
    
    None
}

// 生成排列的辅助函数
fn permute(digits: &[u8], size: usize) -> Vec<Vec<u8>> {
    let mut result = Vec::new();
    let mut used = vec![false; digits.len()];
    let mut current = Vec::with_capacity(size);
    
    permute_helper(digits, size, &mut used, &mut current, &mut result);
    result
}

fn permute_helper(
    digits: &[u8],
    size: usize,
    used: &mut [bool],
    current: &mut Vec<u8>,
    result: &mut Vec<Vec<u8>>,
) {
    if current.len() == size {
        result.push(current.clone());
        return;
    }
    
    for i in 0..digits.len() {
        if !used[i] {
            used[i] = true;
            current.push(digits[i]);
            permute_helper(digits, size, used, current, result);
            current.pop();
            used[i] = false;
        }
    }
}

// 验证等式的辅助函数
fn verify_equation(left_parts: &[&str], right: &str, mapping: &HashMap<char, u8>) -> bool {
    let left_sum: u64 = left_parts
        .iter()
        .map(|part| word_to_number(part, mapping))
        .sum();
    
    let right_value = word_to_number(right, mapping);
    
    left_sum == right_value
}

// 将单词转换为数字
fn word_to_number(word: &str, mapping: &HashMap<char, u8>) -> u64 {
    let mut result = 0;
    for c in word.chars() {
        if let Some(&digit) = mapping.get(&c) {
            result = result * 10 + digit as u64;
        }
    }
    result
}

约束满足问题

字母算术是约束满足问题（Constraint Satisfaction Problem, CSP）的一个典型例子。CSP 包含：

  1. 变量：每个字母都是一个变量
  2. 域：每个变量的可能取值（0-9）
  3. 约束：
    • 所有变量取值必须不同
    • 首字母不能为 0
    • 等式必须成立

实际应用

约束满足问题在现实中有许多应用：

  1. 排班系统：为员工安排工作时间
  2. 资源配置：分配有限资源给不同任务
  3. 电路设计：布局和布线问题
  4. 人工智能：规划和推理系统

总结

通过 alphametics 练习，我们学到了：

  1. 约束满足问题：理解了 CSP 的基本概念和解决方法
  2. 排列生成：学会了如何生成和操作排列组合
  3. 字符串解析：掌握了复杂字符串的解析技术
  4. 算法优化：实践了剪枝和提前终止等优化技术
  5. 数据结构：熟练使用 HashMap 和 HashSet 等集合类型

这些技能在实际开发中非常有用，特别是在处理复杂的业务逻辑和优化计算密集型任务时。约束满足问题虽然看起来抽象，但它是一种强大的建模工具，可以帮助我们解决许多现实世界的问题。

# rust # 算法 # 开发语言
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

AI推理模型工程2026：从o3到DeepSeek-R1的工程化落地实践

推理链质量 > 最终答案正确性，过程才是价值所在推理模型代表的不仅是技术进步，更是AI应用从"快速响应"向"深度思考"转变的范式迁移。- o1：首代推理模型，引入"thinking tokens"概念- o3：重大升级，ARC-AGI得分超87%（人类均值85%）- o4-mini：轻量高效版，适合高频推理场景。## 什么是推理模型？- DeepSeek-R1：开源推理模型，AIME 2024满分

avatar AtomGit开源社区
cover

2026年AI简历生成工具测评：8款推荐帮你节省时间提升面试邀约率

avatar AtomGit开源社区
cover

GitHub 狂揽 1.1 万 Star！22 岁开发者逆向 【Claude Mythos】，撕开闭源 AI 的黑箱

avatar AtomGit开源社区