使用2 x 1和1 x 2多米諾來平鋪W x H網格的方法數量？

Question

寫一個程序

我知道如何解決該作爲輸入的寬度，W和高度H的網格和輸出的不同方式的數量以拼貼的W-通過-H網格（2×1）骨牌3×N網格的問題，但寫這個遞歸公式對我來說太難了！

我不知道該怎麼做！

我創建了兩個函數F（n） - 對於3 x N的不完整拼貼方式，拼貼到N和S（n）的完整方式！但是，這裏的高度是可變的，我想不出什麼

限制：（0≤的W + H≤22）

Answer 1

這是引擎蓋下的DPish。這個想法是IVlad's：回憶與memoization。

memo = {} 


def count_tilings_recursive(uncovered): 
    if len(uncovered) & 1: 
     return 0 
    if not uncovered: 
     return 1 
    if uncovered not in memo: 
     i, j = min(uncovered) 
     memo[uncovered] = count_tilings_recursive(uncovered - {(i, j), (i, j + 1)}) + count_tilings_recursive(uncovered - {(i, j), (i + 1, j)}) 
    return memo[uncovered] 


def count_tilings(m, n): 
    return count_tilings_recursive(frozenset((i, j) for i in range(max(m, n)) for j in range(min(m, n)))) 


print(count_tilings(18, 4)) 

這裏的訣竅是保持狀態的數量不被炸燬。首先，我們總是選擇最左邊然後最上面的方形來覆蓋，使得局部覆蓋可以被描述爲最左上方的連續覆蓋正方形的數量，接下來是部分覆蓋的＃個箭頭，總計最多（#rows * #columns + 1）* 2 ^＃行狀態。其次，我們定位網格，使得至少有與行相同數量的列，爲有趣的計算（因爲11乘以11是微不足道的）將後者數字限制爲10。

Answer 2

有這些各種各樣的問題，一個相當不錯的，一般的方法：

1）計算前幾個值。

0 1 0 1 0 1 
1 2 3 5 8 13 
0 3 0 11 0 41 
1 5 11 36 95 281 
0 8 0 95 0 1183 
1 13 41 281 1183 6728 

2）在整數序列在線百科全書中搜索這些值。您可以通過輸入串聯的antidiagonals來搜索一個正方形數組，或者您可以對一些大的術語進行無序搜索。成功：https://oeis.org/A099390其中包括涉及餘弦的產品公式。

據我所知，直接通過動態編程來做這件事並不是一個特別好的方式，比如說在最小維數中少於指數級的許多狀態。與一些高等數學有聯繫。請參閱OEIS條目或Wikipedia的參考文獻。

---

Kasteleyn的餘弦乘積公式可以用精確的算術實現。事實上，它可以使用動態編程來完成。

2 cos x = e^ix + e^-ix 

所以，

(4+2 cos 2pi j/(w+1) + 2 cos 2pi k/(h+1)) 

在範圍Kasteleyn的產品1 < = j的< = W/2，1 < = K < = H/2可以在z=e^i 2pi/((w+1)*(h+1))被寫爲一個多項式，因爲z ^（（w + 1）*（h + 1））= z^0，所以可以計算指數mod (w+1)*(h+1)。多項式的乘積可以使用動態規劃進行計算，其中您記錄從0到(w+1)*(h+1)-1之間的每個n的z^n的係數。

// part of a C# implementation using a custom CircularVector class 
using System.Numerics; // BigInteger 

CircularVector cv = new CircularVector(w, h); 
cv.setToOne(); 

for (int i = 1; i<=w/2; i++) 
    for (int j = 1; j <= h/2; j++) 
     cv = cv.multiplyWith(new CircularVector(w, h, i, j)); 

結果是高達(w+1)*(h+1)項的和，度小於沿z (w+1)*(h+1)的多項式。例如，當w = 3，h = 4時，我們得到

{18, 1, 0, 1, 5, 8, 0, 1, 5, 1, 2, 1, 5, 1, 0, 8, 5, 1, 0, 1} 
= 18 + z + z^3 + 5z^4 + 8z^5 + z^7 + 5z^8 + z^9 + 2 z^10 + ... 

有必要找到等於這個多項式z的整數。爲此，我們可以將多項式除以cyclotomic polynomialPhi((w+1)*(h+1))。

// part of a C# implementation 

