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

algorithm java computer-science linguistics

2022-09-04 03:05:53

我正在制作一个像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个字母单词，而没有机会找到更大的单词。

例如：

你可以从字母表中随机选择新的字母。这不能很好地工作。
同样，我发现随机选择，但使用Scrabble的字母频率效果不佳。我认为这在拼字游戏中效果更好，因为您对使用字母的顺序的限制较少。
我尝试使用一组列表，每个列表代表Boggle游戏中的一个骰子，每个字母将从随机骰子侧选择（我也想知道我是否可以在产品中合法地使用这些数据）。我没有注意到这很有效。我想Boggle骰子的面是以某种合理的方式选择的，但我找不到这是怎么做到的。

我考虑过的一些想法：

制作一个表格，列出字母对在字典中一起出现的频率。为了便于论证，假设E在30%的情况下出现在A旁边。在选择新字母时，我会根据该字母在网格上随机选择的相邻字母旁边出现的频率随机选择一个字母。例如，如果相邻字母是 E，则新字母在 30% 的时间内为“A”。这应该意味着有很多像样的对可以在地图上使用。我也许可以通过制作一个字母在另外两个字母之间出现的概率表来改善这一点。
以某种方式搜索哪些单词可以在当前网格上拼写，将新字母作为通配符。然后，我将通配符替换为允许拼写最大单词的字母。但是，我不确定您将如何有效地做到这一点。

任何其他想法都值得赞赏。我想知道是否有一种常见的方法来解决这个问题，以及其他文字游戏使用什么。

编辑：感谢您到目前为止的精彩回答！我忘了提一下，如果可能的话，我真的瞄准了低内存/ CPU要求，我可能会使用SOWPODS字典（约250，000），我的网格将能够6 x 6。

答案 1

这是一个简单的方法：

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

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

答案 2

字母对方法的一个小变化：在长单词中使用字母对的频率 - 比如6个字母或更长 - 因为这是你的目标。您还可以开发一个包含所有相邻字母的权重，而不仅仅是随机字母。