8

很高兴看到这个问题有两个赞成票。我现在将重新提出我的问题以避免混淆。

问题是如何用没有孔的随机但预定义的形状填充 mxn 网格/矩阵。预定义的形状有一个变量 k，它是由多少块组成的形状。每个块都是一个正方形，并且与一个网格正方形（即 1x1 网格）大小相同。形状可以旋转以适应网格，但不会缩小或扩大。k 在一轮中不会改变，换句话说，当我运行答案脚本时，m、n 和 k 不会改变。当我第二次运行脚本时，我可能会更改其中的一个或全部。例如，第一次，我可能运行 k=4、m=10 和 n=20 的答案脚本。脚本完成并打印输出。第二次我将 k=3、m=6 和 n=10。我将保证 m 乘以 n 并且乘积调制 k 等于零（mxn % k = 0），以确保它们在数学上相互匹配。好的，还有一个条件：1

该脚本需要使用预设 k 池中的随机形状填充网格。当 k=2 时，预定义的形状只有一种，两个块在一起。如果你认为没有旋转，那么它有两种，水平和垂直。当k=4 时，基本上就是用俄罗斯方块填满了网格，即总共有7 种预定义的形状（每种都可以旋转，并且可以制作~20 种）。k=5 的预定义形状是什么，我还不知道。答案可以计算出来，也可以硬编码，因为不难找到 k=5 的所有形状。

如果解是有限的，则不需要随机数。例如，m=2、n=2、k=4；或 m=1，n=4，k=2。没有其他办法，没有随机性。

网格中的任何地方都不能留下任何孔。我认为，没有经过证明的想法，许多 mxn 和 mxn%k=0 的网格将有一个没有孔的解决方案。直觉上这听起来很合理，但在数学上我不知道。如果 m 或 n 是 k 的倍数，则保证有解（所有直条）。

理想情况下，我希望 k 是一个小整数，例如 k<10，但在 2 到 5 的范围内是可以接受的。如果更简单，我们可以在这里有一个固定的 k，比如 4，因为俄罗斯方块带有众所周知的 7 个形状（ITOLJSZ）。

我正在寻找最好在 Perl 中的解决方案。Python也不错。程序每次运行需要 m、n 和 k。同样，我将让 m,n,k 适合 mxn%k=0。

我自己的努力，我在 Perl 中尝试过，可以解决一些 k=3 的情况，并且由于边缘/角落中的单例（孔）而失败了一些情况。需要一种检查是否有任何块变成单例的好方法。我的文本输出如下所示（m=4，n=9，k=3）。您当然可以使用这种或任何有意义的格式。

AABB
ACCB
DCEE
DFFE
DFGH
IGGH
IIJH
KKJJ
KLLL

我将设置 100 分的赏金（感谢那两个投票，我现在有 107 个声望）来奖励最佳解决方案。

感谢您的输入。

4

3 回答 3

1

这个问题肯定是 NP 难题（它类似于背包），这意味着通常解决它的唯一方法是检查所有可行块放置的一部分的算法。这将需要类似于分支定界搜索的东西，它以与拼图相同的方式组装碎片，除了每个拼图有任意多个副本。每当您到达一个不适合不引入孔的位置时，就回溯。在伪代码中：

place one piece to make the initial blob B containing no holes

procedure branch_and_bound
loop
  for each shape S
    for each position P that S can be added 
            to B without creating an unfillable hole
       place S in P to enlarge B
       if puzzle is complete throw DONE!
       call branch_and_bound

听起来您专注于如何找到位置 P。解决此问题的一种简单方法是考虑与 B 接触的每个空网格正方形 E 并尝试将构成 S 的每个正方形放在 E 中，丢弃所有导致重叠的情况B. 避免无法填充的空洞可以简单地通过要求未被B 填充的空间保持连续来完成：不要让未填充空间的“孤岛”发展。通过选择任何空方格，执行 DFS 或 BFS 来触摸所有可能的未填充空间，然后检查剩余的未触及未填充方格，很容易检测到孤岛。

您可以使用启发式方法来指导选择形状和放置碎片的顺序。

事实上，除非启发式算法非常好或块的形状很简单（或两者兼而有之），否则该算法将很快变得无用。这就是 NP 难题的本质。即使启发式方法通常非常出色，也必然会出现失败的问题。这也是 NP 难题的本质。

