algorithm - 关于多米诺骨牌棋盘的平铺数

Question

多米诺骨牌对棋盘的部分平铺是将多米诺骨牌放置在棋盘上，使得没有两个多米诺骨牌重叠。多米诺骨牌平铺棋盘是一种部分平铺，其中棋盘的每个方格都被一些多米诺骨牌覆盖。

我感兴趣的问题如下:多米诺骨牌的 $N$ 乘 $N$ 棋盘的平铺数是多少？

事实证明，$M$ 乘 $N$ 棋盘 b 多米诺骨牌的拼贴数实际上有一个明确的公式:

https://wikimedia.org/api/rest_v1/media/math/render/svg/1bc328b90d68fd765e2666ad0c62bb42b2e2bd10

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

我创建了一个名为 number_of_tilings(partial_tiling) 的函数，它接受棋盘的部分平铺并输出用多米诺骨牌覆盖未覆盖方 block 的方法数量，这样我们最终得到一个平铺。

我创建了一个名为 uncovered_square(partial_tiling) 的辅助函数，它接受部分平铺并输出平铺中最左上角未覆盖的方 block ，如果不存在这样的方 block ，则输出 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_horizo​​ntal。同样我们定义 t_vertical。最后我们计算 number_of_tilings(t_horizo​​ntal)+number_of_tilings(t_vertical)。

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

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

---

所以我的问题是还有哪些其他可能的算法存在或者可以优化暴力算法？

Answer 1

有一个非常简单的动态规划解决方案，运行时间复杂度为 O(N*2^2N) 或更短:

1. 生成所有可能的填充第一行的方法(小于 2^N)。

2. 由于多米诺骨牌只有 2 个方格长，因此其效果只会传播到第二行。第二行的可能配置少于 2^N 种。计算每一种有多少种生成方式。

3. 类似地，通过填充前两行产生第三行的 <= 2^N 种配置，依此类推。给定通过填充前 m 行剩余的生成每个配置的方法数，您可以计算在 O(2^2N) 或更短时间内通过填充前 m+1 行剩余的生成每个配置的方法数。

4. 对于通过填充前 N-1 行生成的每个配置，最多可以有 1 种方法来填充最后一行。将生成每个配置的方法数加起来，在最后一行只留下偶数长度的间隙，这就是您的答案。

在一个代码紧凑的好盒子上，我希望 N=16 时这需要不到一分钟的时间。我可以想出很多方法来让它更快一点，但没有什么能在 O(2^N) 之下