
研究者用精确覆盖算法枚举迷你填字游戏全部解法
来源标题:Generating Mini-Crosswords
一位研究者提出将迷你填字游戏解法构造转化为带约束的广义精确覆盖问题,并利用 Knuth 的 Dancing Links (DLX) 算法求解。此前《College Mathematics Journal》的文章曾用 Metropolis-Hastings 算法随机采样此类谜题。该思路旨在枚举给定网格尺寸和词典下的所有可能谜题,而非逐个随机采样。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
《纽约时报》会发布“迷你填字游戏”,也就是在相对较小的网格(通常是 5×5)上、不含任何黑格的填字游戏,因此网格的每一行和每一列都必须拼出一个单词。下图展示了一个此类谜题的解答示例。
制作这些谜题有多难?本文的灵感来自最近发表在《College Mathematics Journal》上的一篇文章(见下方参考文献 (1)),该文章探讨了这个问题,并描述了一种使用 Metropolis-Hastings 算法对谜题实例进行随机采样的方法。
但与其一次只随机采样一个谜题,我们能不能真正枚举出所有可能的谜题呢?具体来说,我的想法是把寻找填字游戏解的问题,归约为在精心构造的约束下寻找(广义)精确覆盖的问题。这会很方便,因为我们已经有了用 Knuth 的 Dancing Links (DLX) 算法求解精确覆盖问题的代码(类似的过往练习见这里和这里)。
更精确地陈述这个问题:给定一个表示网格大小的正整数(上例中为 ),以及一个词典,其中每个单词的长度为 ,字母表为 ,我们必须构造一个精确覆盖问题,使其解对应于在所有网格位置中填入字母,使得每一行和每一列都拼出 中的一个单词。
为此,我们构造一个 0-1 矩阵,其行数 ,每一行对应于将词典中的某个单词按“横向”(放在谜题的某一行中)或“纵向”(放在谜题的某一列中)放置。一个解将由矩阵行的一个子集组成: 个“横向”单词,谜题每一行一个;以及 个“纵向”单词,每一列一个;并且每一对相交的单词都在适当的公共字母处相交。
为了表示这些约束,我们最初需要矩阵中的 列(其中 ),每一列由一个元组(谜题行 ,谜题列 ,字母 ,横向或纵向)索引。对于给定的矩阵行——它表示将一个具有字母 的单词放置在谜题网格中某个特定位置和方向上——我们把对应于该单词将被放置在谜题中的不同网格位置的那些列设为 1……其中,对于每个字母 ,当且仅当以下任一条件满足时,我们把“横向”列设为 1:
如果这两个条件都不满足,我们就改为把“纵向”列设为 1。下面的 Python 代码会生成所得稀疏矩阵的 (行, 列) 对的数量和列表。
letters = 'abcdefghijklmnopqrstuvwxyz' m = len(words) n = len(words[0]) print(m * n * 2 * (n * 26), file=file) b = [True, False] for row, ((w, word), k, across) in enumerate( product(enumerate(words), range(n), b)): for col, (i, j, letter, horiz) in enumerate( product(range(n), range(n), letters, b)): if ((i if across else j) == k and (word[j if across else i] == letter) == (across == horiz)): print(row, col, file=file)
不过,我们还没完全做完。尽管期望的最终结果是每一行和每一列都含有不同单词的填字游戏,如下方 (a) 中所示的 6×6 解,但正如 Howard 在 CMJ 文章中所观察到的,有许多使用同一个单词不止一次的合法解,包括对称的“单词方阵”这种极端情况,如下方 (b) 所示。
(a) 6×6 迷你填字游戏,其中每一行和每一列的单词都是唯一的。(b) 6×6“单词方阵”,即一个对称网格,其中每一行和对应的列包含相同的单词。
我们可以通过向 0-1 矩阵添加“可选”列来消除这种重复,词典中的每个单词对应一列,然后求解所得的广义精确覆盖问题,使得每个单词在一个解中最多使用一次。
所有源代码都可以在这里以及 GitHub 上找到。我最初的测试使用了 Howard 论文中讨论的 4×4 情形,以及他那包含 1826 个单词的词典。他描述了一个通过使用马尔可夫链蒙特卡洛方法重复采样来估计可能谜题总数的方法:“我们估计大约有 73,000–74,000 个不同的谜题,每个谜题都没有重复的单词。”这相当准确;事实证明,恰好有 74,339 个(每个谜题在广义精确覆盖问题中贡献两对对称解,总共 148,678 个解)。
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。