關於用多米諾骨牌劃分棋盤的次數

Question

用多米諾骨牌對棋盤進行部分拼貼是在棋盤上放置多米諾骨牌，使得沒有兩個多米諾骨牌重疊。由多米諾骨牌拼成的棋盤是局部拼貼，棋盤上的每個方格都被多米諾骨牌覆蓋。

我感興趣的問題如下：多米諾骨牌的$ N $ by $ N $ chessboard的起伏數是多少？

原來居然還有一個$ M $的$ N $棋盤b多米諾骨牌的拼接數量的明確公式：

https://wikimedia.org/api/rest_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_horizo​​ntal。同樣我們定義t_vertical。最後我們計算number_of_tilings（t_horizo​​ntal）+ number_of_tilings（t_vertical）。

number_of_tilings的初始輸入是$ N $ by $ N $ chessboard，沒有多米諾骨牌放在它上面。

這個算法非常快速地爲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行生成的每個配置，最多可以有一種方法填充最後一行。把生成每個配置的方法加起來，在最後一行中只留下等長的空白，這就是你的答案。

在密碼很好的盒子上，我預計N = 16的時間不會超過一分鐘。 我可以想到一堆方法，使其更快一點，但沒有得到O（2^N）

Answer 2

這個問題已經在文獻中研究，似乎並不是很容易和直接。例如看看

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

上面的鏈接提供了一個多項式時間算法來計算。

事實上，它首先將其轉化爲圖形問題，即特殊圖類中完美匹配的數量。然後爲該圖定義一個鄰接矩陣，並計算該矩陣的永久性，這相當於完​​美匹配的數量。

計算矩陣的永久性在一般圖中很難。但是在這個特定的圖表或平面圖表中，可以解決這個問題。這部分的想法雖然不是很直觀。