每日算法 — 使用java实现灯谜：字符串约束满足与候选筛选算法

灯谜是中国传统文化中的文字益智游戏，通过谜面的描述、谐音、拆字等手法隐射谜底。本文将使用Java实现一个灯谜求解系统，重点讲解字符串约束满足（Constraint Satisfaction）、Trie前缀树匹配以及候选答案智能筛选的核心算法。

灯谜结构与算法抽象

一个灯谜由谜面、谜目（提示猜射范围）和谜底组成。从算法角度看，灯谜求解可以建模为：

1. 约束提取：从谜面解析出谜底的特征约束（字数、部首、谐音、类别等）
2. 候选空间构建：根据谜目确定搜索范围（如”打一字”、”打一成语”、”打一动物”）
3. 约束满足验证：逐一验证候选答案是否满足所有约束
4. 评分排序：对满足约束的候选进行相关性评分

核心算法设计

约束模型

/**
 * 灯谜约束类
 * 描述谜底必须满足的条件
 */
public class Constraint {

    public enum Type {
        LENGTH,           // 长度约束（字数）
        PREFIX,           // 前缀约束
        SUFFIX,           // 后缀约束
        CONTAINS,         // 包含特定字符
        CATEGORY,         // 类别约束（动物、植物、成语等）
        HOMOPHONE,        // 谐音约束
        RADICAL,          // 部首约束
        STRUCTURE         // 结构约束（拆字、组合等）
    }

    private final Type type;
    private final String value;
    private final int intValue;  // 用于数值型约束如长度

    public Constraint(Type type, String value) {
        this(type, value, -1);
    }

    public Constraint(Type type, int intValue) {
        this(type, null, intValue);
    }

    public Constraint(Type type, String value, int intValue) {
        this.type = type;
        this.value = value;
        this.intValue = intValue;
    }

    public boolean matches(String candidate) {
        switch (type) {
            case LENGTH:
                return candidate.length() == intValue;
            case PREFIX:
                return candidate.startsWith(value);
            case SUFFIX:
                return candidate.endsWith(value);
            case CONTAINS:
                return candidate.contains(value);
            case CATEGORY:
                // 类别验证由外部词典提供
                return true;
            case HOMOPHONE:
                // 谐音验证需要拼音库支持
                return true;
            case RADICAL:
                // 部首验证需要汉字拆解库
                return true;
            case STRUCTURE:
                // 结构约束由专门逻辑处理
                return true;
            default:
                return true;
        }
    }

    public Type getType() { return type; }
    public String getValue() { return value; }
    public int getIntValue() { return intValue; }
}

Trie前缀树词典

import java.util.*;

/**
 * Trie前缀树节点
 * 用于高效存储和检索灯谜候选答案
 */
class TrieNode {
    // 子节点映射：字符 -> 子节点
    Map<Character, TrieNode> children;
    // 是否为完整词条的结尾
    boolean isEndOfWord;
    // 存储该节点对应的完整词条列表（支持多词共享前缀）
    List<String> words;
    // 词条类别标签
    Set<String> categories;

    public TrieNode() {
        this.children = new HashMap<>();
        this.isEndOfWord = false;
        this.words = new ArrayList<>();
        this.categories = new HashSet<>();
    }
}

/**
 * Trie前缀树实现
 * 支持按前缀搜索、按长度筛选、按类别过滤
 */
public class RiddleDictionary {

    private final TrieNode root;
    private int size;  // 词条总数

    public RiddleDictionary() {
        this.root = new TrieNode();
        this.size = 0;
    }

    /**
     * 插入词条
     * 时间复杂度: O(m)，m为词条长度
     */
    public void insert(String word, String category) {
        if (word == null || word.isEmpty()) return;

        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current = current.children.computeIfAbsent(ch, k -> new TrieNode());
        }

