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

Question

很高兴看到两个投票的问题.我现在要重新提出我的问题以避免混淆.

问题是如何用没有孔的随机但预定义的形状填充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时,基本上用Tetris块填充网格,即共有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 困难的，但有很好的基于启发式的算法。一个常见的做法是贪婪的启发式，将每个形状放置在它进入的第一个空位上。

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

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