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

Question

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

比如有五个数组，里面是这样的字符串。五行，每行由六个字母组成:

AMSDNS
MASDOM
ASDAAS
DSMMMS
OAKSDO

因此，游戏的用户在使用可用字母造词时应牢记以下限制和规则:

• 不可能通过重复同一个字母来组成单词。我在谈论“物理”字母，在游戏中是一个骰子。不可能使用同一个骰子两次或更多次来组成单词。
• 不可能“跳转”任何字母来组成单词。组成单词的字母必须是连续的。
• 除了上面提到的两个之外，用户可以在她想要的任何方向上移动而不受任何限制。所以可以先到顶部，然后到底部，然后到右边，然后再到顶部，依此类推。因此，寻找单词的 Action 可能会有些不稳定。

我想知道如何遍历所有字符串来造词。要知道单词，我将使用带有单词的 txt 文件。

我不知道如何设计一个能够执行搜索的算法，特别是考虑到查找单词所需的不稳定运动并遵守限制。

我已经实现了用户体验、掷骰子和填满棋盘游戏的逻辑，以及六个字母骰子的所有逻辑。

但这部分并不容易，我想阅读您对这个有趣挑战的建议。

我在这款游戏中使用 Python，因为它是我用来编写代码的语言，也是我最喜欢的语言。但是算法本身的解释或建议也应该很好，独立于语言。

Answer 1

基本算法很简单。

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

为了在询问“这个词是我词典中任何词的前缀”这个问题时顺利进行，考虑将您的词典表示为 trie . Tries 可以快速查找单词和前缀。