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 回答