3 骨牌鋪磚問題 Domino Tilings

骨牌鋪磚問題：給定兩個整數 \(m, n\)，並考慮大小為 \(m\times n\) 的矩形棋盤。其中某些格子有障礙物，不能放置骨牌。請問有多少種方法使用 \(1\times 2\) 骨牌能恰好鋪滿這個 \(m\times n\) 的棋盤所有不含障礙物的地方？

範例

若 \(m=3\)、\(n=4\)，且該矩形沒有任何障礙物，那麼答案是 \(11\)。

方法零：空棋盤的公式解

\[\prod_{j=1}^m\prod_{k=1}^n \left(4\cos^2\frac{j\pi}{m+1}+4\cos^2\frac{k\pi}{n+1}\right)^{1/4}\]

這是個非常優雅的數學解，一生請至少要想通過一次它的證明！ 不過呢，若依此公式實際計算該數值，則這個方法存在著滿滿的精確度問題，大家不妨實作看看、細細體會。

方法一：枚舉答案系列

我們可以使用基於深度優先搜索 (Depth First Search) 的試誤法： 每一次找一個還沒有被填滿的空格，然後決定要讓骨牌蓋直的還是橫的，如果能放就接著遞迴下去。 由於每次做決策會覆蓋兩格，因此遞迴深度不超過 \(mn/2\)、且遞迴樹上每個節點最多只會分出兩個子問題。 因此，我們得知整個遞迴樹上的節點數量為 \(O(2^{mn/2})\)。

但是，這麼一來我們就能聲稱時間複雜度是 \(O(2^{mn/2})\) 了嗎？可能會不夠充分。 問題出在哪裡呢？原因是在每一次遞迴呼叫時，『找一個還沒被填滿的空格』這個步驟的執行時間可能不是固定的，最壞情形甚至可能是 \(O(mn)\)。 好加在，若此時我們使用一個 hashmap + linked list 來存放當前沒有被覆蓋的所有格子座標，就能夠保證每次找到一個空格需要的時間是 \(O(1)\)。 於是就能正確地達到 \(O(2^{mn/2})\) 的時間複雜度啦。

分法一之二：預判剪枝

要搜，就要好好地搜。到達一個子問題（也就是鋪到一半的棋盤）時，若有某種方法幫我們快速判斷剩下的盤面是否有解，那麼我們就可以透過預判剪枝的方法，將時間複雜度由 \(O(2^{mn/2})\) 降到 \(O(TDK)\) 時間，其中 \(T\) 是判斷盤面是否有解的時間複雜度、\(D=O(mn)\) 是遞迴深度、\(K\) 則是鋪磚方法的總數。 至於 \(TDK\) 和 \(2^{mn/2}\) 之間要如何比較呢？這就要端看『判斷剩餘盤面是否有解』的演算法、與『實際鋪滿盤面的解數』了。

若我們使用最陽春的二分圖最大匹配演算法來判斷是否有解，那麼我們有 \(T=O(mn\sqrt{mn})\)。 此外，若 \(m=n\) 的時候，依照 Kasteleyn、Fisher 以及 Temperley 等人提出的算式推導，可以推知鋪滿盤面的解數大約是 \(c^{mn/2}\)，其中 \(c = e^{2G/\pi} \approx 1.79162\ldots\) 而這邊的數值 \(G\) 是卡塔蘭常數 (Catalan constant) \(\frac{1}{1^2}-\frac{1}{1^3}+\frac{1}{1^5}-\frac{1}{1^7}+\cdots\approx 0.915965\ldots\)。

於是，我們的演算法就從 \(O(2^{mn/2})\) 加速到 \(O^*(1.79163^{mn/2})\) 啦～

方法二：動態規劃系列

動態規劃 (dynamic programming) 是眾多演算法典範 (algorithmic paradigm) 當中數一數二重要的一種解題典範。 其核心概念首先在於正確地定義子問題、然後找出原問題與子問題之間的遞迴關係 (與邊界條件)、並且找出正確的解題順序。 說得更直接一些，便是將所有曾經計算過的子問題通通記錄下來，並重複利用以加速計算的一種方法。

而將動態規劃應用在鋪磚問題時，則會是一個訓練『子問題設計』很好的練習題目。 比方說，我們可以考慮以下這樣的想法。 假若我們硬生生地考慮矩形棋盤的左邊 \(k\) 行，那麼完全身處左邊 \(k\) 行之中的骨牌們會形成一種邊緣不完整的鋸齒狀棋盤。 我們觀察到，由於我們使用的是 \(1\times 2\) 大小的骨牌進行鋪磚，因此鋸齒的邊界，在每一列只有可能是平的或凹進去恰好一格。 其邊界情形只有 \(2^m\) 種（其中 \(m\) 是棋盤的列數）。 於是一個有趣的想法誕生了：我們可以考慮對於任意鋸齒的形狀 \((k, \text{邊界長相})\) 定義成『子問題』，並且令 \(dp(k, \text{邊界長相})\) 為使用 \(1\times 2\) 骨牌鋪滿這個鋸齒狀棋盤的方法數。我們要的答案就是 \(dp(n, \text{整條邊界平的})\) 之值。剩下來要考慮的，便是子問題 (或狀態) 的轉移了。

狀態壓縮

『邊界長相』是個難以言喻的東西。因此，在實作前我們會試著將它變成可以操作的形式。對這題來說算是相對簡單的：我們可以令平的邊緣為 \(1\)、凹進去的邊緣為 \(0\)。 這麼一來，『邊界長相』就可以被一個介於 \(0\) 到 \(2^m-1\) 之間的整數來表示了。以整數形式（通常是二進位）精簡地描述動態規劃的子問題的技巧，通常我們稱之為狀態壓縮。

