问题标签 [boggle]

我正在尝试解决反向Boggle问题。简单地说，给定一个单词列表，得出一个 4x4 的字母网格，其中可以在相邻字母序列中找到列表中尽可能多的单词（字母在正交和对角线上都相邻）。

我不想拿一个已知的板子来解决它。这是一个简单的 TRIE 问题，并且已经在这里为人们的 CS 项目进行了讨论/解决。

示例单词列表：

解决方案：

这个问题很难（对我来说）。到目前为止我的算法：

1. 对于输入中的每个单词，列出所有可以合法地单独出现在板上的可能方式。
2. 尝试在这些板上放置单词＃2的所有可能组合，并保留没有冲突的组合。
3. 重复直到列表结束。
4. ...
5. 利润！！！（对于那些阅读 /。）

显然，有实现细节。首先从最长的单词开始。忽略作为其他单词子串的单词。

我可以在大约 0.4 秒内为 7 个字符的单词生成所有 68k 可能的板。然后当我添加一个额外的 7 字符板时，我需要比较 68k x 68k 板 x 7 比较。解决时间变得冰冷。

必须有更好的方法来做到这一点！！！！

一些代码：

并像这样使用它：

我有一个字母列表，我试图找到可以用这些字母创建的所有可能的单词。我还没有在objective-c 或类似的东西中找到任何实现。

我发现的是一个不错的 Boggle 求解器，它很好，但不是我想要的。我不需要选定的字母彼此相邻。我想找出通过组合 25 个字母列表中的任何字母可以找到多少个单词。

有人可以帮助我使用伪代码甚至是描述在 Boggle 板上递归搜索单词的递归公式，这样我就可以开始了吗？

完全公开这是针对算法课的作业，但我不是在找人为我编写任何代码或握住我的手。无论如何，我们必须做 Boggle 游戏。对于那些不知道的人，基本上你会得到一个 Boggle 板并且必须找到尽可能多的单词，考虑到递归的字符串可能性，这可能需要大量时间。

为了减少 OP 时间，我们被鼓励使用我们想尝试的任何算法，并在我们进行过程中“清除”字符串。目前我有一个系统，可以通过将它们存储在字典中来找到所有可能的 3 个字母后缀，如果字符串有 3 个字母但不匹配任何有效的后缀，则停止递归。

进入问题的症结所在，我正在尝试实现 Radix 后缀树，目前它看起来像这样

所以我将指针存储在一个无序列表中，这意味着如果我正在检查后缀，我可以预期，更糟糕的情况是，26 次操作甚至可以找到我需要继续沿着树向下的后缀指针。

有什么方法可以加快插入速度，简化流程吗？是否值得为每个节点在内存中建立一个小字典来检查后缀的第一个字母是否存在？这么小就无所谓了吗？

这个函数是我将节点及其数据插入到链表的地方。

这个函数是我从boggle board获取所有单词的地方（这个函数似乎工作正常，因为当我在这里打印出单词时，它会正确打印出来。

前注：这是这个问题的后续问题。

我在 R 中编写了一个 Boggle Game Solver（参见这个github 页面的源代码），但发现它的性能令人失望。

这是它的工作原理...

13个字母单词候选的可重复示例

对于这么小的路径列表，这非常快。但是 13 个字母单词的实际路径数是 2,644,520。因此，找到所有候选人可能需要一分钟甚至更长时间。使用 doSNOW，我可以并行化搜索，从而大大减少总时间，但这样做有一个巨大的缺点：当使用正常循环时，只要我到达没有更多单词的点，我就可以退出/中断成立。这与并行过程无关（不可能？）。

所以我的问题是：你能想出一个更好的函数/算法来完成这项任务吗？一些网站在几秒钟内就为 Boggle 游戏提供了解决方案......要么他们生成所有可能的字母组合并将结果存储在数据库中（！），要么他们显然使用更好的算法（可能是编译语言）来实现这些结果。

有任何想法吗？

我找到了几个关于如何检查字符串是否是完整单词的答案，但没有找到关于如何检查字符串是否是单词的第一部分的答案。

例如，我需要一个函数，它会为“c”、“b”、“cong”（恭喜、一致等）或“exa”（例如、检查等）返回 true，但为“congx”返回 false "、"qt" 或其他乱码。

我想有很多方法可以解决这个问题。如果您能提供一个粗略的策略大纲，我将不胜感激。我正在尝试制作一个 Boggle 求解器。谢谢！

这是一个在 Boggle 中查找所有单词的（丑陋的）算法：

该算法的 Big-O 运行时间是多少？我相信它是O((N²)!)，但我不确定。

我试图理解名为“Boggle”的游戏算法，它在 N*N 矩阵中查找单词。

我不明白这部分：

为什么这些数组具有它们所具有的值以及为什么会这样？

时间复杂度是多少？我只是想避免这是O(n!)。使用深度优先搜索是否会是时间复杂度O(n^2)，因为对于每个字母，它可能必须通过所有其他字母最坏的情况？

我想我不确定我是否以正确的方式考虑这个问题。

当我说使用深度优先搜索时，我的意思是从第一个字母开始深度优先搜索，然后从第二个字母开始，等等。

那有必要吗？

注意：
最初的问题是在填字游戏/拼图板上找到所有可能的单词。我正在考虑使用 trie 数据结构来查找字典中是否有单词，但我正在考虑自己生成单词的方法。