使用预定义的图形来填充一个网格/矩阵

Question

很高兴看到这个问题有两个赞。为了避免混淆，我现在会重新措辞我的问题。

The question is how to fill up a mxn grid/matrix with random but pre-defined shapes without a hole. Pre-defined shapes have a variable k which is how many blocks the shape is made of. Each block is a square and is the same size of a grid square (ie, 1x1 grid). The shape can be rotated to fit into the grid, but does not shrink or expand. k does not change for one round, in another word, m, n, and k does not change while I run the answer script. When I run the script second time, I may change one or all of them. For example, the first time, I may run the answer script with k=4, m=10, and n=20. The script finishes and print out output. The second time I'll k=3, m=6 and n=10. I'll assure m times n and the product modulate k equals zero (m x n % k = 0) to make sure they fit each other mathematically. Okay, one more condition: 1

The script need fill the grid with random shapes from the pool of preset k. When k=2, predefined shapes have just one kind, two blocks together. If you think with no rotation, then it has two kinds, horizontal and vertical. When k=4, that's basically fill up the grid with Tetris blocks, i.e., totally 7 kinds of predefined shapes (each of them can rotate, and make ~20 kinds). What are the predefined shapes for k=5, I don't know yet. The answer can compute that or can be hard-coded, since it's not difficult to find all shapes for k=5.

If the solution is limited, no random is required. For example, m=2, n=2, and k=4; or m=1, n=4, k=2. No other way around, no random.

No holes can be left anywhere in the grid. I think, no prove thought, many grid with mxn and mxn%k=0 will have a solution without hole. Intuitively it sounds reasonable, but mathematically I don't know. If m or n is k's multiples, it's guaranteed to have solution (of all straight bars).

Ideally I want k be a small integer, like k<10, but in the range of 2 to 5 is acceptable. If it is simpler, we can have a fixed k here, such as 4, since Tetris comes with well-known 7 shapes (ITOLJSZ).

I'm looking for solutions preferably in Perl. Python is okay too. Program takes m, n, and k to run each time. Again, I'll have m,n,k fit mxn%k=0.

Effort of myself, I tried in Perl, can solve some cases of k=3 and failed some cases because of singletons (holes) in the edges/corners. Need a good way to check if any block becomes singleton. My text output looks like this (m=4, n=9, k=3). You can of course use this kind or any format that makes sense.

AABB
ACCB
DCEE
DFFE
DFGH
IGGH
IIJH
KKJJ
KLLL

I'll set up bounty of 100 points (thanks those two up-vote, I now have 107 reputations) to award the best solution.

Thanks for your input.

- Tony Xu

---

k是每一件都不同还是恒定的？ - MirroredFate

很抱歉，我没有看到任何足够好的答案来获得我设定的悬赏。我会让声望点数消失。感谢所有回答和投票的人。 - Tony Xu

Answer 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、B和p，则显然只需找到一个p x p的方格的解即可。可以将其铺砌以获得更大的解。你可以想象有无数类似的想法。

- Gene

Answer 2

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

如果您不必放置每个拼图，那么您可以简单地跳过一些直到只剩下一堆直线或正方形。那里的算法非常容易想出 - 找出一组填充1或2行的拼图配置并重复使用它。如果(nm mod k != 0)，则没有解决方案；否则，我猜测您可以制定一般性的规则。例如，如果(m mod k = 0)或(n mod k = 0)，则可以使用直线。这些将是有趣的思考方向，但我会留给您来思考。

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

如果您必须放置您获得的每个图形，则从开始就知道您必须填满箱子的(nm/k)个图形。这给了您一个标准的箱子装载问题，它是NP-hard的，但是有很好的基于启发式的算法。常见的一种是贪心启发式算法，即将每个形状放在它遇到的第一个空位中。

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

您需要处理的一个问题是，有时无法用给定的棋子填满网格。例如，如果您有m = 2，n = 2，k = 4，则只会得到一个棋子，如果它不是正方形，则无法填满状态空间。

- Andrew Latham

---

感谢您的输入。首先，请确保每次运行时 mxn mod k = 0。我已将此添加到原始问题中，以及随机性的要点。至于回溯，这实际上是我的代码当前阶段缺失的部分。然而，我还没有找到一个好的方法来实现它。想知道是否有一种聪明的方法来防止单例（空洞）出现。谢谢！ - Tony Xu

好的，那么更好地描述您的问题是什么——您是否有一组nm/k形状和一个必须插入它们的顺序，并且想确定最佳放置位置，还是您一次只能得到一个形状，并且必须找出最佳放置位置，而不知道接下来会发生什么？也就是说，解决方案状态是否确定？ - Andrew Latham

同样地，正如我所说的，无论哪种情况下都可能无法避免出现漏洞。因此，你必须接受这一点。 - Andrew Latham

这似乎是一个多形瓷砖问题实例。http://en.wikipedia.org/wiki/Polyomino - Alien Life Form

Answer 3

关于孔洞问题，应该有一种简单的解决方法... 3！（对于k≤9而言；））

让我解释一下，每个块不仅与另一个或两个块相邻，而且还与“空位”相邻，这涉及到k的形状，你应该关心的是，这样的空位计数始终为k*2+2，因此k=1->4，k=2->6... k=9->20 对于k.length的每个项目，您知道它的位置对吧？在您的矩阵中，现在可以向每侧移动一步，并检查它是否为空格，如果是...请注意（空白）位置，如果您以这种方式勾勒出k，则将具有不同数量的空格，其小于或等于上述计算。

如果相等，则k中不能有任何孔洞，您可以继续， 如果少，则检查少多少，如果您错过了一个，则制成L形，如果您错过了两个，则可能有U形或T形（特殊情况k=9为S），您可以继续。

如果你错过了三个或更多，你需要进一步调查！现在检查你暂时记录的每个空白位置的相邻块，如果每个这样的空白位置的数字小于或等于3，则你没有洞并且可以继续，但是只要有一个以上的空白位置有3个相邻块，你就会在k中有一个洞。

对于k=10，很难做到这一点，但是对于九个以下的数字，这些简单的规则可以防止你的k对象出现洞。

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

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

*多米诺骨牌棋问题是指如果在棋盘上放置31个多米诺骨牌（2x1块），是否可以在棋盘上放置2个棋子（8x8）。（答案：如果一个在白色上，另一个在黑色上，你可以；否则你不能）

- itsid