1

我有一个任务，我应该在任何给定的 NxN 中解决摩天大楼难题 ( http://www.brainbashers.com/skyscrapershelp.asp )。我试图做出一个蛮力解决方案，但是自从我运行它以来，它似乎并没有很快完成（现在已经运行了一个小时，而电路板的最后一个单元格没有更新超过“1”）。我一直在研究以更有效的方式解决难题的算法，但我并不真正了解它是如何工作的。我已经建立了一个程序，可以：

1) 使用拼图大小的值测试提示（例如，5x5 拼图中的 5），这意味着相邻行必须从提示旁边的字段中的 1 开始，递增 1 直到大小谜题（前面示例中的 5，即 1、2、3、4、5）。

2) 测试值为 1 的提示，这意味着相邻字段必须是拼图的最大大小（在前面的示例中为 5）。但在此之后，我真的不知道我的代码下一步该去哪里。如果我解决特定大小的谜题（例如 4x4），我知道如何工作，但问题是为 NxN 谜题开发一个......我发现了这个：摩天大楼谜题算法 ，但我并不真正理解那里提供的答案. 我也发现了这个： http: //www.wikihow.com/Solve-a-Skyscrapers-Puzzle 但这是一个具体的例子，我真的不明白如何将它转换成 NxN 算法。

我不能发布两个以上的链接，所以我将发布我的代码的链接（包括蛮力解决方案和算法一）作为对这个问题的评论。感谢您的时间！

4

1 回答 1

2

这是一种可行的方法：

1) 对于您的网格大小，生成一个包含所有数字排列的数组。例如，在 4x4 中，您将拥有 [1234、1243、1324、1342、1423、1432、2134、2143、2314、2341 等]

2）然后对于其中的每一个，从左侧和右侧计算可见的摩天大楼。[[1234, 4, 1], [1243, 3, 2], [1324, 3, 1], ...

3) 对于拼图的每一行，通过从步骤 2 中选择与拼图左侧和右侧的数字匹配的行来生成将起作用的摩天大楼列表。

4）所以，现在你可能有 1 适用于第 1 行，3 适用于第 2 行，2 适用于第 3 行和 2 适用于第 4 行。这里是蛮力部分。您想尝试每种组合的所有组合并测试它们是否满足顶部和底部的数字。对于我的示例，您必须测试 1*3*2*2 = 12 组合才能找到有效的组合。您还需要验证每一列是否包含每个数字。

于 2013-10-13T12:42:30.287 回答