数独生成 - 谜题自动生成算法的设计思想

数独谜题的生成分 3 个步骤：(1) 随机生成有效的完成盘面。(2) 逐个移除格子中的数字，验证移除后仍保持唯一解。(3) 分析移除后谜题的难度，确认是否符合目标难度。步骤 2 和 3 是决定品质的核心部分，计算成本的大部分集中于此。

作为谜题成立的前提是解必须唯一。每次移除格子后，都需要验证剩余谜题是否拥有唯一解。验证方法是使用求解器计算解的数量。一旦发现 2 个以上的解，即判定为「非唯一解」，撤销该格子的移除。这种验证计算成本较高，但对保证谜题品质不可或缺。

难度通过解题所需技巧的复杂程度来定义。对生成的谜题模拟人类解法，分析需要哪些技巧。仅用显性单数就能解出则为 Easy，需要隐性单数则为 Medium，需要数对则为 Hard，需要 X-Wing 则为 Master。如果与目标难度不符，则丢弃谜题重新生成。

要实现「所有用户解同一道谜题」的每日挑战功能，需要给随机数生成器提供种子值以确保可重现性。从日期计算种子值，相同种子始终生成相同谜题。这样无需在服务器保存谜题，客户端即可重现相同谜题。

生成中最棘手的是难度评估。难度通常以「所需技巧的最高难度」来定义，但同一谜题的体感难度会随解题者的路径而变化。而且这一刻度并非线性：仅把所需技巧提高一级，体感难度就可能骤增。实现上会用模拟人类解法的求解器，依次判断谜题能否仅凭显性唯一数解出、是否需要隐性唯一数等，并在首次卡住的阶段确定难度。然而这一判断取决于求解器所实现的技巧范围，因此若缺少某种技巧，可能高估难度。要让难度标注保持一致，求解器对技巧的覆盖必须足够全面。

生成的计算开销大多花在验证唯一性上。朴素的穷举很慢，因此实用的生成器会采用若干优化。引入约束传播、优先尝试候选最少的格子，可大幅减少无谓的分支。计数解的求解器会设定为「一旦找到第二个解就立即中止」，而不是枚举所有解。再使用 Dancing Links (DLX) 这类面向精确覆盖问题的算法，可进一步提升回溯效率。生成是较重的处理，但若只为每日挑战生成一道题，即便在客户端也能以足够的速度运行。

生成器应当追求的，不只是拥有唯一解，而是解起来令人愉快的好题。好题的条件包括：能仅凭逻辑解到最后、不强迫漫无目的的试错，以及所标注的难度与实际手感相符。为满足这些条件，生成之后会用求解器重演解题路径，以验证是否存在需要猜测的环节、能否用预期的技巧解出。不满足条件的谜题会被丢弃并重新生成，因此目标难度越高，生成所需的尝试次数越多。相比量产，更重视逐题质量的设计，最终会提升游玩者的满意度。仅以提示数量来判定难度是一种误解：有些提示少的题目却很顺畅，有些提示多的题目反而需要高级技巧。