查看“︁多格骨牌”︁的源代码

{{Multiple issues|
{{Roughtranslation|time=2020-02-17T15:52:52+00:00}}
{{Expand English|time=2020-02-12T01:58:19+00:00}}
}}
{{Translating|||time=2020-02-15T07:54:03+00:00}}
'''多格骨牌'''（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無解的證明需要使用[[肢解西洋棋盤問題]]的概念，而<math>n\geq 7</math>時，n格骨牌中有些骨牌的中間有空洞，因此也無解。
[[File:Pentominos_square_8x8_016.svg|缩略图|12個[[五格骨牌]]形成一個8×8平方，刪除中間的2x2平方]][[File:Hexominoes.svg|thumb|35個[[六格骨牌]]（两面），不考慮對稱相同則有60個片面骨牌。<ref name=":0">{{Cite book|title=Polyominoes|last=Golomb|first=Golomb|publisher=|year=1975|isbn=|location=|pages=}}</ref> 不同顏色代表不同对称性类型。]]
[[File:Pseudopentominoes-chain10-02.svg|缩略图|94個六格骨牌的[[密铺]]]]

== 列表 ==
[[File:Tetrominoes_letter_oriented.png|缩略图|150x150像素|7種片面[[四格骨牌]]（<math>n</math> = 4）]]
[[File:Pentominos.svg|缩略图|150x150像素|12種両面[[五格骨牌]]（<math>n</math> = 5）。每個骨牌使用一个拉丁字母的字母。]]多格骨牌有三种，以[[对称]]分类：

# 自由（两面）骨牌（[[刚体]]）：[[平移]]、[[转动]]、[[反射 (数学)|反射]]、{{Internal link helper/en|Glide reflection|Glide reflection}}；可以包括洞以及[[單連通]]（无洞）的骨牌
# 一片面：[[平移]]、[[转动]]（不可反射）
# 固定（有向）：[[平移]]（不可转动、不可反射）

{| class="wikitable"
|-
!<math>n</math>
!名称
!兩面（自由）<ref>{{OEIS|A000105}}</ref>
!片面（單邊）<ref>{{OEIS|A000988}}</ref>
!有向（固定）<ref>{{OEIS|A001168}}</ref>
|-
| style="text-align:right;"|1
| style="text-align:center;"|[[一格骨牌]]
| style="text-align:right;"|1
| style="text-align:right;"|1
| style="text-align:right;"|1
|-
| style="text-align:right;"|2
| style="text-align:center;"|[[二格骨牌]]
| style="text-align:right;"|1
| style="text-align:right;"|1
| style="text-align:right;"|2
|-
| style="text-align:right;"|3
| style="text-align:center;"|[[三格骨牌]]
| style="text-align:right;"|2
| style="text-align:right;"|2
| style="text-align:right;"|6
|-
| style="text-align:right;"|4
| style="text-align:center;"|[[四格骨牌]]
| style="text-align:right;"|5
| style="text-align:right;"|7
| style="text-align:right;"|19
|-
| style="text-align:right;"|5
| style="text-align:center;"|[[五格骨牌]]
| style="text-align:right;"|12
| style="text-align:right;"|18
| style="text-align:right;"|63
|-
| style="text-align:right;"|6
| style="text-align:center;"|[[六格骨牌]]
| style="text-align:right;"|35
| style="text-align:right;"|60
| style="text-align:right;"|216
|-
| style="text-align:right;"|7
| style="text-align:center;"|[[七格骨牌]]
| style="text-align:right;"|108
| style="text-align:right;"|196
| style="text-align:right;"|760
|-
| style="text-align:right;"|8
| style="text-align:center;"|[[八格骨牌]]
| style="text-align:right;"|369
| style="text-align:right;"|704
| style="text-align:right;"|2725
|-
| style="text-align:right;"|9
| style="text-align:center;"|[[九格骨牌]]
| style="text-align:right;"|1285
| style="text-align:right;"|2500
| style="text-align:right;"|9910
|-
| style="text-align:right;"|10
| style="text-align:center;"|[[十格骨牌]]
| style="text-align:right;"|4655
| style="text-align:right;"|9189
| style="text-align:right;"|36446
|-
| style="text-align:right;"|11
| style="text-align:center;"|十一格骨牌
| style="text-align:right;"|17073
| style="text-align:right;"|33896
| style="text-align:right;"|135268
|-
| style="text-align:right;"|12
| style="text-align:center;"|十二格骨牌
| style="text-align:right;"|63600
| style="text-align:right;"|126759
| style="text-align:right;"|505861
|-
| style="text-align:right;"|13
| style="text-align:center;"|十三格骨牌
| style="text-align:right;"|238591
| style="text-align:right;"|476270
| style="text-align:right;"|1903890
|-
| style="text-align:right;"|14
| style="text-align:center;"|十四格骨牌
| style="text-align:right;"|901971
| style="text-align:right;"|1802312
| style="text-align:right;"|7204874
|-
| style="text-align:right;"|15
| style="text-align:center;"|十五格骨牌
| style="text-align:right;"|3426576
| style="text-align:right;"|6849777
| style="text-align:right;"|27394666
|}

