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

Question

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

例如，有五个数组，其中的字符串如下所示。五行，每行六个字母：

AMSDNS
MASDOM
ASDAAS
DSMMMS
OAKSDO

因此，游戏的用户应该在考虑到以下限制和规则的情况下，使用字母的单词：

• 不可能重复同一个字母来造字。我说的是“物理”字母，在游戏中那是一个骰子。不可能用同一个骰子两次或两次以上来造出这个词。
• 不可能“跳转”任何字母来造字。构成这个词的字母必须是连续的。
• 用户可以在不受上述两个限制的情况下朝任何方向移动。所以有可能是先上，再下，再右，再上，等等。因此，寻找单词的动作可能有些不稳定。

我想知道如何通过所有的字符串来造字。要知道我要用一个带单词的文本文件。

我不知道如何设计一个能够执行搜索的算法，特别是考虑到寻找单词所需的不稳定移动，同时也要尊重这些限制。

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

但这一部分并不容易，我想听听你对这一有趣挑战的建议。

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

Answer 1

你可能会发现一个Trie有用-将所有字典单词放入一个Trie中，然后从复杂的网格中进行另一个Trie，只要你匹配字典Trie。

即字典trie：

S->T->A->C->K = stack
      \->R->K = stark
         \->T = start

网格：（简化）

STARKX 
XXXTXX 
XXXXXX

网格trie:（仅从S开始显示-也从A开始表示艺术等）

S->X (no matches in dict Trie, so it stops) 
\->T->X
   \->A-R->K (match)
      | |->T (match)
      | \->X  
      \->C->K (match)
         \->X    

你可以想象你尝试用this这样的图形。

Answer 2

基本算法很简单。

• 对于每个平铺，请执行以下操作。
  • 从一个空的候选词开始，然后访问当前互动程序。
  • 按照以下步骤访问磁贴。
    • 将平铺位置的字母添加到候选单词中。
    • 候选词是已知词吗？如果是，请将其添加到查找到的单词列表中。
    • 候选词是已知词的前缀吗？
      • 如果是，对于尚未访问以形成候选词的每个相邻平铺，请访问它（即递归）。
      • 如果没有，则返回（停止考虑此候选词的新平铺）。

当你问“这个词是我字典里任何一个词的前缀”时，为了让事情顺利进行，可以考虑把你的字典表示成trie。尝试为单词和前缀提供快速查找时间。