以上面的圖樣為範例的話，若將每一橫列之狀態依序以 \(2^0, 2^1, \ldots, 2^{m-1}\) 表示，那麼我們可將該子問題描述為 \((k=, \text{邊界}=)\)。

狀態的轉移與時間複雜度分析

如果我們查看第 \(k\) 行、邊緣沒有凹進去的那些地方的骨牌們，則它們可能是橫的或直的。 若我們將這些邊界位置全部放置橫著的骨牌，那麼該情形下的骨牌總數是 \(dp(k-1, 2^m-1-邊界)\)（因為拿掉這些骨牌後，剛好形成一個少了一行、且邊界鋸齒剛好與原本的鋸齒形狀互補的長相）。若有些邊界地方被放置了豎著的骨牌，那麼有兩種方式可以考慮這些情形：

  • 第一種『暴力枚舉』：我們可以再次枚舉所有在該行放置若干豎著的骨牌的方法數，由於放法計數至多與費氏數列相同，因此至多有 \(O(\phi^n)\) 種情形需要枚舉。 結合狀態總數 \(O(n2^m)\)，從而得出整體動態規劃之時間複雜度為 \(O(n2^m\phi^n)\)。 (備註：這個時間複雜度比暴力法還糟糕呢！)
  • 第二種『另一層動態規劃』：如果只針對第 \(k\) 行的話，總是可以考慮『最後一個出現豎著放的骨牌的位置』。因此，我們可以拓展原本的子問題定義：令 \(dp(k, 邊界, r)\) 表示『把 \((k, 邊界)\) 這個形狀填滿骨牌時，在第 \(k\) 行裡頭允許出現豎著放的骨牌位置不得超過第 \(r\) 列』的時候，有幾種放置 \(1\times 2\) 的骨牌方法數。 在這樣的情形下，轉移就可以變成 \(O(1)\) 時間的（因為只要考慮第 \(k\) 行第 \(r\) 列的骨牌到底要橫著還是豎著放就可以；且當 \(r=0\) 的時候可以得知所有邊界處都是橫著放骨牌，就可以一次退一排了）。於是整體時間複雜度變成了 \(O(mn2^m)\)。

方法二之二：破碎化的拼貼

與其一口氣關注一整行，如果一次只考慮一格的動態規劃設計，在遞迴轉移的時候反而變得更單純些，實作上也變得相當精簡。這個方法的時間複雜度也是 \(O(mn2^m)\)。 由於筆者稍微偷懶了一下的關係，不介意的話還請大家參考筆者曾經寫過的 透過鋪磚塊問題來看看動態規劃可運用之處！ 鐵人賽文章。

方法三：使用圖論轉化問題

我們可以使用圖論的想法來解決這個問題！ 簡單來說，我們可以讓每一個棋盤上的沒有障礙物的格子都變成圖上的一個點、並且將相鄰的格子連上一條邊。 這樣建立出來的圖為 \(G\)，其點數恰好為空格的數量、而每條邊就對應著可以放置骨牌的位置。 一個成功的骨牌鋪法，便對應了圖 \(G\) 上面的一組完美匹配 (perfect matching)。

而尋求骨牌鋪磚的鋪法數量，就可以轉化到圖 \(G\) 上面完美匹配的數量了。 對於一般的圖 \(G\)，這個問題其實在計算上是非常困難的 (♯P-Complete)。 不過呢，我們建立出來的這個圖 \(G\)，是個平面圖 (planar graph)，在平面圖上則有個相當美妙的 Fischer-Kasteleyn-Temperley (FKT) 演算法來計算完美匹配的數量。

Fischer-Kasteleyn-Temperley 演算法

這個在平面圖上計算完美匹配數量的 FKT 演算法意外地酷炫而且單純，但是要證明它的正確性需要一些有趣的線性代數小知識。 因此我們首先介紹這個演算法的步驟，然後再試圖證明它。

  • 第一步：先把圖 \(G\) 繪製在平面上，找出每一個面 (face)。
    • 此時我們可以先把『必定匹配的那些邊和點暫時拔掉』，所以剩下的每條邊都身處環中。
  • 第二步：找出圖 \(G\) 的任意一個生成樹 (spanning tree)，並且對生成樹上的所有邊隨意定向 (orientation)。
  • 第三步：重複以下步驟直到所有的邊都被定向為止：
    • 找出一個面，使得構成這個面的邊們，恰好只剩下一條邊 \(e\) 還沒被定向。
    • 定向這條邊，使得沿著這個面順時針走訪時，恰好有奇數條順向的邊。
  • 經過第三步以後，我們得到一個有向圖 \(G\)。我們建構一個帶有正負號的鄰接矩陣 (\((-1, 1, 0)\)-adjacency matrix) \(A\)，矩陣內 \((i, j)\) 位置的值根據邊 \((i, j)\) 的方向來決定：順向為 \(1\)、反向為 \(-1\)、沒有邊的時候是 \(0\)。
  • 我們要找的答案就是 \(A\) 的行列式值開平方根：\(\sqrt{\det(A)}\)。




這樣定義出來的矩陣 \(A\)，是一個斜對稱矩陣 (skew-symmetric)，在斜對稱矩陣上，其行列式值 \(\det(A)\) 恰好會等於普法夫值 (Pfaffian) \(\mathrm{pf}(A)\) 的平方。而根據每個面周圍的邊定向的情形，可以得知 \(A\) 的普法夫值的絕對值恰好等於圖 \(G\) 中完美匹配的數量。 上面的證明大家可以參考這份講義以及下面參考資料的投影片們囉！

參考資料