完美搭配上的完美搭配
[编辑 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 正方形四联骨牌填充它。