多格骨牌

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目翻譯品質不佳。 (2020年2月17日) 翻譯者可能不熟悉中文或原文語言，也可能使用了機器翻譯。請協助翻譯本條目或重新編寫，并注意避免翻译腔的问题。明顯拙劣的翻譯請改掛{{d|G13}}提交刪除。 此條目可参照英語維基百科相應條目来扩充。 (2020年2月12日) 若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。

此條目目前正依照其他维基百科上的内容进行翻译。 (2020年2月15日) 如果您擅长翻译，並清楚本條目的領域，欢迎协助翻譯、改善或校对本條目。 此外，长期闲置、未翻譯或影響閱讀的内容可能会被移除。

多格骨牌（Polyomino），又稱多連塊、多連方、多方塊或多連方塊，是由全等正方形連成的圖形，包括四格骨牌、五格骨牌、六格骨牌等，n格骨牌的個數為（鏡射或旋轉視作同一種）：

1, 1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655, 17073, 63600, 238591, 901971, 3426576, 13079255, 50107909, 192622052, 742624232, 2870671950, ... （OEIS數列A000105）

除了n=0, 1, 2的顯然易見的條件以外，只有n=5的時候才能用所有的n格骨牌填滿一個長方形（見五格骨牌#長方形填充），n=3的情形顯然無解，對n=4和n=6無解的證明需要使用肢解西洋棋盤問題的概念，而${\displaystyle n\geq 7}$時，n格骨牌中有些骨牌的中間有空洞，因此也無解。

多格骨牌有三种，以对称分类：

1. 自由（两面）骨牌（刚体）：平移、转动、反射、Glide reflection（英语：Glide reflection）；可以包括洞以及單連通（无洞）的骨牌
2. 一片面：平移、转动（不可反射）
3. 固定（有向）：平移（不可转动、不可反射）

${\displaystyle n}$	名称	兩面（自由）[2]	片面（單邊）[3]	有向（固定）[4]
1	一格骨牌	1	1	1
2	二格骨牌	1	1	2
3	三格骨牌	2	2	6
4	四格骨牌	5	7	19
5	五格骨牌	12	18	63
6	六格骨牌	35	60	216
7	七格骨牌	108	196	760
8	八格骨牌	369	704	2725
9	九格骨牌	1285	2500	9910
10	十格骨牌	4655	9189	36446
11	十一格骨牌	17073	33896	135268
12	十二格骨牌	63600	126759	505861
13	十三格骨牌	238591	476270	1903890
14	十四格骨牌	901971	1802312	7204874
15	十五格骨牌	3426576	6849777	27394666

• 母函数
• 传递矩阵法^[5][6]，这使用统计力学的渗流理论（阅读文章，扩充内容）

若A(n)是自由n格骨牌的总数，則有猜想說明

${\displaystyle A_{n}\sim c\lambda ^{n}/n}$

其中${\displaystyle c\approx 0.3169,\ \lambda \approx 4.0626}$。但是这个是未解决的问题，缺乏证明。^[7]

但是有证明表示A為指數增長^[8][9]（${\displaystyle 4.00253<\lambda <4.65}$）

${\displaystyle \lim _{n\to \infty }(A_{n})^{1/n}=\lambda }$

• 双体模型，使用二格骨牌密铺格子
• 康威準則
• 娛樂數學
• 王氏砖^[10]

這些問題有些是NP完全的，或與递归集合有關。

任何少於或等於六格的骨牌都可以鋪滿整個平面，因為它們都滿足康威準則，而在全部108種七格骨牌中，有101種滿足康威準則，有104種可以鋪滿整個平面，另外4種（包括唯一一個中間有洞的那種）無法鋪滿整個平面，至於369種八格骨牌則有320種滿足康威準則，有343種可以鋪滿整個平面；1285種九格骨牌中則有960種滿足康威準則，有1050種可以鋪滿整個平面。

若需要至少n個多格骨牌P覆盖任何长方形（或矩形的格子），则n是P的次数（order）。若一個多格骨牌不可以覆盖（如Z形的四格骨牌），則其次数是未定义的。^[11][1][12]

L形骨牌有次数2。^[13]

次数${\displaystyle 4n}$的骨牌存在（n是整数）。^[12]

次数3的骨牌不存在。^[14][12]

未解決的数学問題：奇数次数的多格骨牌存在嗎？

可不可以使用5、7或9個骨牌密铺一个长方形這個問題仍未解答。有次数2的骨牌P，可以使用11個P覆盖一个更大的长方形。^[15][1][12]

更大奇数次数的骨牌存在。^[16][17]

截至2020年，有两个未解决的问题：

• 奇数次数的多格骨牌存在嗎？
• 若可以用n個骨牌密铺一个长方形，且n是奇数，最小的n為何？现在已知n最多為11。

