如何生成正方形的多米诺骨牌平铺？

Question

简要说明：

我试图用多米诺骨牌或者换句话说，用2x1和1x2瓷砖生成正方形的瓷砖。

有时我的算法会以某种方式放置垂直磁贴，这使得无法填充最后一行。

我目前的方法是用0初始化网格（例如8x8网格）。我在网格中用1表示水平平铺的左半部分，用2表示右半部分。

因此，垂直瓷砖的上半部分是3，下半部分是4。

然后我从左到右遍历网格的每一行，在0处放置一个平铺：

• 每当我在网格的右侧边缘或右侧的空间不是0时，我都会放置一个垂直图块（3）。
• 当我在底部边缘时，我只能放置水平瓷砖。
• 当以上都没有设置值时，我将随机值（1或3）。

每当我放一个瓷砖（1或3）时，我也相应地放相应的一半作为网格的相邻空间。假设我在（i， j）放一个1，然后在（i， j 1）放一个2。

StoneMatrix = int[8][8];

for (int i = 0; i < StoneMatrix.length; i++) {
    for (int j = 0; j < StoneMatrix.length; j++) {
        if (StoneMatrix[i][j] != 0){
            //field already set as a tile
            continue;
        }

        if (i == StoneMatrix.length - 1) {
            //bottom row
            StoneMatrix[i][j] = 1;
            StoneMatrix[i][j + 1] = 2;
            continue;
        }

        if (j == StoneMatrix.length - 1) {
            //right edge
            StoneMatrix[i][j] = 3;
            StoneMatrix[i + 1][j] = 4;
            continue;
        }

        if (StoneMatrix[i][j + 1] != 0) {
            //field to the right taken.
            StoneMatrix[i][j] = 3;
            StoneMatrix[i + 1][j] = 4;
            continue;
        }

        StoneMatrix[i][j] = putOneOrThreeRandomly();
        putCorrespondingAdjacentTile();
    }
}

我觉得必须有一个简单或更容易的方法来生成这样的瓷砖，但我还没有找到。我要找的要么是某个源代码，其中描述了这样一个生成算法，要么是一个简单的解决方案，可以修复我的错误。

Answer 1

我通过将布尔值设置为true来“解决”这个问题，每次我达到无法正确填充网格的状态时。

然后在生成方法的末尾，如果布尔值为false，则网格有效，如果布尔值为true，则重新启动该方法。我认为这基本上是一个肮脏的“试错”。

这不是我想要的解决方案，但它确实有效。所以我把这个问题留待讨论。

Answer 2

通过带有2x1多米诺骨牌的m棋盘创建任意n的随机最大平铺。当n*m为偶数时，平铺将是完美的。

考虑棋盘上的黑白方块。多米诺骨牌必须同时覆盖白色和黑色正方形。因此，如果存在某种完美的平铺，则可以将解决方案转换为如下图：每个棋盘成为一个顶点，如果多米诺平铺覆盖两个相邻的平铺，则两个顶点相连。这将导致一个二分图（所有边都有一个白色和一个黑色顶点）和（最大）匹配图。

因此，给定任何大小的网格（或任何形状），如果我们能够解决二部图中的最大基数匹配问题，我们可以将解决方案转换为多米诺平铺。

要解决上述图问题，请将其转换为最大流问题，并使用Ford Fulkerson进行求解。将源节点连接到所有白色平铺，将汇节点连接到所有黑色平铺。只有当他们是棋盘格上的邻居时，白色方块才指向黑色方块。使用所有边的容量为1进行求解。节点之间利用的边表示将在那里放置domino。

考虑一个2行深4列宽的棋盘。白色方块是{0,1,2,3}，黑色方块是{4,5,6,7}

+---+---+---+---+
| 0 | 4 | 1 | 5 |
+---+---+---+---+
| 6 | 2 | 7 | 3 |
+---+---+---+---+

现在假设我们有两个额外的节点，8源和9接收器。然后找到Max流的图表如下所示。请注意，所有边的容量为1。

0: 4, 6
1: 4, 5, 7
2: 4, 6, 7
3: 5, 7
4: 9
5: 9
6: 9
7: 9
8: 0, 1, 2, 3

在运行Ford-fulkerson之后（使用随机DFS来获得有趣的解决方案——如果您每次都想要一个无聊的逐行解决方案，请使用BFS），我们可能会发现使用了以下边。请注意，涉及源/接收器节点的边已被省略，因为它们对于重建平铺没有用。

0-4
2-6
1-7
3-5

最后，这对应于以下平铺

+-----+---+---+
| 0 4 | 1 | 5 |
+-----+   |   |
| 6 2 | 7 | 3 |
+-----+---+---+

我还在这里用Java创建了一个概念验证：https://github.com/forsythe/domino_tiling.如果您想看到它的实际运行，这里有一个16x16输出：