万维百科

多格骨牌

多格骨牌(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无解的证明要用到肢解国际象棋盘问题的概念,而则是n格骨牌中有些是中间有空洞的,因此也无解。

12把五格骨牌,8×8平方,删除中间2x2平方
35把六格骨牌(两面),不然有60把片面骨牌。 不同颜色代表不同对称性类型。
94把六格骨牌的密铺

列表

7种类的片面四格骨牌 = 4)
12种类的両面5格骨牌 = 5)。每把骨牌使用一个拉丁字母的字母。

有三种多格骨牌,使用对称性分类:

  1. 自由(两面)骨牌(刚体):平移转动反射Glide reflection英语Glide reflection;可以包括洞以及单连通(无洞)的骨牌
  2. 一片面:平移转动(不可反射)
  3. 固定(有向):平移(不可转动、不可反射)
名称 两面(自由) 片面(单边) 有向(固定)
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

计算算法

渐近分析

若A(n)是自由n格骨牌的总数,有人猜想

其中。但是这个是未解决的问题,缺乏证明。

但是有人证明A表示指数增长

这也许是普遍性的极限。

密铺

有时候这些问题是NP完全的,或者跟递归集合有关。

平面

任何少于或等于六格的骨牌都可以铺满整个平面,因为都满足康威准则,而全部108种七格骨牌当中,有101种满足康威准则,而有104种可以铺满整个平面,另外4种(包括唯一一个中间有洞的那种)是没办法铺满整个平面的,至于369种八格骨牌则有320种满足康威准则,343种可以铺满整个平面,1285种九格骨牌则有960种满足康威准则,1050种可以铺满整个平面。

长方形

L骨牌有次数2

若需要至少n把多格骨牌P覆盖任何长方形(或长方形的格子),则n是P的次数(order)。若不可以覆盖(例如Z形的四格骨牌),次数是未定义的。

可以使用11把六格骨牌密铺长方形

L形骨牌有次数2。

次数的骨牌存在(n是整数)。

次数3 的骨牌不存在。

Question mark2.svg

不知道可以使用5、7、9把骨牌密铺一个长方形。有次数2的骨牌P,可以使用11把P覆盖一个更大的长方形。

更大奇数次数的骨牌存在。

但是截至2020年,有两个未解决的问题:

  • 奇数次数的多格骨牌没?
  • 若可以用n把骨牌密铺一个长方形,而且n是奇数,最小的n是啥?现在知道n最多是11。
Question mark2.svg

谜题和游戏

最小面积

若可以用骨牌A覆盖每把n格骨牌,则A是共同超形式(common superform、CS)。若A有最小的面积,则A是最小共同超形式(minimal common superform、MCS)。比方说,五格骨牌的MCS是下面两把九格骨牌。无论P是哪一把五格骨牌,P都可以放在这两把骨牌。

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

参见

参考文献

  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. doi:10.1145/2851485 (英语). 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. doi:10.1016/S0021-9800(70)80055-2 (英语).
  11. ^ Tiling Rectangles With Polyominoes. www.eklhad.net. [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=为空 (帮助)
  13. ^ Weisstein, Eric W. L-Polyomino. mathworld.wolfram.com. [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. ISSN 0097-3165. doi:10.1016/0097-3165(92)90058-3 (英语).
  15. ^ Primes of the P hexomino. www.cflmath.com. [2020-02-15].
  16. ^ Tiling Rectangles and Half Strips with Congruent Polyominoes. www.cflmath.com. [2020-02-15].
  17. ^ co.combinatorics - Cutting a rectangle into an odd number of congruent pieces. MathOverflow. [2020-02-15].
  18. ^ Polyomino Common Superforms. puzzlezapper.com. [2020-02-15].
  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..



本页面最后更新于2021-05-22 17:59,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器