数独生成 - 谜题自动生成算法的设计思想
·约 1 分钟阅读
优质数独谜题的自动生成不是简单地随机放置数字就能实现的。本文讲解唯一解的保证、难度控制、美观提示分布的实现方法。
生成的 3 个步骤
数独谜题的生成分 3 个步骤:(1) 随机生成有效的完成盘面。(2) 逐个移除格子中的数字,验证移除后仍保持唯一解。(3) 分析移除后谜题的难度,确认是否符合目标难度。步骤 2 和 3 是决定品质的核心部分,计算成本的大部分集中于此。
唯一解的保证
作为谜题成立的前提是解必须唯一。每次移除格子后,都需要验证剩余谜题是否拥有唯一解。验证方法是使用求解器计算解的数量。一旦发现 2 个以上的解,即判定为「非唯一解」,撤销该格子的移除。这种验证计算成本较高,但对保证谜题品质不可或缺。
难度的控制
难度通过解题所需技巧的复杂程度来定义。对生成的谜题模拟人类解法,分析需要哪些技巧。仅用显性单数就能解出则为 Easy,需要隐性单数则为 Medium,需要数对则为 Hard,需要 X-Wing 则为 Master。如果与目标难度不符,则丢弃谜题重新生成。
种子值实现可重现性
要实现「所有用户解同一道谜题」的每日挑战功能,需要给随机数生成器提供种子值以确保可重现性。从日期计算种子值,相同种子始终生成相同谜题。这样无需在服务器保存谜题,客户端即可重现相同谜题。