许多谜题求解器中使用的一种技术是通过仅考虑有限的解决方案集来降低复杂性。这里的一个例子是如果 m = Ap 和 n = Bp，对于一些 A 整数 A、B、p，那么显然找到 apxp 平方的解就足够了。这可以平铺以获得更大的解决方案。你可以想象出无数类似的想法。

于 2013-02-08T02:14:09.283 回答
1

以下是有关解决方案设计的一些想法：

如果你不必把每一块都放好，你可以简单地跳过，直到你有一堆直线或正方形。那里的算法很容易想出——找出一个片段的配置来填充 1 或 2 行并重复它。如果 (nm mod k != 0) 则无解；否则，我怀疑您可以制定一套通用的规则。例如，如果 (m mod k = 0) 或 (n mod k = 0) 那么你可以只使用直线。想想这些会很有趣，但我会把它们留给你。

实际上，阅读您的问题时，我看到您写了 2 <= k <= 5 - 这真的很容易，因为 2、3 和 5 是素数。数论告诉我们，如果 nm mod a prime p = 0 那么 n 或 m 必须能被 p 整除，所以对于 k = 2、3、5，你可以找出 n、m 中的哪一个可以被 k 整除并填充行或列在长度为 k 的直线。对于 k = 4，n、m 中的一个可以被 4 整除（在这种情况下，您只需使用相同的策略）或者它们都可以被 2 整除，在这种情况下，一个必须是 (4x + 2) 并且您只需填充每一列用直线向上，然后在最后放置正方形。

如果您确实必须放置给定的每一件，那么您从一开始就知道您必须装满垃圾箱的 (nm/k) 件。这为您提供了装箱问题的标准案例，这是 NP 难的，但是那里有很好的基于启发式的算法。一个常见的方法是将每个形状放在它进入的第一个开放位置的贪婪启发式。

但是，您的问题需要一个精确的解决方案，这意味着“足够接近”永远不够好。您可以使用回溯算法，但更好的方法可能是对网格有效位置的状态空间进行双向搜索。将一个位置定义为目标位置，然后从它向后移动，包括从随机（不是真的——你应该找到好的启发式）位置中取出碎片。然后将另一个位置定义为起始位置，并进行涉及插入件的向前移动。当两棵树相交时停下来，沿着那条路走。

您必须处理的一个问题是，有时无法用您获得的碎片填充网格。例如，如果你有 am = 2、n = 2、k = 4，你只会得到一个棋子，如果它是一个正方形以外的任何棋子，你将无法填满状态空间。

于 2013-01-31T06:01:52.110 回答
0

至于孔问题，应该有一个简单的方法来解决这个问题...... 3！（很适合 k<=9 ，即 ;)）

让我解释一下，每个块不仅与另一个或两个块相邻，而且还与EMPTY SPOTS您应该关心的 k 的形状相邻，这样的空点的每个计数总是k*2+2如此k=1 -> 4, k=2 -> 6 .... k=9 -> 20 ，对于 k 的每个项目.length 你知道它的位置吗？在您的矩阵中，您现在可以向每一侧迈出一步并检查它是否是一个空白空间，如果是的话。请注意（空白）位置暂时，如果您以这种方式勾勒出您的 k ，您将有不同数量的空白空间小于或等于上述计算。

如果相等，则 k 中不能有任何孔，您可以继续，如果更少，则检查减少了多少，如果您错过了一个，则您制作了 L 形，如果您错过了两个，则您有 U 形或 T 形（特殊情况 k=9 an S)，你很高兴

如果你错过了三个或更多，你需要进一步调查！现在检查您临时记下的每个空白位置的相邻块，如果每个这样的空白的数量小于或等于 3，那么您没有孔并且可以继续，只要 MORE than ONE 有 3 个相邻块但是，您将在 k 中有一个洞。

对于 k=10，很难做到这一点，但是这些简单的规则最多可以防止九个 k 对象中的漏洞。

抱歉，我不熟悉 perl，否则我给你的代码不仅仅是一个提示；）

因此，在您的任何 k 对象中都没有任何孔，您应该确信您可以解决任何m*n%k=0网格。您应该始终牢记一件事，那就是经典的多米诺国际象棋问题*，因此请始终从一个角/边缘开始填充网格，并且在将最后一块插入网格之前不要留下任何空白，以避免这些情况。

*多米诺国际象棋问题是如果棋盘上有 2 个棋子，您是否可以在棋场 (8x8) 中布置 31 个多米诺骨牌（2x1 块）。（答案：如果一个是白色的，另一个是黑色的，你可以......否则你不能）

于 2013-02-09T05:55:56.270 回答