Tetromino空间填充：需要检查是否可能

Question

我正在编写一个程序，需要快速检查连续的空间区域是否可以被四格骨牌（任何类型、任何方向）填充。我的第一次尝试是简单地检查平方数是否能被 4 整除。但是，这样的情况仍然可能会出现：

\n\n

\n

\n\n

正如您所看到的，即使这些区域每个都有 8 个方格，它们也不可能用四格骨牌平铺。

\n\n

我想了一会儿，但不知道如何继续。在我看来，“枢纽”广场，或者通向两个以上“隧道”的广场，是关键。在上面的示例中很容易，因为您可以快速计算每个此类隧道 \xe2\x80\x94 3、1 和 3 在第一个示例中的空间，以及在第二个示例中的 3、1、1 和 2 \xe2\x80\x94 并确定不可能继续进行，因为每个隧道都需要连接到中心广场以安装四格骨牌，而这对于所有隧道来说都是不可能发生的。但是，您可以有更复杂的示例，如下所示：

\n\n

\n\n

...简单的计数技术根本不起作用。（至少，据我所知。）更不用说更多的开放空间和很少数量的中心广场了。另外，我没有任何证据表明中心方块是这里唯一的技巧。据我所知，可能还有很多其他不可能的情况。

\n\n

某种搜索算法（A*？）是解决这个问题的最佳选择吗？我非常关心数百甚至数千个方块的性能。该算法需要非常高效，因为它将用于实时平铺（或多或少），并且在浏览器中。

\n

Answer 1

完美搭配上的完美搭配

[编辑28/10/2014：正如pix所注意到的，这种方法从不尝试使用T-tetrominoes，所以它比我想象的更有可能给出错误的“否”答案......]

这不能保证任意形状的解决方案，但在大多数情况下它会快速且良好地工作。

想象一个图，其中每个白色方块都有一个顶点，并且当且仅当它们对应的白色方块相邻时两个顶点之间有一条边。（因此，每个顶点最多可以接触 4 条边。）该图中的完美匹配是边的子集，使得每个顶点恰好接触子集中的一条边。换句话说，它是一种将相邻顶点配对的方式，或者换句话说，是白色方块的多米诺骨牌拼接。稍后我将解释如何找到看起来随机的完美匹配；现在，我们假设这是可以做到的。

然后，从这个多米诺骨牌开始，我们可以重复匹配过程，将多米诺骨牌粘在一起形成四格骨牌！第二次唯一的区别是，我们不再为每个白色方块一个顶点，而是为每个多米诺骨牌一个顶点；因为只要两个多米诺骨牌相邻，我们就必须添加一条边，所以一个顶点现在可以有多达 6 条边。

第一步（多米诺骨牌平铺）不能失败：如果给定形状的多米诺骨牌平铺存在，那么就会找到一个。然而，第二步（将多米诺骨牌粘合在一起形成四格骨牌）可能会失败，因为它必须与已经决定的多米诺骨牌一起使用，这可能会限制其选择。下面的示例显示了相同形状的不同多米诺骨牌瓷砖如何启用或破坏四格骨牌瓷砖：

AABCDD   -->   XXXYYY   Success :)
  BC             XY

AABBDD   -->   Failure.
  CC

解决最大匹配问题

为了生成随机的多米诺骨牌图案，可以给图中的边赋予随机权重，从而可以解决最大加权匹配问题。权重应在 [1, V/(V-2)) 范围内，以保证永远不可能通过不配对某些顶点来获得更高的分数。该图实际上是二分图，因为它不包含奇数长度循环，这意味着最大加权二分匹配问题的更快 O(V^2*E) 算法可用于此步骤。（对于第二个匹配问题，情况并非如此：一张多米诺骨牌可以碰触另外两块互相碰触的多米诺骨牌。）

如果第二步未能找到一组完整的多米诺骨牌，则要么无法解决*，要么可以使用另一组多米诺骨牌来解决。您可以尝试随机重新加权用于查找多米诺骨牌平铺的图表，然后重新运行第一步。或者，您可以增加有问题的多米诺骨牌的重量，然后重试，而不是从头开始完全重新调整重量。

* 对于边长为偶数的普通正方形，我们知道解决方案总是可能的：只需用 2x2 的方形方块填充它即可。