多米诺骨牌对棋盘的部分平铺是在棋盘上放置多米诺骨牌，使两个多米诺骨牌不重叠多米诺骨牌对棋盘的平铺是一种局部平铺，棋盘的每一个方格都被多米诺骨牌覆盖。
我感兴趣的问题是：多米诺骨牌的棋盘数目是多少？
事实上，有一个明确的公式来计算一张价值百万美元的棋盘b多米诺骨牌的数量：
https://wikimedia.org/api/rest_v1/media/math/render/svg/1bc328b90d68fd765e2666ad0c62bb42b2e2bd10
我对这个问题的算法方法感兴趣。我们只需要考虑$N$偶数的情况（对于$N$奇数，瓷砖的数量显然是$0$）我唯一想到要解决的算法是蛮力递归。
我创建了一个名为number_of_tillings（partial_tilling）的函数，它接受棋盘的部分平铺，并输出用多米诺骨牌覆盖未覆盖的正方形的方法数，这样我们最终得到平铺。
我创建了一个辅助函数称为unBuffEdFixSuffic（PultaluthTILLIN），它接受了一个部分的平铺，并输出了平铺中的最左边的未覆盖的正方形，或者如果没有这样的正方形，则是错误的。
递归地定义了_平铺（部分_平铺）的函数编号：如果未覆盖的_平方（部分_平铺）输出为False，则_平铺（部分_平铺）的编号=1，因为部分_平铺实际上是一个正确的平铺否则，uncovered_square（partial_tiling）将输出一些正方形S。我们将多米诺骨牌水平放置在正方形S上（如果可能），从而生成新的partial tiling t_horizontal同样，我们定义t_垂直最后，我们计算瓦片数（t_水平）+瓦片数（t_垂直）。
瓦片数量的初始输入是一个n$x n$chessboard，上面没有放置多米诺骨牌。
这个算法对于n=2,4,6给出了正确的答案，但是对于n>=8则非常慢（超指数时间）。
因此，我的问题是，还有其他可能的算法存在，或者蛮力算法能被优化吗？
最佳答案
有一个非常简单的动态编程解决方案可以运行在O（N*2^2N）或更好的版本中：
生成填充第一行的所有可能方法（小于2^n）。
由于多米诺骨牌只有两个正方形长，所以这种效应只会传播到第二排第二行的可能配置少于2^n。计算有多少种方法可以生成每一个。
类似地，通过填充前两行产生的第三行的<=2^N配置，依此类推给定通过填充前m行来生成每个剩余配置的方法，您可以通过在o（2^2n）时间内填充前m+1行来计算生成每个剩余配置的方法的数量或更好。
对于通过填充前N-1行生成的每个配置，最多可以有一种方法填充最后一行把生成每一个配置的方法加起来，在最后一行中只留下相等的长度间隔，这就是你的答案。
在一个代码紧凑的好框中，我希望N=16的时间不到一分钟。
我能想出一堆方法来加快速度，但是没有什么方法能低于O（2^N）
关于algorithm - 关于多米诺骨牌的棋盘平铺数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41433365/