java - 为允许拼写多个单词的单词搜索游戏选择随机字母的算法

Question

我正在制作 boggle -喜欢文字游戏。给用户一个这样的字母网格:

O V Z W X
S T A C K
Y R F L Q

用户使用任何相邻的字母链选择一个单词，例如中间一行的单词“STACK”。然后使用的字母由机器替换，例如(小写的新字母):

O V Z W X
z e x o p
Y R F L Q

请注意，您现在可以使用新字母拼写“OVeRFLoW”。我的问题是:我可以使用什么算法来选择新字母，使用户可以拼写的长单词数量最大化？我希望游戏有趣并涉及拼写，例如有时是 6 个字母的单词，但如果您选择了错误的字母，游戏会涉及用户仅拼写 3 个字母的单词而没有机会找到更大的单词。

例如:

• 您可以从字母表中随机选择新字母。这效果不佳。

• 同样，我发现随机选择但使用拼字游戏中的字母频率效果不佳。我认为这在拼字游戏中效果更好，因为您对使用字母的顺序没有那么大的限制。

• 我尝试了一组列表，每个列表代表 Boggle 游戏中的一个骰子，每个字母都是从随机骰子面挑选的(我也想知道我是否可以在产品中合法使用这些数据).我没有注意到这个效果很好。我想 Boggle 骰子的面是以某种明智的方式选择的，但我不知道这是怎么做到的。

我考虑过的一些想法:

• 制作一个表格，列出字典中字母对一起出现的频率。为了争论起见，假设 E 在 30% 的时间里出现在 A 旁边。 When picking a new letter, I would randomly pick a letter based on the frequency of this letter occurring next to a randomly chosen adjacent letter on the grid.例如，如果相邻字母是 E，则新字母在 30% 的情况下会是“A”。这应该意味着有很多像样的配对散布在 map 上。我可以通过制作一个字母出现在其他两个字母之间的概率表来改进这一点。

• 以某种方式搜索当前网格上可以拼写的单词，将新字母作为通配符。然后我会用允许拼写最大单词的字母替换通配符。不过，我不确定您将如何有效地做到这一点。

任何其他想法表示赞赏。想知道有没有什么通用的方法可以解决这个问题还有其他的文字游戏用的是什么。

编辑:感谢您迄今为止的出色回答!我忘了说，如果可能的话，我的目标是降低内存/CPU 要求，我可能会使用 SOWPODS 词典(大约 250,000)，我的网格将能够达到 6 x 6。

Answer 1

这是一个简单的方法:

使用玩家将使用的相同单词列表为游戏编写一个快速求解器。随机生成 100 个不同的可能板(在这里使用字母频率可能是个好主意，但不是必需的)。对于每个板计算所有可以生成的单词，并根据找到的单词数或按单词长度加权的计数(即找到的所有单词的单词长度的总和)对板进行评分。然后从 100 种可能性中选出最好的计分板，然后将其交给玩家。

此外，您可以设置不同的分数阈值，而不是总是选择得分最高的棋盘(即最简单的棋盘)，让游戏对专家来说更加困难。