哪种算法最适合用Python解决像"Boggle"这样的单词搜索游戏

Question

我正在编写一个类似于Boggle的游戏,游戏玩家应该在随机字母组成的大字符串中找到单词.

例如,有五个数组,其中包含像这样的字符串.五行,每行六个字母:

AMSDNS
MASDOM
ASDAAS
DSMMMS
OAKSDO

因此,游戏的用户应该使用可用的字母制作单词,并考虑以下限制和规则:

• 它不可能重复相同的字母来表达一个字.我正在谈论骰子游戏中的"实体"字母.它不可能使用相同的骰子两次或更多来制作这个词.
• 它不可能"跳"任何一个字来形成一个字.制作单词的字母必须是连续的.
• 用户能够在没有任何限制的情况下向她想要的任何方向移动,而不是上述两个.所以它可以到达顶部,然后是底部,然后到右边,然后再到顶部,依此类推.所以寻找单词的动作可能会有些不稳定.

我想知道如何通过所有字符串来制作单词.要知道我将使用带有单词的txt文件的单词.

我不知道如何设计能够执行搜索的算法,特别是考虑找到单词和尊重限制所需的不稳定运动.

我已经实现了UX,掷骰子和填充棋盘游戏的逻辑,以及六个字母骰子的所有逻辑.

但这部分并不容易,我想看看你对这个有趣挑战的建议.

我在这个游戏中使用Python,因为我使用的语言代码和我最喜欢的语言.但是算法本身的解释或建议也应该很好,与语言无关.

Answer 1

基本算法很简单。

• 对于每个图块，执行以下操作。
  • 从空候选词开始，然后访问当前图块。
  • 按照以下步骤访问图块。
    • 将图块位置的字母添加到候选词中。
    • 候选词是已知词吗？如果是这样，请将其添加到找到的单词列表中。
    • 候选词是任何已知词的前缀吗？
      • 如果是，则对于尚未被访问以形成候选词的每个相邻图块，访问它（即，递归）。
      • 如果不是，则回溯（停止考虑该候选词的新图块）。

为了使问题顺利进行，当询问“这个单词是我的字典中任何单词的前缀吗”时，请考虑将您的字典表示为trie。尝试为单词和前缀提供快速查找时间。