6

问题基本上是“我如何为游戏'Boggle'生成一个有很多单词的好网格”，其中好被定义为有很多5个或更多字母的单词。

Boggle 是一款游戏，您可以在其中掷骰子，上面有字母，它们被放置在 4x4 网格中。例子：

H S A V
E N I S
K R G I
S O L A

单词可以通过水平、垂直或对角连接字母来组成。在上面的良好示例网格中，您可以根据使用的字典创建单词“VANISHERS”、“VANISHER”、“KNAVISH”、“ALIGNERS”、“SAVINGS”、“SINKERS”和大约 271 个其他单词，例如“AS” 、“我”、“空气”、“SIN”、“IS”等...

作为一个不好的例子，这个网格

O V W C
T K Z O
Y N J H
D E I E

只有约 44 个单词，其中只有 2 个大于 4 个字母。“TYNED”和“HINKY”。

有很多类似的问题，但 AFAICT 不是这个确切的问题。这显然是对《与朋友争夺战》游戏的参考。

第一个解决方案，随机选择字母，如果你不小心选择了所有的辅音，就会没有单词。添加几个随机元音并不足以保证一组好的单词。您可能只会得到 1 到 4 个字母的单词，而一个好的算法会选择一组具有 > 200 个单词的字母，其中许多单词 > 7 个字母。

我对任何算法持开放态度。显然，我可以编写代码来蛮力解决方案找到每个可能的网格，然后按单词最多的网格对它们进行排序，但是这个简单的解决方案将永远运行。

我可以想象各种启发式方法，例如选择一个长单词（8-16 个字母），将这些字母随机放入网格中，但实际上仍然可以生成单词，然后填充剩余的空格。我怀疑这也不足以保证一组好的单词，尽管我还没有尝试过。

该解决方案可能需要预处理字典以了解单词的常见部分。例如所有以“ing”或“ers”或“ght”或“tion”或“land”结尾的单词。或者以某种方式将它们组织成共享字母的图表。也许对某些字母集进行加权，因此经常插入“ing”或“ers”。

想法？

4

3 回答 3

1

缺少蛮力搜索建议，可能无法保证您拥有良好的网格。如果您使用在 Boggle 骰子上找到的字母频率，那么您将获得“平均”网格（就像您掷骰子一样）。您可以通过添加额外的启发式或过滤器来改进这一点，例如：

 ensure that (almost) every consonant is 'in-reach-of' a vowel
 ensure 'Q' is 'in-reach-of' a 'U'
 ensure the ratio of vowels to consonants is within a set range
 ensure the number of rare consonants is not too large
 etc

那么你可以

 set letters using weighted letter frequency
 change (swap/replace) letters not meeting your heuristics

除非您通过蛮力检查，否则坏网格仍然有可能通过，但是您可以从简单随机生成的网格返回的那些中大幅减少坏网格的数量。

或者，生成随机网格并根据需要执行蛮力工作以选择好的网格。但在后台执行此操作（需要几天或几周前）。然后存储一堆好的网格，并在需要时根据需要随机选择一个（并将其从列表中划掉，这样你就不会再看到它了）。

于 2013-08-11T23:35:15.380 回答
0

  1. 从字典中计算统计字母频率和字母对频率。

  2. 从随机选择四个中心方块之一开始

  3. 为按单个字母频率加权的正方形随机选择一个字母。

  4. 递归：

    4.1。随机选择所有空的连通方格之一。

    4.2. 随机选择一个由任何相连的实心方块的双字母频率和任何相连的空方块的单字母频率的组合加权的字母（平均值）。

瞧！

PS 您可能还想尝试根据当前在网格中出现的次数将全局字母降额添加到 4.2。

于 2013-08-12T05:34:10.297 回答
0

Boggle 的工作方式是有六面模具，侧面带有某些字母。这些骰子被随机分配到 16 个方格，然后滚动。常见的字母出现在骰子的更多面上。四处搜索 - 你也许能够得到准确的骰子。

于 2013-08-11T23:17:50.640 回答