perl - 用预定义的形状填充网格/矩阵

Question

很高兴看到这个问题有两个投票。我现在重新表述我的问题以避免混淆。

问题是如何在没有孔的情况下用随机但预定义的形状填充 mxn 网格/矩阵。预定义的形状有一个变量 k，它是由多少个块组成的形状。每个块都是一个正方形，大小与网格正方形(即 1x1 网格)相同。形状可以旋转以适应网格，但不会缩小或扩大。 k 在一轮中不会改变，换句话说，当我运行答案脚本时，m、n 和 k 不会改变。当我第二次运行脚本时，我可能会更改其中的一个或全部。例如，第一次，我可能会运行 k=4、m=10 和 n=20 的答案脚本。脚本完成并打印输出。第二次我将 k=3，m=6 和 n=10。我将确保 m 乘以 n 并且乘积调制 k 等于零 (m x n % 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 个声望)来奖励最佳解决方案。

感谢您的输入。

Answer 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 难的，但是有很好的基于启发式的算法。一个常见的方法是将每个形状放置在它进入的第一个开放位置的贪婪启发式。

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

您必须处理的一个问题是，有时无法用您获得的碎片填满网格。例如，如果你有一个 m = 2, n = 2, k = 4，你只能得到一个，如果它不是正方形，你将无法填充状态空间。