论多米诺骨牌对棋盘倾斜的次数

Question

棋盘上的多米诺骨牌是将多米诺骨牌放置在棋盘上，使两块多米诺骨牌不重叠。用多米诺骨牌打棋盘是一块局部的瓷砖，棋盘的每一个方格都被一些多米诺骨牌所覆盖。

我感兴趣的问题是：，$N$由$N$棋盘向多米诺骨牌倾斜的次数是多少？

事实证明，实际上有一个明确的公式，表明$M$的倾斜数由$N$棋盘b多米诺骨牌决定：

v1/media/math/render/svg/1bc328b90d68fd765e2666ad0c62bb42b2e2bd10

我对这个问题的算法方法很感兴趣。我们只需要考虑$N$偶数的情况(对于$N$奇数，倾斜的数目显然是$0$)。我想要解决的唯一算法是蛮力递归。

我创建了一个名为number_of_tilings(partial_tiling)的函数，它接受棋盘的部分贴图，并输出用多米诺骨牌覆盖无盖方块的方法，这样我们就可以得到一块瓷砖。

我创建了一个名为uncovered_square(partial_tiling)的辅助函数，它接受部分平铺并输出平铺中最左边的方块，如果没有这样的方块，则输出False。

函数number_of_tilings( partial_tiling )是递归定义的:如果uncovered_square(partial_tiling)输出False，那么number_of_tilings(partial_tiling)=1，因为partial_tiling实际上是一个正确的平铺。否则，uncovered_square(partial_tiling)输出一些平方S，我们在平方S(如果可能的话)水平放置一个支配线，从而产生一个新的局部平铺t_horizontal。类似地，我们定义了t_vertical。最后，我们计算了number_of_tilings(t_horizontal)+number_of_tilings(t_vertical).

number_of_tilings的初始输入是$N$棋盘上的$N$，上面没有多米诺骨牌。

该算法对N=2,4,6快速给出了正确的答案，但对于N>=8则是非常慢的(超指数时间)。

，所以我的问题是，还有其他可能的算法，还是可以优化蛮力算法？。

Answer 1

有一个运行在O(N*2^2N)或更高版本中的非常简单的动态规划解决方案：

1. 生成填充第一行的所有可能方法(小于2^N)。
2. 因为多米诺骨牌只有两个正方形长，所以它的效果只会传播到第二排。第二行的可能配置少于2^N。计算出产生每种方法的方法。
3. 类似地，第三行的<= 2^N配置是通过填充前2行产生的，依此类推。给定通过填充前m行生成每个配置的方式#，您可以通过在O(2^2N)或更长时间内填充第一个m+1行来计算生成每个配置的方法数。
4. 对于每个通过填充第一个N-1行而产生的配置，最多只能有1种方式来填充最后一行。把生成每一种配置的方式加起来，在最后一行中只留下等长的空白，这就是你的答案。

在一个代码紧凑的好盒子上，我希望N=16所用的时间不到一分钟。

Answer 2

这个问题已经在文献中研究过了，看起来并不是很容易和直接的。看一看

http://www.math.cmu.edu/~bwsulliv/domino-tilings.pdf

上面的链接提供了一个多项式时间算法来计算它。

实际上，它首先将其转化为一个图问题，即特殊图类中的完全匹配数。然后定义了该图的邻接矩阵，并计算了该矩阵的永久值，该矩阵等价于完全匹配的个数。

在一般图中，矩阵的永久值的计算是很困难的。但是在这个特殊的图中，或者在平面图中，它是有可能解决的。然而，这个部分的想法并不是很直观。