public static BigInteger[] cyclotomic(int n) 
{ 
    BigInteger[] working = nthRoots(n); // x^n - 1 

    for (int i = 1; i<n; i++) 
     if (n % i == 0) 
      working = polynomialExactDivision(working, cyclotomic(i)); 

    return working; 
} 

除以分圓多項式的餘數是計算矩形的多米諾骨牌的數量的（大）整數。這花了0。在一個處理器上運行014秒來計算20x20平方的傾斜數1269984011256235834242602753102293934298576249856，這與OEIS A004003中的值一致。這個計算可以在O（w^2h^2）BigInteger加法中完成，因爲您執行的是大小爲5倍的因子的多項式的wh乘法。

Answer 3

在代碼中編寫不同狀態之間的關係。高度爲2的情況相當於斐波那契數列。具有高度3的情況可以用具有九個相互遞歸序列的公式（有點乏味！）來編寫，或者等同於具有大小爲9的向量的線性遞歸。

而對於H>=4，請看看這個article。 Fibreacci Quarterly，18.1（1980），24-27。關於用多米諾骨牌鋪砌矩形的注意事項，斐波那契季刊，18.1（1980），24-27。

從n * 2電網的情況開始。填寫方法的數量是第Fibonacci數。爲什麼？因爲有兩種方法可以在右端完成網格，可以使用一個垂直多米諾骨牌或兩個水平多米諾骨牌。

另一種看到它的方法是從一個空格開始，並從左到右填充它。考慮到這一點，我們可以根據它們的「輪廓」類型對所有可能的不完整網格進行分組，即右側的邊界。

例如，對於H=2情況下，有兩種類型的配置文件，以及用於H=3，有9種類型的配置

的（即從圖2中的文章中）。

對於一般情況，使用H >= 2，我們預先計算配置文件列表。每個配置文件可以由兩個位掩碼編碼。請注意，第一個不應該代表整列，以表示沒有歧義。

要枚舉配置文件類型，同時將它們鏈接在一起，我們嘗試將一個多米諾骨牌水平放置，然後垂直放置在可用的最左側最低單元格中。這會生成另一個配置文件，如果它是新的，我們將添加到列表中。這樣，每個配置文件最多可鏈接到兩個配置文件。

爲H請參見下面的代碼，爲其他的選擇。這個過程爲我們提供了一個遞歸「公式」，用於填充r多米諾骨牌的不完整網格與填充了r+1多米諾骨牌的網格之間的遞歸「公式」。這不是一個真正的公式，它編碼在next_profile字典中。這篇文章中的公式爲(1.1)，相當於H=3。

from collections import defaultdict 


def disambiguation(a,b): 

    if a == (1<<H) - 1: 
     return disambiguation(b,0) 
    return (a,b) 

def generate_next_profile(): 

    global next_profile 
    next_profile = {}  
    q = [(0,0)] 
    done = {(0,0): True} 
    while q != []: 
     a,b = q.pop(0) 
     next_profile[(a,b)] = [] 
     i = 0 
     while i < H and a & 1<<i != 0: 
      i += 1 
     if i+1 < H and a & 1<<(i+1) == 0: 
      c, d = disambiguation(a | 1<<i | 1<<(i+1), b) 
      next_profile[(a,b)].append((c,d)) 
      if (c,d) not in done: 
       q.append((c,d)) 
       done[(c,d)] = True 
     c, d = disambiguation(a | (1<<i), b | (1<<i)) 
     next_profile[(a,b)].append((c,d)) 
     if (c,d) not in done: 
      q.append((c,d)) 
      done[(c,d)] = True 


def count_it(_W, _H): 
    W = _W 
    H = _H 
    result = 0 
    if W * H % 2 == 0: 
     u = 0 
     v = 1 
     num = [{(0,0): 1}, {}] 
     n_steps = W * H // 2 
     for step in range(n_steps): 
      num[v] = defaultdict(int) 
      for key, value in num[u].items(): 
       for pair in next_profile[key]: 
        num[v][pair] += value 
      u, v = v, u 
     result = num[n_steps % 2][(0,0)] 
    return result 


WMAX = 10 
HMAX = 10 

for W in range(1, WMAX): 
    for H in range(1, HMAX): 
     generate_next_profile() 
     res = count_it(W, H) 
     print(res, end = "\t") 
    print()