        current.isEndOfWord = true;
        current.words.add(word);
        if (category != null) {
            current.categories.add(category);
        }
        size++;
    }

    /**
     * 按前缀搜索所有匹配词条
     * 时间复杂度: O(m + k)，m为前缀长度，k为结果数
     */
    public List<String> searchByPrefix(String prefix) {
        List<String> results = new ArrayList<>();
        if (prefix == null || prefix.isEmpty()) return results;

        TrieNode node = findNode(prefix);
        if (node == null) return results;

        collectAllWords(node, results);
        return results;
    }

    /**
     * 按前缀和长度联合搜索
     * 用于"X字开头且为N字"的约束
     */
    public List<String> searchByPrefixAndLength(String prefix, int length) {
        List<String> results = new ArrayList<>();
        TrieNode node = findNode(prefix);
        if (node == null) return results;

        collectWordsByLength(node, prefix.length(), length, prefix, results);
        return results;
    }

    /**
     * 按长度范围搜索（用于无前缀约束时）
     * 时间复杂度: O(n)，n为词典规模
     */
    public List<String> searchByLength(int length) {
        List<String> results = new ArrayList<>();
        collectWordsByLength(root, 0, length, "", results);
        return results;
    }

    /**
     * 辅助方法：定位前缀对应的节点
     */
    private TrieNode findNode(String prefix) {
        TrieNode current = root;
        for (char ch : prefix.toCharArray()) {
            TrieNode node = current.children.get(ch);
            if (node == null) return null;
            current = node;
        }
        return current;
    }

    /**
     * 辅助方法：收集节点下所有完整词条
     */
    private void collectAllWords(TrieNode node, List<String> results) {
        if (node.isEndOfWord) {
            results.addAll(node.words);
        }
        for (TrieNode child : node.children.values()) {
            collectAllWords(child, results);
        }
    }

    /**
     * 辅助方法：按精确长度收集词条（DFS）
     */
    private void collectWordsByLength(TrieNode node, int currentDepth, 
                                       int targetLength, String currentWord, 
                                       List<String> results) {
        if (currentDepth == targetLength) {
            if (node.isEndOfWord) {
                results.addAll(node.words);
            }
            return;
        }

        for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
            collectWordsByLength(entry.getValue(), currentDepth + 1, 
                                  targetLength, currentWord + entry.getKey(), results);
        }
    }

    public int size() {
        return size;
    }
}

灯谜求解引擎

/**
 * 灯谜求解引擎
 * 基于约束满足思想，通过多轮筛选缩小候选空间
 */
public class RiddleSolver {

    private final RiddleDictionary dictionary;

    public RiddleSolver(RiddleDictionary dictionary) {
        this.dictionary = dictionary;
    }

    /**
     * 求解灯谜
     * 核心流程：提取约束 -> 构建候选集 -> 逐条过滤 -> 评分排序
     * 
     * @param riddle 谜面对象
     * @return 按匹配度排序的候选答案列表
     */
    public List<Candidate> solve(Riddle riddle) {
        // 步骤1：提取约束
        List<Constraint> constraints = extractConstraints(riddle);
        System.out.println("[约束提取] 共 " + constraints.size() + " 条约束");
        for (Constraint c : constraints) {
            System.out.println("  - " + c.getType() + ": " + 
                              (c.getValue() != null ? c.getValue() : c.getIntValue()));
        }

        // 步骤2：根据最严格约束构建初始候选集
        List<String> candidates = buildInitialCandidates(constraints);
        System.out.println("[候选集] 初始大小: " + candidates.size());

        // 步骤3：逐条应用约束过滤
        for (Constraint constraint : constraints) {
            int before = candidates.size();
            candidates = filterByConstraint(candidates, constraint);
            System.out.println("[过滤] " + constraint.getType() + ": " + 
                              before + " -> " + candidates.size());
        }

        // 步骤4：评分排序
        List<Candidate> scored = scoreCandidates(candidates, riddle);
        scored.sort((a, b) -> Double.compare(b.score, a.score));

        return scored;
    }

