我如何确保每个每日 Q-less 谜题都是可解的

这是一篇关于Daily Q-less的技术概述,它是 Q-less 单词拼图游戏的网络改编版。

主要观点

  • 介绍 Q-less 游戏规则,如 12 个字母、组成英语单词、单词相连等,给出示例解决方案。
  • 指出 Q-less 骰子游戏的挫折在于有时掷出的字母无有效解,而在 Daily Q-less 中不想自己预先求解。
  • 阐述计算机程序求解 Q-less 问题的困难,如分支数量多、合法性检查复杂等,估计需数百万分支和数千次合法性检查。
  • 提出更好的求解方法,将求解器分为两阶段,先计算合法网格形状,再用该形状集求解。
  • 说明求解器的其他好处,可量化roll的难度,根据检查网格数将roll分配到一周的不同天数,难度逐渐增加。

关键信息和重要细节

  • 求解过程:先找词,再找相交词,检查剩余字母是否合适,不行则回溯;第一阶段忽略字母计算合法网格形状,减少分支和开销。
  • 优化方法:放置字母时注意避免 2 字母片段,使用优化算法减少重复网格;按解决方案可能性/平均分支数排序网格以提高性能。
  • 难度量化:根据找到十个不同解决方案所需检查的网格数将 roll 分配到周一至周日,难度逐渐增加;周四和周日允许任何 12 个字母的组合。
  • 代码相关:Daily Q-less 及其他游戏代码开源,可在GitHub查看,文中讨论的文件为here
阅读 10
0 条评论