algorithm - 如何生成包含大量单词的字母网格

Question

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

Boggle 是一种游戏，您可以掷带有字母的骰子，它们被放置在 4x4 的网格中。示例:

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

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

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

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

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

有很多 similar questions但 AFAICT 不是这个确切的问题。这显然是对游戏“Scramble with Friends”的引用。

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

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

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

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

想法？

Answer 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

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

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