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

Question

这个问题基本上是“如何生成一个有很多5个或更多字母单词的好的 'Boggle' 游戏网格”的问题。

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”、“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"。

有很多{{link1：相似的问题}}，但据我所知没有这个确切的问题。这显然是对游戏“Scramble with Friends”的参考。

第一个解决方案是随机选择字母，但问题在于如果您意外选择了所有辅音字母，则不会有单词。添加一些随机元音字母不足以保证一个好的单词集。您可能只会得到1到4个字母的单词，而一个好的算法将选择一个具有> 200个单词的字母集，其中许多单词> 7个字母。

我可以接受任何算法。显然，我可以编写代码来强制解决方案，找到每个可能的网格，然后按具有最多单词的网格进行排序，但是这个简单的解决方案需要运行很长时间。

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

可能需要对字典进行预处理才能找到单词的共同部分，例如所有以“ing”、“ers”、“ght”、“tion”或“land”结尾的单词。或者将它们组织成共享字母的图表。也许会给某些字母集合加权，使得“ing”或“ers”经常被插入。

有什么想法吗？

- gman

---

我建议找到一个字母频率表，并基于加权随机化使用它。也许生成一个网格，检查它，如果它不够好，尝试一个新的。 - Kevin

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

即使您不通过暴力破解方式检查，仍然有可能出现 错误 的网格，但是通过简单随机生成的网格返回的错误网格数量可以大幅减少。

或者，随机生成网格并根据需要进行暴力破解以选择好的网格。但是，请在后台进行此操作（在需要之前的几天或几周）。然后存储一堆好的网格，并在需要时随机选择一个（并将其从列表中划掉，以免再次看到它）。

- Penguino

Answer 2

Boggle的工作原理是有六面骰子，每个面上都有特定的字母。这些骰子随机分配到16个方格中并进行滚动。常见字母在骰子的更多面上出现。搜索一下 - 你可能能够获得完全相同的骰子组合。

- disatisfieddinosaur

---

我想Hasbro不会批准使用他们的精确骰子，最好自己制作一套。 - Kevin

Answer 3

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

2. 从四个中心方格中随机选择一个开始。

3. 按单个字母频率加权随机选择一个字母填入该方格。

4. 递归执行：

   4.1. 随机选择一个空连接方格。

   4.2. 按照任何相邻填充方格的双字母频率平均值和任何相邻空方格的单字母频率的组合（平均值）加权随机选择一个字母填入该方格。

完成！

P.S. 你也可以尝试在4.2中添加全局字母降级，基于它在网格中出现的当前次数。

- Paddy3118