    /**
     * 约束提取
     * 从谜面和谜目中解析显式和隐式约束
     */
    private List<Constraint> extractConstraints(Riddle riddle) {
        List<Constraint> constraints = new ArrayList<>();

        // 从谜目提取长度约束（如"打一字"=长度1，"打一成语"=通常4字）
        String category = riddle.getCategory();
        if (category != null) {
            constraints.add(new Constraint(Constraint.Type.CATEGORY, category));

            // 根据类别推断长度
            int inferredLength = inferLengthFromCategory(category);
            if (inferredLength > 0) {
                constraints.add(new Constraint(Constraint.Type.LENGTH, inferredLength));
            }
        }

        // 从谜面提取字符包含约束
        String surface = riddle.getSurface();
        if (surface != null) {
            // 检测谜面中是否暗示了部首或特定字符
            List<String> hintedChars = extractHintedChars(surface);
            for (String ch : hintedChars) {
                constraints.add(new Constraint(Constraint.Type.CONTAINS, ch));
            }
        }

        return constraints;
    }

    /**
     * 根据类别推断谜底长度
     */
    private int inferLengthFromCategory(String category) {
        switch (category) {
            case "字": return 1;
            case "成语": return 4;
            case "人名": return 2;  // 通常2-3字
            case "地名": return 2;  // 通常2-3字
            case "动物": return 2;  // 通常2字
            case "植物": return 2;  // 通常2字
            default: return -1;     // 未知，不添加长度约束
        }
    }

    /**
     * 从谜面提取暗示字符
     * 简化的启发式规则：提取谜面中的关键提示字
     */
    private List<String> extractHintedChars(String surface) {
        List<String> hints = new ArrayList<>();

        // 检测"X字"、"X旁"等模式
        String[] patterns = {"字", "旁", "头", "底", "边"};
        for (String pattern : patterns) {
            int idx = surface.indexOf(pattern);
            if (idx > 0) {
                hints.add(surface.substring(idx - 1, idx));
            }
        }

        return hints;
    }

    /**
     * 构建初始候选集
     * 优先使用最严格的约束（如前缀约束）减少搜索空间
     */
    private List<String> buildInitialCandidates(List<Constraint> constraints) {
        // 寻找最严格的约束来构建初始集
        Optional<Constraint> prefixConstraint = constraints.stream()
            .filter(c -> c.getType() == Constraint.Type.PREFIX)
            .findFirst();

        Optional<Constraint> lengthConstraint = constraints.stream()
            .filter(c -> c.getType() == Constraint.Type.LENGTH)
            .findFirst();

        if (prefixConstraint.isPresent()) {
            String prefix = prefixConstraint.get().getValue();
            if (lengthConstraint.isPresent()) {
                return dictionary.searchByPrefixAndLength(prefix, lengthConstraint.get().getIntValue());
            }
            return dictionary.searchByPrefix(prefix);
        }

        if (lengthConstraint.isPresent()) {
            return dictionary.searchByLength(lengthConstraint.get().getIntValue());
        }

        // 无有效约束时返回空（实际应返回全部或要求更明确的谜目）
        return new ArrayList<>();
    }

    /**
     * 应用单条约束过滤候选集
     */
    private List<String> filterByConstraint(List<String> candidates, Constraint constraint) {
        List<String> filtered = new ArrayList<>();
        for (String candidate : candidates) {
            if (constraint.matches(candidate)) {
                filtered.add(candidate);
            }
        }
        return filtered;
    }

    /**
     * 候选答案评分
     * 基于与谜面的相关性计算匹配分数
     */
    private List<Candidate> scoreCandidates(List<String> candidates, Riddle riddle) {
        List<Candidate> scored = new ArrayList<>();
        String surface = riddle.getSurface();

        for (String candidate : candidates) {
            double score = calculateScore(candidate, surface);
            scored.add(new Candidate(candidate, score));
        }

        return scored;
    }