未解決的数学問題：若可以用n個骨牌密铺一个长方形，且n是奇数，最小的n為何？现在已知n最多為11。

• 有些數獨#變體用多格骨牌
• 角鬥士棋
• 俄羅斯方塊

若可以用骨牌A覆盖每個n格骨牌，则A是共同超形式（common superform、CS）。若A是共同超形式中面积最小的那個，则A是最小共同超形式（minimal common superform、MCS）。比如，五格骨牌的MCS是下面两個九格骨牌。无论P是哪一個五格骨牌，P都可以放在这两個骨牌裡。^[1][12][18]

  ###     ### #####    #####   #       # 

• 多連立方體
• 渗流理论^[19][20]
• 杨表
• 角鬥士棋
• 多格形

1. ^ ^{1.0 1.1 1.2 1.3} Golomb, Golomb. Polyominoes. 1975. 
2. ^ （OEIS數列A000105）
3. ^ （OEIS數列A000988）
4. ^ （OEIS數列A001168）
5. ^ Jensen, Iwan. Enumerations of Lattice Animals and Trees. Journal of Statistical Physics. 2001, 102 (3/4): 865–881. doi:10.1023/A:1004855020556. 
6. ^ Conway, A. Enumerating 2D percolation series by the finite-lattice method: theory. Journal of Physics A: Mathematical and General. 1995-01-21, 28 (2): 335–349. ISSN 0305-4470. doi:10.1088/0305-4470/28/2/011. 
7. ^ Jensen, Iwan; Guttmann, Anthony J. Statistics of lattice animals (polyominoes) and polygons. Journal of Physics A: Mathematical and General. 2000-07-28, 33 (29): L257–L263. ISSN 0305-4470. doi:10.1088/0305-4470/33/29/102. 
8. ^ Barequet Gill, Rote Günter; ShalahMira. λ > 4: an improved lower bound on the growth constant of polyominoes. Communications of the ACM. 2016-06-24 [2020-02-15]. doi:10.1145/2851485. （原始内容存档于2020-06-30） （英语）.  Authors list列表缺少|last2= (帮助)
9. ^ Klarner, D. A.; Rivest, R. L. A Procedure for Improving the Upper Bound for the Number of n -Ominoes. Canadian Journal of Mathematics. 1973-06, 25 (3): 585–602. ISSN 0008-414X. doi:10.4153/CJM-1973-060-4 （英语）. 
10. ^ Golomb, Solomon W. Tiling with sets of polyominoes. Journal of Combinatorial Theory. 1970-07, 9 (1): 60–71 [2020-02-15]. doi:10.1016/S0021-9800(70)80055-2. （原始内容存档于2021-02-26） （英语）. 
11. ^ Tiling Rectangles With Polyominoes. www.eklhad.net. [2020-02-15]. （原始内容存档于2020-02-15）. 
12. ^ ^{12.0 12.1 12.2 12.3 12.4} Golomb, Solomon W. (Solomon Wolf). Polyominoes : puzzles, patterns, problems, and packings. 2nd ed. Princeton, N.J.: Princeton University Press https://www.worldcat.org/oclc/29358809. 1994. ISBN 0-691-08573-0. OCLC 29358809.  缺少或|title=为空 (帮助) 引文格式1维护：冗余文本 (link)
13. ^ Weisstein, Eric W. (编). L-Polyomino. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2020-02-15]. （原始内容存档于2015-07-26） （英语）. 
14. ^ Stewart, I. N; Wormstein, A. Polyominoes of order 3 do not exist. Journal of Combinatorial Theory, Series A. 1992-09-01, 61 (1): 130–136 [2020-02-15]. ISSN 0097-3165. doi:10.1016/0097-3165(92)90058-3. （原始内容存档于2020-01-12） （英语）. 
15. ^ Primes of the P hexomino. www.cflmath.com. [2020-02-15]. （原始内容存档于2016-03-22）. 
16. ^ Tiling Rectangles and Half Strips with Congruent Polyominoes. www.cflmath.com. [2020-02-15]. （原始内容存档于2020-01-15）. 
17. ^ co.combinatorics - Cutting a rectangle into an odd number of congruent pieces. MathOverflow. [2020-02-15]. （原始内容存档于2020-02-15）. 
18. ^ Polyomino Common Superforms. puzzlezapper.com. [2020-02-15]. （原始内容存档于2017-05-21）. 
19. ^ Whittington, S. G.; Soteros, C. E. (1990)., Whittington, S. G.; Soteros, C. E. (1990). "Lattice Animals: Rigorous Results and Wild Guesses".. 
20. ^ In Grimmett, G.; Welsh, D. (eds.)., In Grimmett, G.; Welsh, D. (eds.). Disorder in Physical Systems. Oxford University Press..