我正在编写一个程序，该程序需要快速检查一个连续的空间区域是否可以被四联体（任何类型，任何方向）填充。我的第一次尝试是简单地检查正方形的数量是否可以被 4 整除。但是，仍然会出现这样的情况：
如您所见，即使这些区域各有 8 个方格，也无法用四联骨牌平铺。
我已经考虑了一会儿，我不知道如何进行。在我看来，“枢纽”广场，或通向两个以上“隧道”的广场，是实现这一目标的关键。在上面的示例中很容易，因为您可以快速计算每个此类隧道中的空间——第一个示例中的 3、1 和 3，以及第二个示例中的 3、1、1 和 2——并确定不可能继续由于每条隧道都需要连接到中心广场以安装四联牌，这对所有人来说都是不可能的。但是，您可以有更复杂的示例，例如：
......简单的计数技术不起作用。（至少，据我所知。）更不用说更多的开放空间，中心广场的数量很少。另外，我没有任何证据证明中心方块是这里唯一的技巧。据我所知，可能还有很多其他不可能的情况。
某种搜索算法（A*？）是解决这个问题的最佳选择吗？我非常关心数百甚至数千个正方形的性能。该算法需要非常有效，因为它将用于实时平铺（或多或少），并在浏览器中使用。
[编辑 2014 年 10 月 28 日：正如 pix 所注意到的，这种方法从不尝试使用 T-tetrominoes，因此比我想象的更有可能给出不正确的“否”答案......]
这不能保证任意形状的解决方案，但它会在大多数情况下快速且良好地工作。
想象一个图，其中每个白色方块都有一个顶点，当且仅当它们对应的白色方块相邻时，两个顶点之间有一条边。（因此每个顶点最多可以接触 4 条边。）该图中的完美匹配是边的子集，使得每个顶点恰好接触子集中的一条边。换句话说，它是一种将相邻顶点配对的方式——或者换句话说，是白色方块的多米诺骨牌。稍后我将解释如何找到看起来很随机的完美匹配；现在，让我们假设它可以完成。
然后，从这个多米诺骨牌拼贴开始，我们可以重复匹配过程，将多米诺骨牌粘合成四肢骨！第二次的唯一区别是，我们不是每个白色方块都有一个顶点，而是每个多米诺骨牌都有一个顶点。并且因为每当两个多米诺骨牌相邻时我们都必须添加一条边，所以一个顶点现在可以有多达 6 条边。
第一步（多米诺拼贴）步骤不能失败：如果给定形状的多米诺拼贴存在，那么将找到一个。但是，第二步（将多米诺骨牌粘合在一起成为 tetrominos）可能会失败，因为它必须与已经确定的多米诺骨牌拼贴一起工作，这可能会限制它的选择。这是一个示例，展示了相同形状的不同多米诺拼贴如何启用或破坏四格拼贴：
AABCDD --> XXXYYY Success :)
BC XY
AABBDD --> Failure.
CC
为了生成多米诺骨牌的随机模式，可以给图中的边赋予随机权重，从而解决最大加权匹配问题。权重应该在 [1, V/(V-2)) 的范围内，以保证通过不配对某些顶点永远不可能获得更高的分数。该图实际上是二分图，因为它不包含奇数长度的循环，这意味着对于最大加权二分匹配问题的更快的 O(V^2*E) 算法可用于此步骤。（对于第二个匹配问题，情况并非如此：一个多米诺骨牌可以接触到另外两个相互接触的多米诺骨牌。）
如果第二步未能找到一组完整的 tetrominos，则要么没有解决方案*，要么使用不同的多米诺骨牌解决方案是可能的。您可以尝试随机重新加权用于查找多米诺平铺的图形，然后重新运行第一步。或者，您可以只增加有问题的多米诺骨牌的权重，而不是从头开始完全重新加权，然后再试一次。
* 对于一个边长相等的正方形，我们知道一个解决方案总是可能的：只需用 2x2 正方形四联骨牌填充它。