问题标签 [crossword]

我目前正在做一项任务，我坚持使用这种方法。

我有一个填字游戏问题，它由一个空网格组成（没有像传统填字游戏那样的实心正方形），宽度和高度在 4 到 400（含）之间变化。

规则：

1. 单词是输入的一部分——包含 10 到 1000 个（含）长度不等的英语单词的列表。
2. 水平词只能与垂直词相交。
3. 垂直词只能与水平词相交。
4. 一个词只能与其他 1 或 2 个词相交。
5. 每封信值一分。
6. 单词周围必须有 1 个网格空间间隙，除非它是相交单词的一部分。

例子：

目标：
在 5 分钟的时间内获得最高分。

到目前为止：
经过一些研究，我知道这是一个 NP-Hard 问题。因此，无法计算出最优解，因为无法检查每个组合。

最简单的解决方案似乎是根据长度对单词进行排序并插入得分最高的单词以获得最高分数（贪婪算法）。

我还被告知一个递归树，其节点由替代的等分词插入组成，背包算法适用于这个问题（不确定实现会是什么样子）。

问题：

1. 是什么让我可以在 5 分钟的时间跨度内检查最大组合数，并根据最大可能的单词列表和网格大小进行缩放？
2. 插入单词时可以应用哪些启发式方法？

顺便说一句，这里的目标是在 5 分钟内获得最佳解决方案。澄清一个有效单词的每个字母得 1 分，因此一个 5 个字母的单词得 5 分。

在此先感谢我整天都在阅读很多关于填字游戏研究论文的数学符号，这似乎让我绕了一圈。

我正面临这个困难的练习，我已经看过其他关于填字游戏的练习（即“p-99：九十九个序言程序”的最后一个练习，或者 Bratko 在“人工智能的序言编程”中报告的那个），但是这个是不同的，更难，因为这里我们没有任何模板要填写。

文字：

编写一个 Prolog 程序来生成一个填字游戏。假设你有一个这样的事实字典：w(Word,Lentgth)。写一个谓词填字游戏（C，W，H）来实例化C，到字典的所有可能的列表（填字游戏行）列表（填字游戏），其中黑色单元格由星号表示。
例子：

给定提示

1）您可以将这些“黑色”单词添加到字典中：

2）每一行是“白色”词（普通词）和“黑色”词交错的序列，并且该序列可以以两者开始/结束。

3）我建议你用 2 个不同的子句来管理前一点的 2 种可能性。

4）填字游戏是一个字符矩阵，所以它的转置仍然是一个填字游戏。

5）转置填字游戏已经实例化，所以你只需要用字典检查它的可行性。

这就是我想到的：创建一个 H（填字游戏的高度，行）列表（填字游戏的行），对于每个列表（行）我尝试从字典中插入单词，然后是“黑色”单词和然后又是一个词，直到行满，或者同样的东西从一个“黑色”开始。当填字游戏已满时，我将其转置并检查转置是否也是有效的填字游戏：包含的每个单词都是字典中的有效单词。我知道这是一种非常低效的方法，我尝试用一​​个小字典来生成 2x2 填字游戏，它正确地生成了前两个，但似乎需要数年才能生成第三个。我不知道我的代码是否有问题，也许它卡在某个地方。您是否知道解决此问题的更有效方法，或者您在我的代码中看到了需要改进的地方？

我正在使用这本小字典而不是原始字典来测试我的程序并生成简单的 2x2 填字游戏，但正如我之前所说，在正确找到 2 个解决方案后它似乎卡住了。

请查看此图片以阅读实际作业

我需要做这个填字游戏，我是 IT 领域的新手，但是我一直在非常努力地做这个，因为我必须把它作为作业提交，才能找到一份 Web 开发工作。我很难决定使用为拼图更改背景颜色的 HTML 表格，还是制作一个 javascript 多维数组来制作这个填字游戏。

我正在尝试使用 BST 制作一个填字游戏程序，我目前在树中插入了以下单词：

word, will, wyr, wale, wilt, apple, abs, wack（按此顺序插入）

但每次我在 Visual Studio 中调试程序时，都会出现错误

但是，在跟踪变量时，我遍历的变量永远不会设置为 1，所以我没有退出这个 while 循环，错误发生在内部，我只是不确定在哪里以及为什么。

为澄清起见，我正在搜索的单词是“w***”（“*”是通配符），因此 if 语句检查指针 temp 是否具有子字符串 w，如果听起来它会增加计数，所以我可以发回一个数字，说明该通配符搜索有多少匹配。

此外，在 while 循环之前将 temp 设置为 root(word)。

感谢您提供的任何帮助！

我有一个问题：例如，我们有几个字母：b,o,s. 它是来自某个单词的字母，它们的顺序与单词中的顺序相同（在这种情况下，单词是books）。但是，当然，这可能是另一个词。

所以我需要获取可能单词的列表，例如，lenght = 10。我该怎么做？我觉得这个问题接近填字游戏，所以可能有一些 API 服务？

这段代码中的单词应该在一个共同的字母处相交，并打印出尽可能多的单词可以相互交叉的次数。

我有正确的次数，但单词的格式不正确。

它应该看起来像这样：

但我的打印出来是这样的：

我的代码如下所示，我的打印方法有什么问题导致这种情况？

我编写了以下代码，它从用户那里获取单词，将它们从最长到最短排序，然后检查是否有可能放置单词的位置。我遇到的麻烦是弄清楚如何检查单词是否可以水平或垂直放置。任何帮助将不胜感激。

我想用这种条件在 C# 中编写一个填字游戏：

1. 词不能重复。
2. 单词可以水平放置，但只能从左到右排列。
3. 单词可以垂直放置，但只能从高到低。
4. 一个水平词必须与一个或多个垂直词相交。
5. 一个垂直词必须与一个或多个水平词相交。
6. 每个单词必须由空格或网格边缘分隔。

没有给出字段大小。考虑到单词表，算法应该找到最好的填字游戏输出并且字段大小应该是最小的。我的问题是变量字段大小。有人想知道算法的样子吗？

我正在研究填字算法来开发一个单词应用程序。在 StackOverflow 上进行了大量谷歌搜索或搜索后，我能够达到这一点。但是我无法理解 Java 中算法的正确实现。下面是我使用的类。

正如您在 Main 方法中看到的那样，我添加了单词，但也给出了行号和列号来放置诸如c.addWordv("Safe",8,5);这样的单词。其中 8 和 5 是列号。

现在的问题是我如何实现填字算法，它只取单词并将它们随机放置在板上而不取行号和列号。提前致谢

编辑：
我想修改这个类算法，我不必放弃行号和列号..

我是 Python 初学者，我被困在这里。我编写了以下生成随机数矩阵的程序。

无论如何我可以添加一个从输入参数中获取一个单词并将其对角线隐藏在矩阵中的函数吗？因此，如果用户输入“rain”，则输出如下所示：

谢谢！