arXiv:2510.02855cs.CLcs.AI2025-10被引 2

用约束满足方法优化猜字游戏,准确率超99%且更快。

Constraint Satisfaction Approaches to Wordle: Novel Heuristics and Cross-Lexicon Validation

  • 基于约束传播计算信息增益,比传统方法更精准
  • 平均3.54次猜中,比基准快46%,抗干扰能力更强
  • 跨语言验证有效,适合研究算法鲁棒性与逻辑推理

Wordle为约束满足问题(CSP)求解提供了算法丰富的测试平台。现有求解器依赖信息熵最大化或词频启发式,缺乏形式化约束处理。本文首次提出完整的Wordle CSP建模,并设计新型约束感知求解策略。提出CSP-Aware Entropy,基于约束传播后的候选集计算信息增益;构建融合贝叶斯词频先验与逻辑约束的概率CSP框架。在2,315个英文单词上,该方法实现3.54次平均猜测、99.9%成功率,相比前向检查显著提升1.7%(t=-4.82, p<0.001, Cohen's d=0.07),且每轮猜测速度加快46%(12.9ms vs 23.7ms)。在10%噪声下仍保持5.3个百分点优势(29.0% vs 23.7%, p=0.041),概率CSP在0-20%噪声下均达100%成功率。对500个西班牙语词的跨语言验证显示88%成功率,无需语言调优,验证了核心CSP原理的跨语言迁移性,尽管存在11.2个百分点的语言差异(p<0.001, Fisher's exact test)。开源实现含34个单元测试,代码覆盖率91%,为CSP研究提供可复现基础设施。本工作通过形式化约束处理、约束感知启发式、概率-逻辑融合、鲁棒性分析与跨语言验证,确立新性能基准,证明系统性约束满足方法优于经典信息理论与学习基方法。

原文摘要 · Abstract (English)

Wordle presents an algorithmically rich testbed for constraint satisfaction problem (CSP) solving. While existing solvers rely on information-theoretic entropy maximization or frequency-based heuristics without formal constraint treatment, we present the first comprehensive CSP formulation of Wordle with novel constraint-aware solving strategies. We introduce CSP-Aware Entropy, computing information gain after constraint propagation rather than on raw candidate sets, and a Probabilistic CSP framework integrating Bayesian word-frequency priors with logical constraints. Through evaluation on 2,315 English words, CSP-Aware Entropy achieves 3.54 average guesses with 99.9% success rate, a statistically significant 1.7% improvement over Forward Checking (t=-4.82, p<0.001, Cohen's d=0.07) with 46% faster runtime (12.9ms versus 23.7ms per guess). Under 10% noise, CSP-aware approaches maintain 5.3 percentage point advantages (29.0% versus 23.7%, p=0.041), while Probabilistic CSP achieves 100% success across all noise levels (0-20%) through constraint recovery mechanisms. Cross-lexicon validation on 500 Spanish words demonstrates 88% success with zero language-specific tuning, validating that core CSP principles transfer across languages despite an 11.2 percentage point gap from linguistic differences (p<0.001, Fisher's exact test). Our open-source implementation with 34 unit tests achieving 91% code coverage provides reproducible infrastructure for CSP research. The combination of formal CSP treatment, constraint-aware heuristics, probabilistic-logical integration, robustness analysis, and cross-lexicon validation establishes new performance benchmarks demonstrating that principled constraint satisfaction techniques outperform classical information-theoretic and learning-based approaches for structured puzzle-solving domains.

约束满足算法优化多语言游戏求解

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。