在不断变化的网格中寻找可能的单词

Question

我正在做一个文字游戏，用户从一个不断变化的字母网格中创建单词。验证用户的选择是非常容易的，使用一个字列表。

由于游戏网格是随机生成的，以前播放的瓷砖将被移除并替换为新的字母，因此我需要能够有效地检查每个用户提交之间可能的有效播放，因此如果没有可能的有效单词，我可以重新设置网格或其他对此有影响的内容。解决方案只需检测当前瓷砖集中至少有一个有效的3-7字母单词。它不需要知道任何可能的组合。用户可以在任何瓷砖上开始，并在当前选定的字母的任意方向上使用一个瓷砖构建一个单词。

的重要性：的解决方案不能减缓游戏的速度。一旦用户提交当前单词并出现新的瓷砖，他们就可以立即启动新的选择。

任何方向都会非常感谢，因为我还没有找到我认为我正在寻找的任何谷歌搜索到目前为止。

使用Swift为iOS8+的建筑

Answer 1

正如@jamesp提到的，一个trie是你最好的选择。你在这里有几个优点，第一个是，一旦你找到一个词，你就可以跳出来。你不需要扫描整个网格的所有可能的文字，只要找到一个，并完成它。从任意一个随机字母开始，看看它周围的字母，然后把它们与trie匹配起来。如果你找到一个匹配的，继续在那个字母，以此类推，直到你找到一个词或一个死胡同。如果当前的开始瓷砖周围没有完整的单词，那么继续到网格中的下一个瓷砖，然后再试一次。

Answer 2

为什么不先把一个随机选择的有效单词放在网格上，然后用随机字母填充空格呢？

编辑

因此，如果你不能做到这一点，一种可能足够快的方法是在trie中组织你的单词。这可能足以使搜索足够快。这样做的想法是遍历网格中的字母，并为每个字母在trie中选择合适的第一个字母。这使得对每个允许的邻居的搜索变得更小，等等，直到你的trie用完或者你找到了一个单词。

我还会在反映字典中字母分布的分布中选择随机字母。这样做的一个方法是

• 计算字典中每一个字母的数目，给每个字母一个权重。
• 在0和所有权重的总和之间生成一个随机数。
• 遍历字母，从随机数中减去每个字母的权重
• 当减法值降到零下时，你所使用的字母就是你想要的。

你可以用二进制搜索来加快上面的速度，但是只有26个字母，所以额外的复杂是不值得的。

Answer 3

这将需要相当长的处理时间来解决这样的问题，特别是因为单词可以扭曲和旋转。

有几种方法可以解决这个问题，但是如果你有一个快速的字典查找，你可能会想要从左上角开始看字母。说是"S“。你的字典会给你一个可接受的"S“字的列表。您可以逐步遍历这些单词，查看每个单词的第二个字母，并查看当前具有该字母的瓷砖是否有相邻的瓷砖。如果没有，你就完了--搬到下一块瓷砖去。如果是这样的话，对于以"S“和下一个字母开头的单词，您可以再次递归地执行完全相同的过程。

例如，假设当前的瓷砖是"S“。你会查找你的"S“单词列表，然后开始遍历它们。其中一个是"Syzygy“。如果没有相邻的"Y“瓷砖，你就完成了--移到下一个单词。如果有一个"Y“瓷砖相邻，看看周围的瓷砖一个"Z”。如果没有，你就完蛋了。否则，移到第二个"Y"，等等。(如果tiles只能用于一个单词一次，您可能必须记住tiles才能从后面的字母中排除，这样玩家就不能使用相同的"Y“三次拼写”Syzygy“)。

我敢打赌，使用这种方法，绝大多数瓷砖都会很快被排除在外，但处理起来仍然需要很长时间，特别是在网格很大的情况下。您可以通过在后台运行该检查来解决此问题，并让播放机在检查时继续播放，然后在最终确定没有有效播放时显示警告。

请记住，仅仅因为拼图中有一个有效的单词，并不意味着最终用户仍然可以解决这个问题。这种拼图不像你的典型比赛-三场比赛，如果你看得够长，你会找到匹配的。大多数“有效单词”列表将包含许多大多数人不知道的单词。像"propale“、"helctic”和"syzygy“等词。(你不能排除这样的词，因为当有人找到一个词，而不是找到一个晦涩的词时，他们会产生强烈的挫折感，“但那是一个真正的词，该死！”)

所以，也许你想要的是对现有单词的模糊程度的评估。如果“狗”是唯一可用的词，那么对于大多数人来说，这个词可能仍然是可以解决的，而如果唯一可用的词是"propale“、”hel北区“和"syzygy"，那么对大多数人来说，这可能是不可能的，尽管有更多的词可用。

要做到这一点，你需要对你的字典单词进行排序，看看它们有多常见，然后把现有单词的普遍程度加起来，这样才能做出这样的评估，如果没有达到这个分数的某个临界值，你就会认为这个难题是“无法解决的”。同样的算法，但是你会为你找到的每个单词加一个分数。当你找到第一个单词时，你就不能放弃，但当你达到这个门槛时，你就可以退出。

如果这听起来令人望而生畏，那是因为你已经把自己设计到了一个角落。一种更好的方法可能是让用户在遇到困难时交换一些瓷砖，或者让他们添加通配符等等，这样即使拼图中没有真正的单词，他们仍然有战略选择。然后你甚至不需要解决这个问题，它解决了一个更深层次的问题，那就是知道一个难题是否实际上是可以解决的，而不是技术上可以解决的。