== 计算算法 ==

* [[母函数]]
* [[传递矩阵法]]<ref>{{Cite journal|title=Enumerations of Lattice Animals and Trees|url=http://link.springer.com/10.1023/A:1004855020556|last=Jensen|first=Iwan|date=2001|journal=Journal of Statistical Physics|issue=3/4|doi=10.1023/A:1004855020556|others=|year=|volume=102|page=|pages=865–881|pmid=}}</ref><ref>{{Cite journal|title=Enumerating 2D percolation series by the finite-lattice method: theory|url=http://stacks.iop.org/0305-4470/28/i=2/a=011?key=crossref.03a0d1a73223db63974e059c88808ff5|last=Conway|first=A|date=1995-01-21|journal=Journal of Physics A: Mathematical and General|issue=2|doi=10.1088/0305-4470/28/2/011|volume=28|pages=335–349|issn=0305-4470}}</ref>，这使用[[统计力学]]的[[渗流理论]]（阅读文章，扩充内容）

== [[渐近分析]] ==
若A(n)是自由n格骨牌的总数，則有猜想說明

<math>A_n \sim c\lambda^n / n</math>

其中<math>c \approx 0.3169, \ \lambda \approx 4.0626</math>。但是这个是未解决的问题，缺乏证明。<ref>{{Cite journal|title=Statistics of lattice animals (polyominoes) and polygons|url=http://stacks.iop.org/0305-4470/33/i=29/a=102?key=crossref.6969da9a5c66fd4dc275f43fef7e4148|last=Jensen|first=Iwan|last2=Guttmann|first2=Anthony J|date=2000-07-28|journal=Journal of Physics A: Mathematical and General|issue=29|doi=10.1088/0305-4470/33/29/102|volume=33|pages=L257–L263|issn=0305-4470}}</ref>

但是有证明表示A為[[指數增長]]<ref>{{Cite journal|title=λ > 4: an improved lower bound on the growth constant of polyominoes|author=Barequet Gill, Rote Günter|url=https://dl.acm.org/doi/abs/10.1145/2851485|last=|last2=|date=2016-06-24|journal=Communications of the ACM|issue=|doi=10.1145/2851485|others=|year=|volume=|page=|language=EN|pmid=|last3=ShalahMira|access-date=2020-02-15|archive-date=2020-06-30|archive-url=https://web.archive.org/web/20200630200147/https://dl.acm.org/doi/abs/10.1145/2851485|dead-url=no}}</ref><ref>{{Cite journal|title=A Procedure for Improving the Upper Bound for the Number of n -Ominoes|url=https://www.cambridge.org/core/product/identifier/S0008414X00050628/type/journal_article|last=Klarner|first=D. A.|last2=Rivest|first2=R. L.|date=1973-06|journal=Canadian Journal of Mathematics|issue=3|doi=10.4153/CJM-1973-060-4|volume=25|pages=585–602|language=en|issn=0008-414X}}</ref>（<math>4.00253 < \lambda < 4.65</math>）

<math>\lim_{n \to \infty} (A_n)^{1/n} = \lambda</math>

== 密铺 ==

* [[双体模型]]，使用[[二格骨牌]]密铺[[格子]]
*[[康威準則]]
*[[娛樂數學]]
*[[王氏砖]]<ref>{{Cite journal|title=Tiling with sets of polyominoes|url=https://linkinghub.elsevier.com/retrieve/pii/S0021980070800552|last=Golomb|first=Solomon W.|date=1970-07|journal=Journal of Combinatorial Theory|issue=1|doi=10.1016/S0021-9800(70)80055-2|volume=9|pages=60–71|language=en|access-date=2020-02-15|archive-date=2021-02-26|archive-url=https://web.archive.org/web/20210226142934/https://linkinghub.elsevier.com/retrieve/pii/S0021980070800552|dead-url=no}}</ref>

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

=== 平面 ===

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

=== 长方形 ===
[[File:L-polyomino.svg|缩略图|L骨牌有次数2]]
若需要至少n個多格骨牌P覆盖'''任何'''[[长方形]]（或矩形的[[格子]]），则n是P的'''次数'''（order）。若一個多格骨牌不可以覆盖（如Z形的[[四格骨牌]]），則其次数是未定义的。<ref>{{Cite web|title=Tiling Rectangles With Polyominoes|url=http://www.eklhad.net/polyomino/index.html|accessdate=2020-02-15|work=www.eklhad.net|archive-date=2020-02-15|archive-url=https://web.archive.org/web/20200215082850/http://www.eklhad.net/polyomino/index.html|dead-url=no}}</ref><ref name=":0" /><ref name=":1">{{Cite book|edition=2nd ed|chapter=Polyominoes : puzzles, patterns, problems, and packings|url=https://www.worldcat.org/oclc/29358809|publisher=Princeton University Press|date=1994|location=Princeton, N.J.|isbn=0-691-08573-0|oclc=29358809|last=Golomb, Solomon W. (Solomon Wolf)}}</ref>
[[File:11-odd-order-hexomino.svg|缩略图|left|可以使用11個六格骨牌密铺长方形]]
'''L形骨牌'''有次数2。<ref>{{Cite mathworld|title=L-Polyomino|urlname=L-Polyomino|accessdate=2020-02-15|last=Weisstein|first=Eric W.|work=mathworld.wolfram.com|language=en|archive-date=2015-07-26|archive-url=https://web.archive.org/web/20150726234357/http://mathworld.wolfram.com/L-Polyomino.html|dead-url=no}}</ref>

次数<math>4n</math>的骨牌存在（n是[[整数]]）。<ref name=":1" />

次数3的骨牌不存在。<ref>{{Cite journal|title=Polyominoes of order 3 do not exist|url=http://www.sciencedirect.com/science/article/pii/0097316592900583|last=Stewart|first=I. N|last2=Wormstein|first2=A|date=1992-09-01|journal=Journal of Combinatorial Theory, Series A|issue=1|doi=10.1016/0097-3165(92)90058-3|volume=61|pages=130–136|language=en|issn=0097-3165|access-date=2020-02-15|archive-date=2020-01-12|archive-url=https://web.archive.org/web/20200112164229/https://www.sciencedirect.com/science/article/pii/0097316592900583|dead-url=no}}</ref><ref name=":1" />{{Unsolved|数学|[[奇数]]次数的多格骨牌存在嗎？}}可不可以使用5、7或9個骨牌密铺一个长方形這個問題仍未解答。有次数2的骨牌P，可以使用11個P覆盖一个更大的长方形。<ref>{{Cite web|title=Primes of the P hexomino|url=http://www.cflmath.com/~reid/Polyomino/p6_rect.html|accessdate=2020-02-15|work=www.cflmath.com|archive-date=2016-03-22|archive-url=https://web.archive.org/web/20160322171000/http://www.cflmath.com/~reid/Polyomino/p6_rect.html|dead-url=no}}</ref><ref name=":0" /><ref name=":1" />

更大奇数次数的骨牌存在。<ref>{{Cite web|title=Tiling Rectangles and Half Strips with Congruent Polyominoes|url=http://www.cflmath.com/~reid/Research/Halfstrip/index.html|accessdate=2020-02-15|work=www.cflmath.com|archive-date=2020-01-15|archive-url=https://web.archive.org/web/20200115071042/http://cflmath.com/~reid/Research/Halfstrip/index.html|dead-url=no}}</ref><ref>{{Cite web|title=co.combinatorics - Cutting a rectangle into an odd number of congruent pieces|url=https://mathoverflow.net/questions/11753/cutting-a-rectangle-into-an-odd-number-of-congruent-pieces|accessdate=2020-02-15|work=MathOverflow|archive-date=2020-02-15|archive-url=https://web.archive.org/web/20200215085750/https://mathoverflow.net/questions/11753/cutting-a-rectangle-into-an-odd-number-of-congruent-pieces|dead-url=no}}</ref>

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

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

== 謎題和遊戲 ==

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

=== 最小面积 ===
若可以用骨牌A覆盖每個n格骨牌，则A是'''共同超形式'''（common superform、CS）。若A是共同超形式中面积最小的那個，则A是'''最小共同超形式'''（minimal common superform、MCS）。比如，[[五格骨牌]]的MCS是下面两個[[九格骨牌]]。无论P是哪一個五格骨牌，P都可以放在这两個骨牌裡。<ref name=":0" /><ref name=":1" /><ref>{{Cite web|title=Polyomino Common Superforms|url=http://puzzlezapper.com/aom/mathrec/polycover.html|accessdate=2020-02-15|work=puzzlezapper.com|archive-date=2017-05-21|archive-url=https://web.archive.org/web/20170521163752/http://puzzlezapper.com/aom/mathrec/polycover.html|dead-url=no}}</ref><pre>
  ###     ###
#####    #####
  #       #
</pre>

==參見==

*[[多連立方體]]
*[[渗流理论]]<ref>{{Cite book|title="Lattice Animals: Rigorous Results and Wild Guesses".|last=Whittington, S. G.; Soteros, C. E. (1990).|first=Whittington, S. G.; Soteros, C. E. (1990).|publisher=|year=|isbn=|location=|pages=}}</ref><ref>{{Cite book|title=Disorder in Physical Systems. Oxford University Press.|last=In Grimmett, G.; Welsh, D. (eds.).|first=In Grimmett, G.; Welsh, D. (eds.).|publisher=|year=|isbn=|location=|pages=}}</ref>
*[[杨表]]
*[[角鬥士棋]]
*[[多格形]]

== 參考文獻 ==
<references /><br />

{{Polyform}}

[[Category:多連塊]]
[[Category:骨牌]]
[[Category:几何形状]]
[[Category:離散幾何]]