6

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

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

AMSDNS
MASDOM
ASDAAS
DSMMMS
OAKSDO

因此，游戏的用户应该使用可用的字母来制作单词，并牢记以下限制和规则：

  • 不可能重复同一个字母来造一个词。我说的是游戏中的“物理”字母，即骰子。它不可能使用相同的骰子两次或更多次来制作单词。
  • 不可能“跳”任何字母来造词。组成单词的字母必须是连续的。
  • 用户可以向她想要的任何方向移动，而不受上述两个限制。所以它有可能先到顶部，然后到底部，然后到右边，然后再到顶部，依此类推。所以寻找单词的动作可能有点不稳定。

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

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

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

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

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

4

2 回答 2

4

您可能会发现Trie很有用 - 将所有字典单词放入 Trie，然后从 Boggle 网格中创建另一个 Trie，只要您匹配字典 Trie。

即字典特里：

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

网格：（简化）

STARKX 
XXXTXX 
XXXXXX

Grid trie：（仅从 S 开始显示 - 对于 ART 等也从 A 开始）

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

您可以像这样使用 GraphViz 可视化您的尝试。

于 2013-01-07T08:17:58.597 回答
4

基本算法很简单。

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

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

于 2013-01-07T08:15:28.880 回答