问题标签 [boggle]

我正在尝试解决 CodeFights 的技能测试，但在尝试解决他们的 word boggle 算法时遇到了问题。这是挑战的描述：

Boggle 是一种流行的文字游戏，玩家试图在矩形板上的相邻字母序列中找到单词。

给定一个表示 Boggle 板的字符单元的二维数组板和一个唯一字符串单词的数组，从板上可以形成的单词中找到所有可能的单词。

请注意，在 Boggle 中，当您查找一个单词时，您可以从一个单元格移动到其 8 个相邻单元格中的任何一个，但您不能在一个单词中两次使用同一个单元格。

我写了一个看起来可以工作的代码，但是它没有通过他们拥有的隐藏测试，现在我被困在了这一点上。

这是我的代码：

有谁知道我在这里想念什么？

我正在为编码训练营做一个 BoggleBoard 游戏，其中包括一个功能来获取单词并检查它们是否存在于板上。我检查单词是否存在的方法是创建我所谓的“邻接矩阵”（我知道这不是实际的邻接矩阵，这是我想出的，而是通过字母的实际位置链接起来的我正在寻找）。3x3 网格的想法是：

0 | 1 | 2
3 | 4 | 5
6 | 7 | 8

对应的“邻接矩阵”为：

这个想法是，我不必实际在板上定位单词，而是创建一个与单词字母长度相对应的单独数组。单词的每个字母在数组中都有一个数组，显示单词出现在板上的所有位置的索引。然后我基本上检查每个邻接矩阵与当前字母相邻的单元格是否与以下字符的位置共享一个索引。

示例：板：
C | 交流电
| 吨

查询词语：猫

第一个字符的索引 C = 0
- 与索引 0 相邻的单元格 = 连接 [1,2,3] 和 [0,1,3] => [0,1,2,3]
- 字母 A 出现在 0 中,1,2,3? 是
- 继续
下一个字符 A 的索引 = 1
- 与索引 1 相邻的单元格 = 0,2,3
- 字母 T 出现在 0,2,3 中的任何一个？是
找到字

我目前将游戏设置为 4x4 游戏网格，并在邻接矩阵中硬编码。我想看看是否有一种方法可以根据用户输入使游戏大小成为棋盘，并根据棋盘的大小动态创建邻接矩阵。这可能吗？

（我知道这不是一个实际的邻接矩阵，这是我想出的，而是通过我正在搜索的字母的实际位置链接起来的。）

所以，我正在尝试编写一个模拟游戏 Boggle 的 java 程序。它输入两个文本文件，第一个是代表 nxn 板的文本文件，其中第一行包含板的尺寸，即 4x4.txt 文件的第一行将是数字 4，其余将是板本身。第二个 txt 文件将是一个包含所有可能的字典单词的文件。

我首先想验证我们用来从 nxn 网格生成所有可能的字符串输出的算法是否正确。我使用深度优先搜索算法来做到这一点。

我相信我已经把这部分弄对了。但是，现在我要实施一种启发式方法来帮助识别死胡同，并避免搜索浪费的单词和浪费时间。我不知道这应该如何进行。任何帮助，将不胜感激。

这是我到目前为止的代码。就像我说的，我的 depthFirstSearch 方法是正确的，并且给了我正确的输出。我也不喜欢使用 TreeSet 来存储字典单词，因为我什至不确定这是否正确。我这样做是因为我知道它是存储可能的字符串组合的正确 ADT。

我正在为一个项目用 C 语言制作游戏 Boggle。如果你不熟悉 Boggle，没关系。长话短说，每一轮都有时间限制。我把时间限制在 1 分钟。

我有一个循环显示游戏板并要求用户输入一个单词，然后调用一个函数来检查该单词是否被接受，然后再次循环返回。

while (board == 1)需要更改，使其仅循环 1 分钟。

我希望用户只能执行此操作 1 分钟。我还希望将时间显示在我剩余时间的位置：在printf声明中。我将如何实现这一目标？我在网上看到了一些其他人在 C 中使用计时器的例子，我认为这是可能的唯一方法是，如果我让用户超过时间限制，但是当用户尝试输入超过时间限制的单词时，它会通知他们时间到了。还有其他方法吗？

编辑：我在 Windows 10 PC 上对此进行编码。

我参加了 Coursera 上的算法第二部分课程，其中一项任务是解决 Boggle 游戏： http ://coursera.cs.princeton.edu/algs4/assignments/boggle.html

荣誉代码要求我不公开发布解决方案，所以这里是基本算法的伪代码。

字典是使用 Trie 实现的。

上面的代码有效，我通过了作业，但后来我看到了这篇博客文章，声称使用动态编程有一个更快的解决方案：

事实证明，我们可以使用一种漂亮的动态编程技术来快速检查一个单词（在这种情况下是从字典中）是否可以从板上构造出来！

这是动态规划思想的核心点：

要在棋盘的第 [i, j] 个位置找到长度为 k 的单词（结束位置），该单词的第 k-1 个字母必须位于 [i, j]。

基本情况是 k = 1。

长度为 1 的字母将在棋盘的第 [i, j] 单元格中找到（结束位置），该单词中唯一的字母与棋盘第 [i, j] 位置的字母匹配。

一旦我们的动态规划表填充了基本情况，我们就可以在此基础上构建任何长度为 k，k > 1 的单词。

不幸的是，作者的解释工作很糟糕，我无法遵循他的解决方案。不过我想，希望这里有人可以向我解释。

PS：

1. 不是这个问题的重复，因为那个问题不使用 DP；请检查那些重复的快乐手指。

2. 我已经付出了足够的努力，没有要求任何人做我的功课。我已经有了自己的解决方案。我感兴趣的是学习一种更好的解决问题的方法，如果存在的话。

谢谢！

基本上，我只想让程序打印出找到的任何单词。但是，它从不打印任何单词。

它应该在 5x5 板上工作，并且当我键入“完成”时，哈希集字典的输入会停止。

有一个 4x4 板，共有 16 个字母。在这个数组中，[2,1] 表示第三行第二列中的字母。

试图弄清楚如何将像 [2,1] 这样的一对链接到游戏板上的单个字母，该字母由 16 个字符串（字母）组成的数组表示。

最终目标是让函数根据您提供的游戏板和坐标为单词生成字符串。

带有评论的 JSFiddle：https ://jsfiddle.net/8euxzgy2/4/

我看到大量从 .txt 文件读取或已经硬编码的 boggle 程序示例，但是您可以使用单词列表的 URL 连接并使用它与 boggle 游戏中的网格进行比较吗？

我正在尝试实现一个 URL 连接，其中包含我的程序读取的单词列表，但目前找不到解决方案。我目前的代码从 .txt 文件中读取，但我需要它从 URL 中读取列表

我试过了：

我对 C++ 很陌生，本周要完成一项非常艰巨的任务。我不会详细介绍它，因为我不想为我完成工作，但是谁能指出我将如何从多维字符串数组中选择随机字符的正确方向？

目标是打印出这些字符的 4x4 棋盘，在每场游戏开始时从每个数组中随机选择一个字符，这样棋盘就不一样了。

任何有关如何执行此操作的建议/提示将不胜感激 - 谢谢！

编辑：

我已经到了可以从两个数组生成随机索引的地步，但是我目前的做法只输出一个字符，而我需要从数组中的 16 个分类中的每个分类中获取一个字符。关于如何从每个输出一个的任何想法？我想我必须将索引生成器放在某种循环中。