爲俄羅斯方塊提供的n塊不同的有效作品

Question

這是我朋友昨天問我的一個問題，我認爲這是他看到的一個採訪問題。規則很簡單，對於n=4，有5組不同的部分：

ooo 
o 

    o 
ooo 

oo 
oo 

oooo 

oo 
oo 

對於給定的n，你需要計算不同的件數。

通過disinct這意味着這四個是一樣的：

ooo o o o 
    o ooo o o 
     oo oo 

我失敗的時候n > 4，這個問題變得更加複雜，我甚至不知道它屬於哪個類型的問題，解決這個原因。它看起來像一個DFS，但你可以同時選擇多個指示。刪除重複也很重要。

Answer 1

下面是wiki

溶液的順序每個四角的n + 1可以通過添加一個正方形到n階的四角來獲得。這導致了用於感應生成多肽的算法。

最簡單地，給出n階多米諾列表，可以在每個可能位置的每個多米諾骨牌旁邊添加正方形，並且如果不是已經找到的一個副本，則將所得到的n + 1順序的多米諾骨牌添加到列表中;在排序和標記不應考慮的相鄰方塊的細化方面的改進減少了需要檢查重複的情況的數量。[9]這種方法可以用來列舉遊離或固定的多米諾骨牌。

由Redelmeier描述的一種更復雜的方法已被許多作者用作不僅計算多晶體（不需要存儲n階所有多米諾以便列舉n + 1階）的方法，但也證明了他們的數量上限。基本的想法是，我們從一個單一的方塊開始，並從那裏遞歸地添加方塊。根據具體情況，它可以從每n個正方形開始n次，也可以安排每次只計數一次。

最簡單的實現方式是每次添加一個方塊。從最初的正方形開始，從頂部順時針方向對相鄰的正方形編號1,2,3和4.現在選取一個介於1和4之間的數字，並在該位置添加一個正方形。對未編號的相鄰正方形進行編號，從5開始。然後，選取一個大於先前選取的數字的數字，然後添加該正方形。繼續選取大於當前平方數的數字，然後添加該平方，然後編號新的相鄰方格。當創建n個正方形時，創建了一個n-omino。

該方法確保每個固定的多米諾骨牌計數正好n次，每個起始方格一次。它可以進行優化，使它只計數一次，而不是n次。從最初的方塊開始，將其聲明爲多邊形的左下方。簡單地說，不要對位於同一行的較低行或正方形左側的任何正方形進行編號。這是Redelmeier描述的版本。

如果您希望計算免費的多米諾骨牌，那麼可以在創建每個n-omino後檢查對稱性。然而，分別生成對稱多米諾（用這種方法的一個變體）[11]更快[10]，所以用Burnside的引理來確定免費多米諾骨牌的數量。

Iwan Jensen發現了用於枚舉固定多米諾骨牌的最現代算法。[12]安德魯康威方法的一個改進，[13]它比以前的方法指數地更快（但是，它的運行時間仍然是指數n）。

Conway's和Jensen的轉移矩陣方法的版本都涉及計算具有一定寬度的多米諾數的數量。計算所有寬度的數字可得到多米諾骨牌的總數。該方法背後的基本思想是考慮可能的開始行，然後確定完成給定寬度的多邊形所需的最小平方數。結合使用生成函數，該技術能夠同時計數多個多米諾骨牌，從而使其運行速度比必須生成每個多米諾骨牌的方法快許多倍。

儘管運行時間非常優秀，但這種算法的優勢在於，該算法使用了指數級的內存（對於n大於50需要很多GB的內存），比其他方法編程要困難得多，而且目前還不能用於計算免費的多米諾骨牌。

對我來說，這就夠了。不過，我真正想要計算的是免費的多米諾骨牌的數量，但似乎沒有簡單的解決方案。如果我在採訪中被問到這個問題，我會給出上面提到的算法來計算固定多米諾骨牌的數量，然後刪除重複的數字以計算免費的多米諾骨牌。