问题标签 [boggle]

这是一个家庭作业，所以我不想要确切的代码，但如果有任何想法可以帮助我指出正确的方向，我将不胜感激。

任务是编写一个解谜程序。我感觉递归部分已经下降，但我需要一些关于如何将当前字符序列与字典进行比较的见解。

我需要将字典存储在集合或排序列表中。我一直在尝试一种使用集合来实现这一点的方法。为了使程序运行得更快并且不走死胡同，我需要检查当前字符序列是否作为集合（字典）中任何内容的前缀存在。

我发现 set.find() 操作仅在字符串完全匹配时才返回 true。在实验室要求中，教授提到：

“如果字典存储在一个集合中，许多数据结构库都提供了一种方法来查找集合中与您正在搜索的字符串最接近的字符串。这样的操作可用于快速查找具有给定前缀的单词。”

我今天一直在寻找教授所描述的内容。我找到了很多关于尝试的信息，但由于我需要使用列表或集合，我认为这不会起作用。

我也尝试过查找自动完成功能的算法，但我发现的那些对于我在这里想要完成的任务来说似乎非常复杂。

我还考虑使用 strncmp() 将当前序列与字典集中的一个词进行比较，但同样，我不知道在这种情况下它究竟会如何发挥作用，如果有的话。

是否值得继续研究这将如何在集合中工作，或者我应该尝试使用排序列表来存储我的字典？

谢谢

解决 boggle 的函数的最佳时间复杂度 O(n) 是多少，其中 boggle 板是 n × n？

我觉得这是n^2因为对于每个角色，我们必须看看2(n-1)其他角色。面试官争辩说这不是n^2为了O(1)查字典。

我正在开发一个Boggle游戏求解器，它可以读取文本文件（板）的行。

如果我应该使用s的a或s的vector矩阵，我一直在来回走动。我认为of会更容易访问，因为它是of s需要我使用该功能的地方。stringvectorcharvectorcharsmyvec[y][x]vectorstringstring.at()

char我不知道如果我应该将每一行解析到s 或将行保留为 astring并根据需要访问每个行，哪个会有更好的性能char。关于我应该做哪一个的任何建议？解释为什么会有帮助。

所以，我试图弄清楚如何实现对 Boggle 模拟的递归调用。有两个参与者：人类和计算机。当人走时，他/她在棋盘上找到一个单词（随机洗牌），递归调用应该检查有效性。基本上，我必须遍历从单词输入的索引 0 开始的相邻字母，然后以这种方式爬行，每次检查以确保单词存在与否。问题是我不完全知道如何做到这一点。到目前为止，这是我的代码，我提供了一些伪代码来进一步解释我的意图。任何人都可以帮忙吗？

在组装 Boggle 求解器时，我遇到了一些奇怪的行为，我希望有人能向我解释。我得到了返回一组可能单词的函数，而我似乎缺少的只是一种防止求解器包含通过两次访问同一方格而创建的单词的方法。我试图通过迭代全局变量seen（我知道这是不正确的）来创建当前播放中已经访问过的方块的列表（代表棋盘的字符串中的索引号列表），该变量用于记忆以前探索过的路径. 但是，只需使用以下值初始化变量：

在递归函数find_bwords中，以某种方式影响索引变量i并导致源自 find_bwords 中最后一行的 IndexErrors。

这是引入之前的索引打印输出的一部分prev_ind：

这是之后的一部分：

为什么会这样？

需要明确的是，我不是在寻找这个任务的解决方案，我已经以另一种方式解决了它，我只是想了解在这种情况下发生了什么。

所以我正在用java开发一个Boggle程序，我很难让它找到每一个可能的单词。

它几乎可以找到所有这些，但对于我的生活，我无法弄清楚为什么它不会全部获得。

这是有问题的方法；它递归地在 Boggle 板上找到单词。

有人知道为什么它只能找到大约 75% 的单词吗？

如果需要，我可以附加更多代码。

可能重复：
如何从字母矩阵中找到可能的单词列表 [Boggle Solver]

我有一个String[][]数组，例如

我需要将 ArrayList 与此数组进行匹配，以找到 ArrayList 中指定的单词。搜索 word时，我需要得到肯定匹配和字母的位置，hello例如在这种情况下(0,0), (1,1),(2,1)和。(3,1)(3,2)

当一个字母一个字母地查找时，我们假设我们成功地找到了第一个l字母，程序应该尝试在l它旁边的位置找到下一个字母（ ）。所以它应该匹配 e、e、g、k、o、l、m 和 i 表示它周围的所有字母：水平、垂直和对角线。在单词中找不到相同的位置两次，因此(0,0), (1,1), (2,1),(2,1)和(3,2)是不可接受的，因为该位置(2,1)匹配了两次。l在这种情况下，两者都将匹配单词，因为允许对角位置，但由于要求一个位置不能多次使用，所以它需要匹配另一个。

这种情况也应该匹配

如果我们假设我们尝试搜索helllo，它将不匹配。要么匹配，(x1, y1) (x1, y1)要么(x1, y1) (x2, y2) (x1, y1)无法匹配。

我想知道实现这种功能的最佳方式是什么。如果我String[][]在 ArrayList 中有 4x4 数组和 100 000 个单词，那么最有效和最简单的方法是什么？

我正在尝试为学校完成这个 boggle 游戏 Python 挑战，我创建了一个绘图板函数，该函数创建一个包含 16 个随机字母的板。如何使用 def 函数要求用户输入一个单词，然后根据单词的长度对其进行评分？完成后，游戏应该可以正常运行。任何帮助将不胜感激 ：）

我实现了一个递归函数来解决这个问题：

• 使用由字母 (A...Z) 组成的 4x4 矩阵，对于每个字母 ，仅遵循相邻和对角单元格即可获得所有n 长度的单词。

我的函数的想法是对每个可能的方向的每个字母进行递归调用，然后连接将要形成的字符串。当这个字符串的长度为n时，它会停止。为了防止返回到已经使用的字母，我创建了一个指向字母类的指针数组，它将每个新的可能字母与所有使用的字母进行比较。为此，我为每个字母创建了一个特殊的类。

这是函数：（对不起，它很长）

dirSu 表示 Up - dirGiu Down - dirDx right - dirSx left - 和所有其他的对角线位置

好吧，当我激活3个字母的单词功能时，它真的很快，4个字母：矩阵中每个字母的计算时间为0.028s，5个字母：0.225s，6个字母：1.891s，7个字母：14.914s。

有没有办法通过优化我的函数来减少计算时间？（或删除我愚蠢的逻辑错误？）非常感谢！

我用于测试的矩阵是：

我在每次速度测试中都使用了这个（没有按频率或随机计算），并且有了这个（自从我的问题以来我的递归函数得到了改进），我在大约 90 秒内得到了每个起始字母有 5、6、7 个字母的所有单词。字很多，虽然只是一个4x4的矩阵！如果我可以私下将其发送给您，那么看看您对同一问题的解决方案可能会很有趣。（这里不知道怎么联系你）

所以我在 NetBeans IDE 上用 java 运行 Boggle Solver。当我运行它时，我必须在 10 分钟左右后退出，因为它最终需要大约 2 小时才能完全运行。我的代码是否有问题，或者一种方法会更快？

这是我从以下位置调用此方法的地方：

编辑：顺便说一句，我使用的是 GUI，板上的字母是使用 JLabel 显示的。