4

这样的问题是在我的大学里给我的，也许有人会有有趣的算法来解决这个问题。在 stackoverflow 上有几个解决方案，但没有一个是好的（因为它们正在循环所有可能性）。

问题：找到所有可能的组合，将给定的单词分配到给定的表格、网格（矩形，见下面的输入）中。应该没有空闲单元格，单词可以从左到右或从上到下定位。单词不能在一行（列）中逐个单词地定位。

输入：矩形区域，示例：

+-----+
|  *  | 
|     |
+-----+

或者

+-----+
|   * |
|     |
|    *|
|   * |
+-----+

然后输入不同的单词（下一个输入数据）来填充该网格，例如：

cdi
zobxzst
tdxic
r
sc
zro
and etc ...

数字最初是未知的，但输入到标准输入结束 - 活动 EOF。

输出：如果存在一种解决方案，则在填充网格中输出该可能的解决方案。如果没有解决方案或解决方案数量，则输出 0 或该确切数字。

例子：

（表格输入）

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

然后的话cdi zobxzst tdxic r sc zro rgfvacd oikf df x c r xvf ogish za sh fc hh h bfkh

（每个作为输入，但这里用空格分隔。）

输出（仅 1 个解决方案）：

+-----+
|zro*h|
|ogish|
|bfkh*|
|xvf*r|
|za*c*|
|sc*df|
|tdxic|
+-----+

重要提示：输入的网格仅限于 16 个（！）单元格，字数少于 60 个。我写了一个算法来搜索所有可能的组合，但它对我不起作用，因为执行时间有限（10我猜是秒）并且这个问题无法用粗略的算法解决（例如，15 个网格上的 15 个和大约 60 个！可能或更多可能的排列，可以在普通 2GHz PC 上处理大约 1 天？）。

也许存在另一个独特的解决方案。也许这个问题比编程更数学化，也许可以使用一些左右组合而不是上下组合？或者也许是加权细胞？

PS 我有 3 周的时间来解决这个问题，如果没有，我可以在 3 周后在这里发布解决方案（好消息）；）

4

2 回答 2

2

在 stackoverflow 上有几个解决方案，但没有一个是好的（因为它们正在循环所有可能性）。

那么我的想法也可能是错误的：但这是我脑海中的一个想法。

我写了一个算法来搜索所有可能的组合

如果有太多，那么问题可能是您也在搜索/循环不可能的组合以及可能的组合。

例如，当你在左上角放置一个像“zro”这样的词时，很少有“可能”的组合可以放在它下面的垂直词中：

  1. 第一个垂直单词必须以“z”开头
  2. 第二个垂直单词必须以 'r' 开头
  3. 第三个垂直单词必须以 'o' 开头
  4. 第二行的字母组合（由放置垂直单词产生）本身必须是有效单词
  5. 等等

所以：

  1. 选择任何单词并将其放在左上角
  2. 找到满足上述约束的现有单词
  3. 如果你找到一个或多个这样的词，那么继续这样看你是否能解决整个事情；或者如果你失败了，那么用不同的初始词再试一次

概括：

  • 不要生成每一个完整的网格，然后测试它是否满足所有约束
  • 而是在构建网格时使用约束，以减少您测试的可能性数量

我建议你从一个初始单词开始解决网格。

代替测试左上角的每个单词，更好的（例如，因为它可以快速消除不可能性）生成起始位置的方法是：

  • 查找最长的单词（例如rgfvacd）
  • 找到交叉/加入它的所有可能的单词组合
  • 尝试将这些有效组合中的每一个放在网格上
于 2012-11-13T00:49:54.800 回答
1

我建议你首先应该看看你必须填写的单词长度，在你的例子中：

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

你有两个 7 字母的单词，三个 1 字母的单词，等等。

您应该根据计数对该列表进行排序，并首先尝试使用计数最低的 wrod 长度，在下一次迭代中，您应该列出您需要查找的单词，例如 - 三个以“a”开头的 4 个字母单词- 你应该计算你的单词列表中剩下多少个单词，然后选择其中单词最少的一个 - 如果它是 0 则返回。

希望这是有道理的。

于 2012-11-13T10:48:31.980 回答