    /**
     * 计算单个候选的匹配分数
     * 综合多种启发式特征
     */
    private double calculateScore(String candidate, String surface) {
        double score = 0.0;

        if (surface == null || surface.isEmpty()) {
            return score;
        }

        // 特征1：字符重叠度（谜底字出现在谜面中的比例）
        int overlap = 0;
        for (char ch : candidate.toCharArray()) {
            if (surface.indexOf(ch) >= 0) {
                overlap++;
            }
        }
        score += (overlap / (double) candidate.length()) * 30;

        // 特征2：长度匹配（默认基础分）
        score += 10;

        // 特征3：常见度（简化为词条长度相关，成语/俗语通常固定长度）
        if (candidate.length() == 4) {
            score += 5;  // 四字成语加分
        }

        return score;
    }

    /**
     * 灯谜数据类
     */
    public static class Riddle {
        private String surface;    // 谜面
        private String category;   // 谜目（如"字"、"成语"、"动物"）
        private String hint;       // 额外提示

        public Riddle(String surface, String category) {
            this.surface = surface;
            this.category = category;
        }

        public String getSurface() { return surface; }
        public String getCategory() { return category; }
        public String getHint() { return hint; }
    }

    /**
     * 候选答案评分结果
     */
    public static class Candidate {
        public final String answer;
        public final double score;

        public Candidate(String answer, double score) {
            this.answer = answer;
            this.score = score;
        }

        @Override
        public String toString() {
            return String.format("%s (%.1f)", answer, score);
        }
    }
}

演示程序

/**
 * 灯谜系统演示
 */
public class RiddleDemo {

    public static void main(String[] args) {
        // 构建词典
        RiddleDictionary dict = new RiddleDictionary();

        // 插入常用字
        String[] chars = {"日", "月", "明", "山", "水", "火", "木", "林", "森", "人", 
                          "大", "天", "王", "玉", "主", "石", "口", "回", "品", "晶"};
        for (String c : chars) {
            dict.insert(c, "字");
        }

        // 插入常见成语
        String[] idioms = {"一马当先", "二话不说", "三心二意", "四面楚歌", "五光十色",
                           "六神无主", "七上八下", "八面玲珑", "九牛一毛", "十全十美",
                           "画蛇添足", "守株待兔", "亡羊补牢", "掩耳盗铃", "刻舟求剑"};
        for (String idiom : idioms) {
            dict.insert(idiom, "成语");
        }

        System.out.println("词典加载完成，共 " + dict.size() + " 条词条\n");

        // 创建求解器
        RiddleSolver solver = new RiddleSolver(dict);

        // 测试灯谜1：打一字
        RiddleSolver.Riddle riddle1 = new RiddleSolver.Riddle(
            "太阳挂在树梢上", "字"
        );
        System.out.println("灯谜1：" + riddle1.getSurface() + " （" + riddle1.getCategory() + "）");
        List<RiddleSolver.Candidate> answers1 = solver.solve(riddle1);
        System.out.println("候选答案: " + answers1.subList(0, Math.min(5, answers1.size())));
        System.out.println();

        // 测试灯谜2：打一成语
        RiddleSolver.Riddle riddle2 = new RiddleSolver.Riddle(
            "画蛇添足反类犬", "成语"
        );
        System.out.println("灯谜2：" + riddle2.getSurface() + " （" + riddle2.getCategory() + "）");
        List<RiddleSolver.Candidate> answers2 = solver.solve(riddle2);
        System.out.println("候选答案: " + answers2.subList(0, Math.min(5, answers2.size())));
    }
}

复杂度分析

扩展方向

1. 汉字拆解库：引入部首、笔画、结构信息，支持”拆字”类灯谜
2. 拼音谐音匹配：集成拼音库，处理谐音类谜语（如”羊”谐音”洋”）
3. NLP语义分析：使用词向量计算谜面与谜底的语义相似度
4. 用户反馈学习：记录猜谜历史，通过机器学习优化评分模型

总结

灯谜求解系统将传统文化游戏转化为约束满足问题，通过Trie前缀树实现高效的候选空间检索，利用多轮约束过滤逐步缩小解空间。虽然真实灯谜涉及复杂的语言学和文化遗产知识，但本文实现的框架展示了如何将算法思维应用于趣味问题的求解，为读者提供了字符串处理和搜索算法的实践案例。